1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <stdbool.h>
4 #include <string.h>
5 #include <dos.h>
6
7 #define MaxVertexNum 10
8
9 typedef int ElementType;
10 typedef int Position;
11
12 typedef struct QNode {
13 ElementType *Data; /* 存储元素的数组 */
14 Position Front, Rear; /* 队列的头、尾指针 */
15 int MaxSize; /* 队列最大容量 */
16 }QNode, *Queue;
17
18
19 typedef struct ENode
20 {
21 int ivex; //该边指向的顶点位置
22 struct ENode * next;
23 }ENode, *PENode;
24
25 typedef int VertexType;
26
27 typedef struct VNode
28 {
29 VertexType data;
30 ENode * first_edge;
31 }VNode;
32
33 typedef struct LGraph
34 {
35 int vexnum; //图的顶点数目
36 int edgnum; //图的边的数目
37 VNode * vexs; //存放顶点的数组
38 }LGraph;
39
40 bool TAG; //用于输出格式
41 bool visited[MaxVertexNum];
42
43 LGraph * LGraph_new();
44 void LGraph_destroy(LGraph * G);
45 void LGraph_insert(ENode ** head, int ivex);
46 void ResetVisit();
47 void DFS(LGraph * G, int vex);
48 void BFS(LGraph * G, int vex);
49 void ListComponents(LGraph * G, void (*func)(LGraph * G, int vex));
50
51 //优先队列的基本操作
52 Queue CreateQueue( int MaxSize );
53 bool IsFull( Queue Q );
54 bool AddQ( Queue Q, ElementType X );
55 bool IsEmpty( Queue Q );
56 ElementType DeleteQ( Queue Q );
57
58 int main()
59 {
60 LGraph * G = LGraph_new();
61 ResetVisit();
62 ListComponents(G, DFS);
63 ResetVisit();
64 ListComponents(G, BFS);
65 system("pause");
66 return 0;
67 }
68
69 void ListComponents(LGraph * G, void (*func)(LGraph * G, int vex))
70 {
71 int i;
72 for ( i = 0; i < G->vexnum; ++i )
73 {
74 if (visited[i] == false)
75 {
76 (*func)(G, i);
77 printf("}\n");
78 TAG = false;
79 }
80 }
81 }
82
83 LGraph * LGraph_new()
84 {
85
86 LGraph * G = (LGraph *)malloc(sizeof(LGraph));
87 scanf("%d %d", &G->vexnum, &G->edgnum);
88 G->vexs = (VNode *)malloc(G->vexnum * sizeof(VNode));
89 int i, v1, v2;
90 for ( i = 0; i < G->vexnum; ++i )
91 {
92 G->vexs[i].data = i;
93 G->vexs[i].first_edge = NULL;
94 }
95 for ( i = 0; i < G->edgnum; ++i )
96 {
97 scanf("%d %d", &v1, &v2);
98 //由于顶点信息就是顶点坐标
99 LGraph_insert(&G->vexs[v1].first_edge, v2);
100 LGraph_insert(&G->vexs[v2].first_edge, v1);
101 }
102 return G;
103 }
104
105 void ResetVisit()
106 {
107 TAG = false;
108 memset(visited, false, sizeof(visited));
109 }
110
111 void LGraph_insert(ENode ** head, int ivex)
112 {
113 ENode *pnew, *p1, *p2;
114 pnew = (ENode *)malloc(sizeof(ENode));
115 pnew->ivex = i 
