邻接图的深度广度优先遍历
邻接图的深度广度优先遍历
用户1154259
发布于 2018-01-17 19:05:22
发布于 2018-01-17 19:05:22
邻接图的优点就是，现用现申请，空间存储很灵活，并且需要的空间也很小。我们在做复杂网络时，通常也是用这种方法。缺点是不适合并行化，因为cuda只支持连续地址空间的拷贝。
数据结构
主要包括，边节点和顶点节点
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的边
83 add(g,0,1,0);
84 add(g,0,2,0);
85 add(g,0,3,0);
86 add(g,0,4,0);
87
88 add(g,1,3,0);
89 add(g,1,4,0);
90
91 add(g,2,4,0);
92
93 add(g,3,4,0);
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 }运行结果
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014-02-05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录