http://www.ebook.edu.vn
Phˆa
`
n phu
.
lu
.
c A
Thu
.
viˆe
.
n Graph.h
Du
.
´o
.
i d¯ˆay l`a thu
.
viˆe
.
n gˆo
`
m c´ac cˆa
´
u tr´uc d˜u
.
liˆe
.
u v`a c´ac thu
˙’

#define TRUE 1
#define FALSE 0
#define INFTY 32767
#define MAXEDGES 50 // So cuc dai cac canh
#define MAXVERTICES 25 // So cuc dai cac \dd\ir nh
#define MAXSTRINGS 16 // Chieu dai cuc dai xau ky tu
197
http://www.ebook.edu.vn
/****** Phan dinh nghia cac kieu du lieu *****/
typedef unsigned char byte;
typedef byte Boolean;
typedef char DataType[MAXSTRINGS+1]; // Them mot ma ket thuc chuoi
/*******************************
Cau truc du lieu: don lien ket
*******************************/
typedef struct VertexNode *AdjPointer;
struct VertexNode
{
byte Vertex;
int Length;
int Flow;
AdjPointer Next;
};
typedef struct
{
DataType Data;
AdjPointer Next;
} HeadNode;
typedef HeadNode *HeadPointer;
typedef HeadPointer ArrayOfPointer[MAXVERTICES];

/***** Phan khai bao prototype ham *****/
void Create(AdjPointer *List);
Boolean Empty(AdjPointer List);
void Push(AdjPointer *List, byte Item);
void Pop(AdjPointer *List, byte *Item);
void CreatQueue(Queue *Q);
Boolean EmptyQueue(Queue Q);
void PushQueue(Queue *Q, byte Item);
void PopQueue(Queue *Q, byte *Item);
Boolean EmptySet(SetOfVertices S);
Boolean InSet(SetOfVertices S, byte Value);
void InitSet(SetOfVertices S, byte MaxValue);
void AddSet(SetOfVertices S, byte Value);
void SubSet(SetOfVertices S, byte Value);
void MakeV_out(char *FileName, ArrayOfPointer V_out, byte *NumVertices,
199
http://www.ebook.edu.vn
Boolean Weight);
void MakeV_in(char *FileName, ArrayOfPointer V_in, ArrayOfPointer V_out,
byte *NumVertices);
void BuildGraph(char *FileName, ArrayOfEdge E, byte *NumVertices);
void DisplayV_out(ArrayOfPointer V_out, byte NumVertices, Boolean Weight);
void DisplayV_in(ArrayOfPointer V_in, byte NumVertices);
void DFS(ArrayOfEdge E, byte Start, SetOfVertices S);
void PathTwoVertex(Path Pred, byte Start, byte Terminal);
void PopHeadPtr(byte NumVertices, ArrayOfPointer V_out);
/***** Phan cai dat cac ham *****/
void Create(AdjPointer *List)
{
(*List) = NULL;

(*Q).Head = NULL;
}
Boolean EmptyQueue(Queue Q)
{
return((Q.Head == NULL) ? TRUE : FALSE);
}
void PushQueue(Queue *Q, byte Item)
{
QueueNode TempPtr;
TempPtr = (QueueNode) malloc(sizeof(struct QueueType));
TempPtr->Vertex = Item;
TempPtr->Next = NULL;
if ((*Q).Head == NULL) (*Q).Head = TempPtr;
else (*Q).Tail->Next = TempPtr;
(*Q).Tail = TempPtr;
}
void PopQueue(Queue *Q, byte *Item)
{
QueueNode TempPtr;
if (EmptyQueue(*Q))
{
printf(" Thao tac con tro khong hop le ");
return;
}
TempPtr = (*Q).Head;
(*Item) = TempPtr->Vertex;
(*Q).Head = TempPtr->Next;
free(TempPtr);
201
http://www.ebook.edu.vn

return;
}
202
http://www.ebook.edu.vn
S[(Value-1)/8] |= 0x80 >> ((Value-1)%8);
}
void SubSet(SetOfVertices S, byte Value)
{
if ((Value < 1) || (Value > MAXVERTICES))
{
printf(" Gia tri khong thuoc tap hop ");
return;
}
S[(Value-1)/8] &= ~(0x80 >> ((Value-1)%8));
}
int feoln(FILE *fp)
{
char c;
if ((c=fgetc(fp))==10)
{
fseek(fp, -2, 1);
return(TRUE);
}
else
if (c==EOF) return(TRUE);
else
{
fseek(fp, -1, 1);
return(FALSE);
}

fscanf(FileData, "%d", &(VerPtr->Vertex));
if (Weight)
{
fscanf(FileData, "%d", &(VerPtr->Length));
VerPtr->Flow = 0;
}
VerPtr->Next = HeadPtr->Next;
HeadPtr->Next = VerPtr;
}
freadln(FileData);
++NumVert;
V_out[NumVert] = HeadPtr;
}
(*NumVertices) = NumVert;
fclose(FileData);
}
void MakeV_in(char *FileName, ArrayOfPointer V_in, ArrayOfPointer V_out,
byte *NumVertices);
{
byte NumVert;
204
http://www.ebook.edu.vn
int i, j;
HeadPointer HeadPtr;
AdjPointer CurrPtr, VerPtr;
MakeV_out(FileName, V_out, &NumVert, TRUE);
(*NumVertices) = NumVert;
for (i=1; i<=NumVert; i++)
{
HeadPtr = (HeadPointer) malloc(sizeof(HeadNode));

{
205
http://www.ebook.edu.vn
printf(" File khong tim thay ");
return;
}
NumVert = 0;
while (!feoln(FileData))
{
++NumVert;
E[NumVert] = (ListEdgePointer) malloc(sizeof(ListEdge));
fscanf(FileData, "%s", ch);
E[NumVert]->Data = ch[0];
E[NumVert]->Next = NULL;
}
(*NumVertices) = NumVert;
for (i=1; i<=NumVert; i++) printf("%c ", E[i]->Data);
printf("\n");
freadln(FileData);
while (!feof(FileData))
{
EdgePtr = (EdgePointer) malloc(sizeof(struct EdgeNode));
for (i=0; i<2; i++)
{
fscanf(FileData, "%d", &EndPt);
printf("%d ", EndPt);
EdgePtr->Vertex[i] = EndPt;
EdgePtr->Link[i] = E[EndPt]->Next;
E[EndPt]->Next = EdgePtr;
}

AdjPointer CurrPtr;
for (i=1; i<=NumVertices; i++)
{
printf("(%d) %s ", i, V_out[i]->Data);
CurrPtr = V_out[i]->Next;
while (CurrPtr!=NULL)
{
printf("%d ", CurrPtr->Vertex);
if (Weight) printf("%d ", CurrPtr->Length);
CurrPtr = CurrPtr->Next;
}
printf("\n");
}
printf("\n");
}
void DisplayV_in(ArrayOfPointer V_in, byte NumVertices)
{
int i;
AdjPointer CurrPtr;
for (i=1; i<=NumVertices; i++)
207
http://www.ebook.edu.vn
{
printf("%s ", V_in[i]->Data);
CurrPtr = V_in[i]->Next;
while (CurrPtr!=NULL)
{
printf(" %d %d", CurrPtr->Vertex, CurrPtr->Length);
CurrPtr = CurrPtr->Next;
}

o
[1] Appel K., The proof of the four-colour problem, New Scientist. 72, 154-155 (1976).
[2] Arlinghaus S., Arlinghaus W., Nystuen J., The Hedetniemi matrix sum: an algorithm
for shortest path and shortest distance, Geographical Analysis, Vol. 22, No. 4, Oct.,
351-360 (1990).
[3] Bellman R., On a routing problem, Quart. of Applied Mathematics, 16, 87 (1958).
[4] Berge C., L´y thuyˆe
´
t d¯ˆo
`
thi
.
v`a ´u
.
ng du
.
ng, NXB Khoa ho
.
c v`a K˜y thuˆa
.
t H`a Nˆo
.
i, 1971.
[5] Berge C., Two theorems in graph theory, Proc. Nat. Ac. Sc., 43, 842 (1957).
[6] Berry R. C., A constrained shortest path, Paper presented at the 39th National ORSA
Metting, Dallas, Texas (1971).
[7] Bondy J. A., Properties of graphs with constraints on degrees, Studia Sci. Math. Hung.
4 473-475 (1969).
[8] Bondy J. A., Chvatal V., A method in graph theory, Discrete Math. 15, 111-135 (1976).
[9] Brooks R. L., On coloring the nodes of a network, Proc. Cambridge Phil. Soc., Vol. 37,

(1962).
[28] Gilbert E. N., Pollack H. O., Steiner minimal trees, Jl. of SIAM (Appl. Math.), 16 1
(1968).
[29] Gomory R. E., Hu T. C., Synthesis of a communication network, Jl. of SIAM (App.
Math.), 12 348 (1964).
[30] Gondran M., Minoux M., Vajda S., Graphs and algorithms, John Wiley & Sons (1990).
[31] Hamming R. W., Coding and information theory, Prentice Hall (1980).
[32] Hanan M., On Steiner’s problem with rectilinear distance, Jl. of SIAM (Appl. Math.),
14 255 (1966).
210
http://www.ebook.edu.vn
[33] Hopcroft J. E., Tarjan R. E., Isomorphism of planar graphs, in Complexity of Computer
Computations, Plenum, New York (1972).
[34] Hopcroft J. E., Tarjan R. E., Efficient planarity testing, J. ACM 21, 549-568 (1974).
[35] Hu T. C., Integer programming and network flows, Addison-Wesley, Reading, Mas-
sachusetts (1969).
[36] Kerchenbaum A., Van Slyke R., Computing minimum spanning trees efficiently, Proc.
of the Ann. Conf. of ACM, Boston, 518 (1972).
[37] Kirchhoff G., in “Annalen der Physik and Chemie” 72, 497 (1847).
[38] Klein M., A primal method for minimal cost flows with applications to the assignment
and transportation problems, Man. Sci., 14, 205 (1967).
[39] Kruskal J. B. Jr., On the shortest spanning subtree of a graph and the traveling salesman
problem, Proc. American Mathematical Soc., 7, 48 (1956).
[40] Kraitchik M., Le probl`eme des Reines, Bruxelles (1926).
[41] Kevin V., Whitney M., Algorithm 422-Minimum spanning tree, Comm. of ACM, 15,
273 (1972).
[42] Las Vergnas M., Probl`emes de couplage et probl`emes hamiltoniens en th´eorie des
graphes, Doctoral thesis, Univsit´e de Paris VI (1972).
[43] Larry N., Sanford L., Lˆa
.

[53] Tarjan R., Depth-first search and linear graph algorithms, SIAM J. Computer 1 146-160
(1972).
[54] Tutte W. T., How to draw graph, Proc. London Math. Soc., Ser. 3, Vol. 13, 743-768
(1963).
[55] Whitney H., 2−Isomorphic graphs, Am. J. Math. Vol. 55 245-254 (1933).
212