圖的鄰接矩陣存儲表示以及深度優先和廣度優先遍歷，鄰接矩陣
1 #include<stdio.h>
2 #include<stdlib.h>
3
4 #define OK 1
5 #define ERROR 0
6 #define MAX_VERTAX_SIZE 20
7
8 typedef char VerElemType;
9 typedef char ElemType;
10 typedef int Status;
11
12 typedef struct Graph{
13 VerElemType VertaxMatrix[MAX_VERTAX_SIZE]; //頂點數組
14 int AdjacentMatrix[MAX_VERTAX_SIZE][MAX_VERTAX_SIZE]; //鄰接矩陣
15 int VertaxNum; //頂點的個數
16 int EageNum; //邊的個數
17 }Graph;
18
19 //隊列，在圖的廣度優先遍歷中使用
20 typedef struct QueueNode{
21 ElemType data;
22 struct QueueNode* next;
23 }QueueNode, *QueueNodePtr;
24 typedef struct Queue{
25 QueueNodePtr front;
26 QueueNodePtr rear;
27 }Queue;
28
29 Status InitQueue(Queue* q){
30 (*q).front = (QueueNodePtr)malloc(sizeof(struct QueueNode));
31 (*q).rear = (*q).front;
32 (*q).rear->next = NULL;
33 return OK;
34 }
35 Status EnterQueue(Queue* q, ElemType e){
36 QueueNodePtr n;
37 n = (QueueNode*)malloc(sizeof(struct QueueNode));
38 n->data = e;
39 n->next = q->rear->next;
40 q->rear->next = n;
41 q->rear = n;
42 return OK;
43 }
44 Status DeleteQueue(Queue* q, ElemType* e){
45 QueueNodePtr p;
46 if( q->front == q->rear ){
47 printf("Empty\n");
48 return ERROR;
49 }
50 p = q->front->next;
51 *e = p->data;
52 q->front->next = p->next;
53 free(p);
54 if( p == q->rear )
55 q->rear = q->front;
56 return OK;
57 }
58 Status IsQueueEmpty(Queue q){
59 return q.front == q.rear ? OK : ERROR;
60 }
61
62 //定位某個頂點的下標
63 int LocateVertax(Graph G, VerElemType ver){ //測試1通過
64 int i;
65 for( i = 0; i < G.VertaxNum; i++ ){
66 if( G.VertaxMatrix[i] == ver )
67 return i;
68 }
69 return -1;
70 }
71 //創建無向圖
72 Status CreateUDG(Graph* G){
73 int i,j,k;
74 VerElemType x,y;
75 printf(" Create Undigraph.\n");
76 printf("Please enter the number of Vertax and Eage: \n");
77 scanf("%d %d%*c",&(*G).VertaxNum, &(G->EageNum)); //%*c吃掉回車
78
79 printf("ok, please input value of %d Vertax.\n", G->VertaxNum );
80 for( i = 0; i < G->VertaxNum; i++ ){ //初始化頂點數組
81 scanf("%c%*c", &(G->VertaxMatrix[i]));
82 }
83
84 for( i = 0; i < G->VertaxNum; i++ ) //初始化鄰接表
85 for( j = 0; j < G->VertaxNum; j++ )
86 G->AdjacentMatrix[i][j] = 0;
87 //for( i = 0; i < G->VertaxNum; i++ ){ //初始化鄰接表
88 // for( j = 0; j < G->VertaxNum; j++ )
89 // printf("%d ", G->AdjacentMatrix[i][j]);
90 // printf("\n");
91 //}
92
93 for( k = 0; k < G->EageNum; k++ ){
94 printf("ok, please input two Vertax of Eage: %d,separated by Spaces.\n", k+1 );
95 scanf("%c %c%*c", &x, &y);
96 i = LocateVertax(*G, x);
97 j = LocateVertax(*G, y);
98 G->AdjacentMatrix[i][j] = G->AdjacentMatrix[j][i] = 1;
99 }
100 return OK;
101 }
102 //打印鄰接矩陣
103 Status PrintAdjacentMatrix(Graph G){
104 int i, j;
105 printf(" Adjacent Matrix\n");
106 for( i = 0; i < G.VertaxNum; i++ ){
107 for( j = 0; j < G.VertaxNum; j++){
108 printf("%3d", G.AdjacentMatrix[i][j]);
109 }
110 printf("\n");
111 }
112 return OK;
113 }
114
115 //圖的深度優先遍歷
116 //返回v的第一個鄰接頂點，若沒有鄰接頂點，返回-1
117 int FirstAdjacentVertax(Graph G, VerElemType v){
118 int index_v = LocateVertax(G, v);
119 int i;
120 for( i = 0; i < G.VertaxNum; i++ ){
121 if( G.AdjacentMatrix[index_v][i] == 1)
122 return i;
123 }
124 return -1;
125 }
126 //w是v的鄰接點，返回v的除了w(從w開始)的下一個鄰接頂點，沒有則返回-1
127 int NextAdjacentVertax(Graph G, VerElemType v, VerElemType w){
128 int index_v = LocateVertax(G, v);
129 int index_w = LocateVertax(G, w);
130 int i;
131 for( i = index_w + 1; i < G.VertaxNum; i++ ){
132 if( G.AdjacentMatrix[index_v][i] == 1 )
133 return i;
134 }
135 return -1;
136 }
137 //DFS的遞歸思想： 訪問v，
138 // 從v的第一鄰接點開始深度優先遍歷，
139 // 然後從v的第二鄰接開始深度優先遍歷。直到沒有鄰接點
140
141 int visitedArray[MAX_VERTAX_SIZE];
142
143 void visit(VerElemType c){
144 printf("%c ", c);
145 }
146 VerElemType GetVertaxValue(Graph G, int position){
147 return G.VertaxMatrix[position];
148 }
149 Status DFS(Graph G, VerElemType v){ //Depth First Search
150 VerElemType w;
151 visit(v);
152 visitedArray[LocateVertax(G, v)] = 1; //已訪問，1
153
154 for(w = GetVertaxValue(G, FirstAdjacentVertax(G, v)); LocateVertax(G, w) != -1; w = GetVertaxValue(G, NextAdjacentVertax(G, v, w))){
155 if( visitedArray[LocateVertax(G, w)] != 1 )
156 DFS(G, w);
157 }
158 return OK;
159 }
160 Status DFSTraverse(Graph G){
161 int i;
162 for( i = 0; i < G.VertaxNum; i++ ){
163 visitedArray[i] = 0;
164 }
165 for( i = 0; i < G.VertaxNum; i++){
166 if( visitedArray[i] == 0 ){
167 DFS(G, GetVertaxValue(G, i));
168 }
169 }
170 return OK;
171 }
172 //BFS(廣度優先遍歷)：利用隊列和樹的層次遍歷相似
173 //思想： 將第一個頂點入隊，
174 // 將對中的元素出隊，如果沒有訪問過，則調用visit訪問，將其所有的鄰接頂點入隊
175 Status BFSTraverse(Graph G){
176 ElemType c;
177 Queue q;
178 InitQueue(&q);
179 int i,j;
180 for( i = 0; i < G.VertaxNum; i++ )
181 visitedArray[i] = 0;
182
183 for( i = 0; i < G.VertaxNum; i++ ){
184 if( visitedArray[i] == 0 ){
185 EnterQueue(&q, G.VertaxMatrix[i]);
186 visitedArray[i] = 1;
187 while( IsQueueEmpty(q) != OK ){
188 DeleteQueue(&q, &c); //進到隊裡的都是編輯為訪問過，這樣隊裡不會有重復的點進來
189 visit(c);
190 for( j = FirstAdjacentVertax(G, c); j != -1; j = NextAdjacentVertax(G, c, GetVertaxValue(G, j))){
191 if( visitedArray[j] == 0 ){
192 EnterQueue(&q, GetVertaxValue(G, j));
193 visitedArray[j] = 1; //進到隊裡的都是編輯為訪問過，這樣隊裡不會有重復的點進來
194 }
195 }
196 }
197 }
198 }
199
200 }
201
202 int main(){
203 Graph G;
204 CreateUDG(&G);
205 PrintAdjacentMatrix(G);
206 printf("the Result of DFS(Depth First Search) is: ");
207 DFSTraverse(G);
208 printf("\nthe REsult of BFS(Breadth First Srarch) is: ");
209 BFSTraverse(G);
210 return 0;
211 }
