Đồ thị và các thuật toán - Phụ lục

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:16

Thêm vào BST

Báo xấu

77
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo giáo trình Đồ thị và các thuật toán - Graph

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đồ thị và các thuật toán - Phụ lục

` Phˆn phu luc A a .. Thu. viˆn Graph.h e . Du.´.i d ˆy l` thu. viˆn gˆm c´c cˆ u tr´c d˜. liˆu v` c´c thu tuc cˆn thiˆt hˆ tro. viˆc c`i d at ´˜ e` ´ ˙.` ’ o ¯a a .o aa u ue aa a e o . e a ¯ˇ . . . c´c thuˆt to´n trong gi´o tr` a a a a ınh. . /************************************************** Luu y: Tat ca cac file du lieu dung voi Thu vien nay phai duoc tao bang trinh Norton Commander. **************************************************/ #if !defined(graph_h) #define graph_h #include #include #include #include /****** Phan dinh nghia cac hang *****/ #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 http://www.ebook.edu.vn 197
/****** 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]; typedef struct QueueType *QueueNode; struct QueueType { byte Vertex; QueueNode Next; }; typedef struct { QueueNode Head, Tail; } Queue; typedef byte Path[MAXVERTICES]; http://www.ebook.edu.vn 198
typedef byte SetOfVertices[(MAXVERTICES%8)?((MAXVERTICES/8)+1):(MAXVERTICES/8)]; /*********************************** Danh sach da lien ket cho cac canh ***********************************/ typedef struct EdgeNode *EdgePointer; struct EdgeNode { byte Vertex[2]; EdgePointer Link[2]; }; typedef struct { char Data; EdgePointer Next; } ListEdge; typedef ListEdge *ListEdgePointer; typedef ListEdgePointer ArrayOfEdge[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, http://www.ebook.edu.vn 199
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; } Boolean Empty(AdjPointer List) { return((List == NULL) ? TRUE : FALSE); } void Push(AdjPointer *List, byte Item) { AdjPointer TempPtr; TempPtr = (AdjPointer) malloc(sizeof(struct VertexNode)); TempPtr->Vertex = Item; TempPtr->Next = (*List); (*List) = TempPtr; } void Pop(AdjPointer *List, byte *Item) { AdjPointer TempPtr; if (Empty(*List)) { printf(" Thao tac con tro khong hop le "); return; http://www.ebook.edu.vn 200
} TempPtr = (*List); (*Item) = TempPtr->Vertex; (*List) = TempPtr->Next; free(TempPtr); } void CreatQueue(Queue *Q) { (*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); http://www.ebook.edu.vn 201
} Boolean EmptySet(SetOfVertices S) { int i, k = (MAXVERTICES %8 ) ? ((MAXVERTICES / 8) + 1) : (MAXVERTICES / 8); for (i = 0; i < k; i++) if (S[i] != 0) return(FALSE); return(TRUE); } Boolean InSet(SetOfVertices S, byte Value) { if ((Value < 1) || (Value > MAXVERTICES)) return(FALSE); return((S[(Value - 1) / 8] & (0x80 >> ((Value - 1) % 8))) ? TRUE : FALSE); } void InitSet(SetOfVertices S, byte MaxValue) { int i; if (MaxValue>MAXVERTICES) { printf(" Gia tri khong thuoc tap hop "); return; } for (i = 0; i < MaxValue; i++) S[i/8] |= 0x80 >> (i%8); } void AddSet(SetOfVertices S, byte Value) { int i; if ((Value < 1) || (Value > MAXVERTICES)) { printf(" Gia tri khong thuoc tap hop "); return; } http://www.ebook.edu.vn 202
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); } } void freadln(FILE *fp) { char c; while (((c=fgetc(fp))!=10)&&(c!=EOF)); } void MakeV_out(char *FileName, ArrayOfPointer V_out, byte *NumVertices, Boolean Weight) { http://www.ebook.edu.vn 203
byte NumVert; HeadPointer HeadPtr; AdjPointer VerPtr; FILE *FileData; if ((FileData = fopen(FileName, "rt")) == NULL) { printf(" File khong tim thay "); return; } NumVert = 0; while (!feof(FileData)) { HeadPtr = (HeadPointer) malloc(sizeof(HeadNode)); HeadPtr->Next = NULL; fgets(HeadPtr->Data, MAXSTRINGS+1, FileData); // Ham fgets(char *s, int n, FILE *fp) chi doc n-1 ky tu while (!feoln(FileData)) { VerPtr = (AdjPointer) malloc(sizeof(struct VertexNode)); 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; http://www.ebook.edu.vn 204
int i, j; HeadPointer HeadPtr; AdjPointer CurrPtr, VerPtr; MakeV_out(FileName, V_out, &NumVert, TRUE); (*NumVertices) = NumVert; for (i=1; iData, V_out[i]->Data); HeadPtr->Next = NULL; for (j=1; jNext; while (CurrPtr!=NULL) { if (CurrPtr->Vertex==i) { VerPtr=(AdjPointer)malloc(sizeof(struct VertexNode)); VerPtr->Vertex = j; VerPtr->Length = CurrPtr->Length; VerPtr->Flow = 0; VerPtr->Next = HeadPtr->Next; HeadPtr->Next = VerPtr; } CurrPtr = CurrPtr->Next; } } V_in[i] = HeadPtr; } } void BuildGraph(char *FileName, ArrayOfEdge E, byte *NumVertices) { byte EndPt, NumVert; int i; char ch[2]; EdgePointer EdgePtr; FILE *FileData; if ((FileData = fopen(FileName, "rt")) == NULL) { http://www.ebook.edu.vn 205
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; iData); printf("\n"); freadln(FileData); while (!feof(FileData)) { EdgePtr = (EdgePointer) malloc(sizeof(struct EdgeNode)); for (i=0; iVertex[i] = EndPt; EdgePtr->Link[i] = E[EndPt]->Next; E[EndPt]->Next = EdgePtr; } printf("\n"); freadln(FileData); } fclose(FileData); } void DFS(ArrayOfEdge E, byte Start, SetOfVertices Unvisited) { EdgePointer Ptr; byte StartEnd, OtherEnd, NewStart; SubSet(Unvisited, Start); http://www.ebook.edu.vn 206
Ptr = E[Start]->Next; while ((!EmptySet(Unvisited))&&(Ptr!=NULL)) { StartEnd = 0; OtherEnd = 1; if (Ptr->Vertex[0]!=Start) { StartEnd = 1; OtherEnd = 0; } NewStart = Ptr->Vertex[OtherEnd]; if (InSet(Unvisited, NewStart)) DFS(E, NewStart, Unvisited); Ptr = Ptr->Link[StartEnd]; } } void DisplayV_out(ArrayOfPointer V_out, byte NumVertices, Boolean Weight) { int i; AdjPointer CurrPtr; for (i=1; iData); 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
{ printf("%s ", V_in[i]->Data); CurrPtr = V_in[i]->Next; while (CurrPtr!=NULL) { printf(" %d %d", CurrPtr->Vertex, CurrPtr->Length); CurrPtr = CurrPtr->Next; } printf("\n"); } } void PathTwoVertex(Path Pred, byte Start, byte Terminal) { if (Terminal != Start) { PathTwoVertex(Pred, Start, Pred[Terminal]); printf(" ---> %2d", Terminal); } } void PopHeadPtr(byte NumVertices, ArrayOfPointer V_out) { byte Item; int i; AdjPointer CurrPtr; for (i=1; iNext; while (CurrPtr != NULL) Pop(&CurrPtr, &Item); free(V_out[i]); } } #endif http://www.ebook.edu.vn 208
˙ ’ T`i liˆu tham kha o ae . [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´ thuyˆt d` thi v` u.ng dung, NXB Khoa hoc v` K˜ thuˆt H` Nˆi, 1971. ´o y e ¯ˆ . a ´ .ay a ao . . . [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, 194-197 (1941). [10] Busacker R. G., Gowen P. J., A procedure for determining a family of minimal-cost network ﬂow patterns, Operations Research Oﬃce, Technical paper 15 (1961). [11] Cayley A., Collected papers, Quart. Jl. of Mathematics, 13 Cambridge, 26 (1897). [12] Chase S. M., Analysis of algorithms for ﬁnding all spanning trees of a graph, Report No. 401, Department of Computer Science, University of Illinois, Urbana, Oct. (1970). [13] Chvatal V., On Hamilton’s ideals, J. Combinat. Theory B 12 163-168 (1972). [14] Christoﬁdes N., Graph theory an algorithmic approach, Academic Press INC. (1975). http://www.ebook.edu.vn 209
[15] Coxeter H. S. M., Introduction to geometry, Wiley, New York (1961). [16] Danzig G. B., All shortest routes in a graph, in Th´orie des graphes, Proceedings of the e International Symposium, Rome 1966, Dunod, Paris, 91-92 (1967). [17] Dirac G. A., Some theorems on abstract graphs, Proc. London Math. Soc. 2, 68-81 (1952). [18] De Freisseix H., Rosenstiehl P., The depth-search theorem for planarity, in Proceedings of the Cambridge Combinatorial Conference, North Holland, Amsterdam (1982). [19] Deo N., Graph theory with applications to engineering and computer science, Prentice- Hall Inc. (1974). [20] Dijkstra, E. W., A note on two problems in connection with graphs, Numerische Math- ematik, 1, 269 (1959). [21] Dreyfus S. E., Wagner R. A., The Steiner problem in graphs, Networks, 1, 195 (1972). [22] Euler L., Solutio problematis ad geometriam situs pertinentis, Commun. Acad. Sci. Imp. Petropol. 8, Opera Omnia (1), Vol. 7, 128-140 (1736). [23] Euler L., Commentationes Arithmeticae collectae, St. Petersburg, (1766). [24] Fary I., On straight line representation of planar graphs, Acta Sci. Math. Szeged, Vol. 11, 229-293 (1948). [25] Floyd R. W., Algorithm 97-Shortest path, Comm. of ACM, 5, 345 (1962). [26] Ford L. R. Jr., Network ﬂow theory, Rand Corporation Report 923 (1946). [27] Ford L. R., Fulkerson D. R., Flows in networks, Princeton University Press, Princeton (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). http://www.ebook.edu.vn 210
[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., Eﬃcient planarity testing, J. ACM 21, 549-568 (1974). [35] Hu T. C., Integer programming and network ﬂows, Addison-Wesley, Reading, Mas- sachusetts (1969). [36] Kerchenbaum A., Van Slyke R., Computing minimum spanning trees eﬃciently, Proc. of the Ann. Conf. of ACM, Boston, 518 (1972). [37] Kirchhoﬀ G., in “Annalen der Physik and Chemie” 72, 497 (1847). [38] Klein M., A primal method for minimal cost ﬂows 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`me des Reines, Bruxelles (1926). e [41] Kevin V., Whitney M., Algorithm 422-Minimum spanning tree, Comm. of ACM, 15, 273 (1972). [42] Las Vergnas M., Probl`mes de couplage et probl`mes hamiltoniens en th´orie des e e e graphes, Doctoral thesis, Univsit´ de Paris VI (1972). e [43] Larry N., Sanford L., Lˆp tr`nh nˆng cao bˇ ng Pascal v´.i c´c cˆ u tr´c d˜. liˆu, Scitec. ` ´ a ı a a oaa u ue . . [44] Mei-Ko Kwan, Graphic programming using odd or even points, Chinese Math. 1, 273 (1962). [45] Moore E. F., The shortest path through a maze, Proc. Int. Symp. on the Theory of Switching, Path II, 285 (1957). [46] Murchland J. D., A new method for ﬁnding all elementary paths in a complete directed graph, London School of Economics, Report LSE-TNT-22 (1965). [47] Ore O., Note on Hamilton circuits, Amer. Math. Mothly, 67, 55 (1960). [48] Ore O., The four colour problem, Academic Press, New York (1967). [49] Prim R. C., Shortest connection networks and some generalizations, Bell Syst. Tech. Jl., 36, 1389 (1957). [50] Paton K., An algorithm for ﬁnding a fundamental set of cycles of a graph, Comm. ACM, Vol. 12, No. 9, Sept., 514-518 (1969). http://www.ebook.edu.vn 211
[51] P´sa L., A theorem concerning Hamiltonian lines, Magyar Tud. Akad. Mat. Kutat´ o o Inst. Kozl 7 255-226 (1962). [52] Shirey R. W., Implementation and analysis of eﬃcient graph planarity testing algo- rithms, Ph.D. Dissertation, Computer Sciences, University of Wisconsin, Madison, Wisc. (1969). [53] Tarjan R., Depth-ﬁrst 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). http://www.ebook.edu.vn 212