圖的鄰接矩陣存儲表示 圖的深度優先遍歷 圖的廣度優先遍歷

  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 }