数据结构算法C语言实现（二十七）--- 7.2图的遍历
一.简述
栈与队列，DFS与BFS。仅以连接表为例实现。
二.头文件
BFS要用到的头文件
1 //3_4_part1.h
2 /**
3 author:zhaoyu
4 email:zhaoyu1995.com@gmail.com
5 date:2016-6-9
6 2016-6-25修改版，针对第七章
7 note:realize my textbook <<数据结构（C语言版）>>
8 */
9 //Page 64
10 #include <cstdio>
11 #include "head.h"
12 #define QElemType int
13 //----循环队列：队列的顺序存储结构----
14 #define MAXQSIZE 10 //最大队列长度
15 typedef struct{
16 QElemType *base;
17 int front;
18 int rear;
19 }SqQueue;
20 //----循环队列的基本操作说明及实现----
21 Status InitQueue(SqQueue &Q)
22 {
23 //构造一个空队列 Q
24 Q.base = (QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
25 if (!Q.base)
26 {
27 exit(OVERFLOW);
28 }
29 Q.front = Q.rear = 0;
30 return OK;
31 }
32 int QueueLength(SqQueue Q)
33 {
34 //返回 Q 的元素个数，即队列的长度
35 return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
36 }
37 Status EnQueue(SqQueue &Q, QElemType e)
38 {
39 //插入元素 e 为 Q 的新的队尾元素
40 if ((Q.rear+1)%MAXQSIZE == Q.front)
41 {
42 return ERROR;//队列满
43 }
44 Q.base[Q.rear] = e;
45 Q.rear = (Q.rear+1)%MAXQSIZE;
46 return OK;
47 }
48 Status DeQueue(SqQueue &Q, QElemType &e)
49 {
50 //若队列不空，则删除 Q 的队列头元素，用 e 返回其值，
51 //并返回 OK，否则返回 ERROR
52 if (Q.front == Q.rear)
53 {
54 return ERROR;
55 }
56 e = Q.base[Q.front];
57 Q.front = (Q.front+1)%MAXQSIZE;
58 return OK;
59 }
60 Status QueueEmpty(SqQueue Q)
61 {
62 if (Q.front == Q.rear)
63 {
64 return TRUE;
65 }
66 else
67 {
68 return FALSE;
69 }
70 }
71 void PrintQueue(SqQueue Q)
72 {
73 int cnt = Q.front;
74 if (Q.front == Q.rear)
75 {
76 printf("void\n");
77 return;
78 }
79 while ((cnt+1)%MAXQSIZE != Q.rear)
80 {
81 //printf("%d\t%d\n",Q.base[cnt++], cnt);输出好奇怪
82 printf("%d\t", Q.base[cnt]);
83 cnt++;
84 }
85 printf("%d\n", Q.base[cnt]);
86 }
3_4_part2.h
存储结构用到的头文件
1 //filename：7_2_part2.h
2 //date:2016-6-20
3 //author:zhaoyu
4 //note:
5 //----图的邻接表存储表示----
6 #include "head.h"
7 #include <cstdio>
8 #include <cstdlib>
9 #include <cstring>
10 #define MAX_VERTEX_NUM 20
11 #define VertexType int
12 #define InfoType char
13 #define Graph ALGraph
14 typedef struct ArcNode{
15 int adjvex;//该弧所指向的顶点位置
16 struct ArcNode *nextarc;//指向下一条弧的指针
17 InfoType *info;//该弧相关信息的指针
18 }ArcNode;
19 typedef struct VNode{
20 VertexType data;//顶点信息
21 ArcNode *firstarc;//指向第一条依附该顶点的弧的指针
22 }VNode, AdjList[MAX_VERTEX_NUM];
23 typedef struct {
24 AdjList vertices;
25 int vexnum, arcnum;
26 int kind;
27 }ALGraph;
28
29 void AddNode(ALGraph &G, int v, int w)
30 {
31 G.vertices[v].data = v;
32 if (NULL == G.vertices[v].firstarc)
33 {
34 G.vertices[v].firstarc = (ArcNode *)malloc(sizeof(ArcNode));
35 G.vertices[v].firstarc->nextarc = NULL;
36 G.vertices[v].firstarc->adjvex = w;
37 G.vertices[v].firstarc->info = NULL;
38 return;
39 }
40 ArcNode *temp = G.vertices[v].firstarc;
41 while (temp->nextarc)
42 {
43 temp = temp->nextarc;
44 }
45 ArcNode *move = (ArcNode *)malloc(sizeof(ArcNode));
46 move->nextarc = NULL;
47 move->adjvex = w;
48 move->info = NULL;
49 temp->nextarc = move;
50 }
51 void CreateALGraph(ALGraph &G)
52 {
53 for (int i = 0; i < MAX_VERTEX_NUM; i++)
54 {
55 G.vertices[i].firstarc = NULL;
56 }
57 printf("input vexnum and arcnum(1~MAX):\n");
58 scanf("%d%d", &G.vexnum, &G.arcnum);
59 int v, w;
60 for (int i = 0; i < G.arcnum; i++)
61 {
62 scanf("%d%d", &v, &w);
63 AddNode(G, v, w);
64 AddNode(G, w, v);
65 }
66 }
67 Status Visit(int v)
68 {
69 printf("%d->", v);
70 }
71 int FirstAdjVex(ALGraph G, int v)
72 {
73 if (NULL != G.vertices[v].firstarc)
74 {
75 return G.vertices[v].firstarc->adjvex;
76 }
77 else
78 {
79 return -1;
80 }
81 }
82 int NextAdjVex(Graph G, int v, int w)
83 {
84 if (NULL != G.vertices[v].firstarc)
85 {
86 ArcNode *temp = G.vertices[v].firstarc;
87 while (temp != NULL)
88 {
89 if (temp->adjvex == w)
90 {
91 if (NULL != temp->nextarc)
92 {
93 return temp->nextarc->adjvex;
94 }
95 else
96 {
97 return -1;
98 }
99 }
100 temp = temp->nextarc;
101 }
102 return -1;
103 }
104 else
105 {
106 return -1;
107 }
108 }
7_2_part2.h
其他
1 //filename：7_3.h
2 //date:2016-6-25
3 //author:
4 //note:仅以邻接表为例
5 #include "7_2_part2.h"
6 #include "3_4_part2.h"
7 #define Boolean int
8 #define MAX MAX_VERTEX_NUM
9 Boolean visited[MAX];//访问标志数组
10 Status (* VisitFunc)(int v);//函数变量
11 /**
12 algorithm 7.5
13 */
14 void DFS(Graph G, int v)
15 {
16 visited[v] = TRUE;
17 VisitFunc(v);//访问第 v 个结点
18 for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
19 {
20 if (!visited[w])
21 {
22 DFS(G, w);//对 v 的尚未访问的邻接顶点，递归调用 DFS
23 }
24 }
25 }
26 /**
27 algorithm 7.4
28 */
29 void DFSTraverse(Graph G, Status (* Visit)(int v))
30 {//对图 G 做深度游优先遍历
31 VisitFunc = Visit;//使用全局变量VisitFunc,使DFS不必设函数指针参数
32 for (int v = 0; v < G.vexnum; ++v)
33 {
34 visited[v] = FALSE;
35 }
36 for (int v = 0; v < G.vexnum; ++v)
37 {
38 if (!visited[v])
39 {
40 DFS(G, v);
41 }
42 }
43 printf("\b\b \n");
44 }
45
46 void BFSTraverse(Graph G, Status (* Visit)(int v))
47 {//按广度优先非递归遍历图 G，使用辅助队列 Q 和访问标志数组 visited
48 for (int v = 0; v < G.vexnum; ++v)
49 {
50 visited[v] = FALSE;
51 }
52 SqQueue Q;
53 InitQueue(Q);//置空的辅助队列 Q
54 for (int v = 0; v < G.vexnum; ++v)
55 {
56 if (!visited[v])//v 尚未访问
57 {
58 visited[v] = TRUE;
59 Visit(v);
60 EnQueue(Q, v);// v 入队列
61 while (!QueueEmpty(Q))
62 {
63 int u = -1;
64 DeQueue(Q, u);//队头元素出队并置为 u
65 for (int w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
66 {//w 为 u 尚未访问的邻居节点
67 if (!visited[w])
68 {
69 visited[w] = TRUE;
70 Visit(w);
71 EnQueue(Q, w);
72 }
73 }
74 }
75 }
76 }
77 printf("\b\b \n");
78 }
7_3.h
三.CPP文件
1 #include "7_3.h"
2 int main(int argc, char const *argv[])
3 {
4 ALGraph G;
5 CreateALGraph(G);
6 printf("DFS Traverse\t");
7 DFSTraverse(G, Visit);
8 printf("BFS Traverse\t");
9 BFSTraverse(G, Visit);
10 return 0;
11 }
7_3.cpp
四.测试
以书本上的图为例
