# 邻接图的深度广度优先遍历

## 数据结构

typedef struct edgeNode{
int num;
int weight;
struct edgeNode * next;
}edgeNode;

typedef struct vertexNode{
char data;
edgeNode * firstNode;
}vertexNode,List[NUM];

typedef struct Graph{
List list;
int numver,numedges;
}Graph;

## 深度优先遍历

void DFS(Graph *g,int i){
edgeNode *p = (edgeNode *)malloc(sizeof(edgeNode));
visited[i] = 1;
printf("%c ",g->list[i].data);
p = g->list[i].firstNode;
while(p){
if(!visited[p->num])
DFS(g,p->num);
p = p->next;
}
}
void DFSTraverse(Graph *g){
int i;
for(i=0;i<g->numver;i++)
visited[i] = 0;
for(i=0;i<g->numver;i++)
if(!visited[i])
DFS(g,i);
}

## 广度优先遍历

void BFSTraverse(Graph *g){
int i;
edgeNode *p;
Queue *q = (Queue *)malloc(sizeof(Queue));

for(i=0;i<g->numver;i++)
visited[i] = 0;
initQueue(q,0);
for(i=0;i<g->numver;i++){
if(!visited[i]){
visited[i] = 1;
printf("%c ",g->list[i].data);
inQueue(q,i);
while(getLength(q)){
int *tar = (int *)malloc(sizeof(int));
outQueue(q,tar);
p = g->list[*tar].firstNode;
while(p){
if(!visited[p->num]){
visited[p->num] = 1;
printf("%c ",g->list[p->num].data);
inQueue(q,p->num);
}
p = p->next;
}

}
}
}

}

## 示例代码

  1 #include <stdio.h>
2 #include <stdlib.h>
3 #define NUM 5
4 #define MAXSIZE NUM
5
6 typedef struct edgeNode{
7     int num;
8     int weight;
9     struct edgeNode * next;
10 }edgeNode;
11
12 typedef struct vertexNode{
13     char data;
14     edgeNode * firstNode;
15 }vertexNode,List[NUM];
16
17 typedef struct Graph{
18     List list;
19     int numver,numedges;
20 }Graph;
21
22 typedef struct Queue{
23     int data[NUM];
24     int front;
25     int rear;
26 }Queue;
27
28 void initQueue(Queue *q,int n);
29 void showQueue(Queue *q);
30 int getLength(Queue *q);
31 int inQueue(Queue *q,int num);
32 int outQueue(Queue *q,int *tar);
33
34 void createGraph(Graph *g);
35 void showGraph(Graph *g);
36 void add(Graph *g,int a,int b,int c);
37 void DFS(Graph *g,int i);
38 void DFSTraverse(Graph *g);
39 void BFSTraverse(Graph *g);
40
41 int visited[NUM];
42
43 int main()
44 {
45     Graph * g = (Graph *)malloc(sizeof(Graph));
46     createGraph(g);
47     showGraph(g);
48     printf("\n");
49     DFSTraverse(g);
50     printf("\n");
51     BFSTraverse(g);
52     return 0;
53 }
54 void add(Graph *g,int a,int b,int c){
55     edgeNode *e;
56
57     e = (edgeNode *)malloc(sizeof(edgeNode));
58     e->next = g->list[a].firstNode;
59     g->list[a].firstNode = e;
60     e->num = b;
61     e->weight = c;
62
63     e = (edgeNode *)malloc(sizeof(edgeNode));
64     e->next = g->list[b].firstNode;
65     g->list[b].firstNode = e;
66     e->num = a;
67     e->weight = c;
68
69     g->numedges++;
70
71
72 }
73
74 void createGraph(Graph *g){
75     int i;
76     for(i=0;i<NUM;i++){
77         g->list[i].data = 65+i;
78         g->list[i].firstNode = NULL;
79     }
80     g->numver = NUM;
81     g->numedges = 0;
82     //添加顶点0的边
87
90
92
94 }
95 void showGraph(Graph *g){
96     int i;
97     for(i=0;i<g->numver;i++){
98         printf("g[%d] ",i);
99         edgeNode *p = (edgeNode *)malloc(sizeof(edgeNode));
100         p = g->list[i].firstNode;
101         while(p){
102             printf("->%d(%d)",p->num,p->weight);
103             p = p->next;
104         }
105         printf("->null\n");
106     }
107 }
108
109 void DFS(Graph *g,int i){
110     edgeNode *p = (edgeNode *)malloc(sizeof(edgeNode));
111     visited[i] = 1;
112     printf("%c ",g->list[i].data);
113     p = g->list[i].firstNode;
114     while(p){
115         if(!visited[p->num])
116             DFS(g,p->num);
117         p = p->next;
118     }
119 }
120 void DFSTraverse(Graph *g){
121     int i;
122     for(i=0;i<g->numver;i++)
123         visited[i] = 0;
124     for(i=0;i<g->numver;i++)
125         if(!visited[i])
126             DFS(g,i);
127 }
128 void BFSTraverse(Graph *g){
129     int i;
130     edgeNode *p;
131     Queue *q = (Queue *)malloc(sizeof(Queue));
132
133     for(i=0;i<g->numver;i++)
134         visited[i] = 0;
135     initQueue(q,0);
136     for(i=0;i<g->numver;i++){
137         if(!visited[i]){
138             visited[i] = 1;
139             printf("%c ",g->list[i].data);
140             inQueue(q,i);
141             while(getLength(q)){
142                 int *tar = (int *)malloc(sizeof(int));
143                 outQueue(q,tar);
144                 p = g->list[*tar].firstNode;
145                 while(p){
146                     if(!visited[p->num]){
147                         visited[p->num] = 1;
148                         printf("%c ",g->list[p->num].data);
149                         inQueue(q,p->num);
150                     }
151                     p = p->next;
152                 }
153
154             }
155         }
156     }
157
158 }
159
160 void initQueue(Queue *q,int n){
161     int i;
162     q->front=0;
163     q->rear =0;
164     for(i=0;i<n;i++){
165         q->data[q->rear]=2*i+1;
166         q->rear++;
167     }
168 }
169 void showQueue(Queue *q){
170     int i;
171     int len=getLength(q);
172     printf("front-");
173     for(i=0;i<len;i++){
174         if(q->front+i<MAXSIZE)
175             printf("%d-",q->data[q->front+i]);
176         else
177             printf("%d-",q->data[q->front+i-MAXSIZE]);
178     }
179     printf("rear\n");
180 }
181 int getLength(Queue *q){
182     return (q->rear-q->front+MAXSIZE)%MAXSIZE;
183 }
184 int inQueue(Queue *q,int num){
185     if((q->rear+1)%MAXSIZE == q->front)
186         return 0;
187     q->data[q->rear] = num;
188     q->rear = (q->rear+1)%MAXSIZE;
189     return 1;
190 }
191 int outQueue(Queue *q,int *tar){
192     if(q->front == q->rear)
193         return 0;
194     *tar = q->data[q->front];
195     q->front = (q->front+1)%MAXSIZE;
196     return 1;
197 }

## 运行结果

|
1月前
|

27 0
|
11月前
|

92 0
|
2月前
|
NoSQL 容器 消息中间件

26 0
|

121 1
|
12月前
|

133 0
|
12月前
|

55 0
065.图的深度优先遍利
065.图的深度优先遍利
62 0
066.图的广度优先遍利
066.图的广度优先遍利
75 0
|

C++实现图 - 03 最小生成树

196 0
|

77 0