观察下面两个无向图:
1.PNG
这两个图其实是一样的, 只是画法不同罢了. 第一张图更有立体感, 第二张图更有层次感, 并且把 A 点置为顶点(事实上图的任何一点都可以做为顶点).
一, 用数组来存放顶点
- vexs[0] = 'A'
- vexs[1] = 'B'
- vexs[2] = 'C'
- vexs[3] = 'D'
- vexs[4] = 'E'
- vexs[5] = 'F'
- vexs[6] = 'G'
- vexs[7] = 'H'
- vexs[8] = 'I'
二, 用邻接矩阵来表示边
2.PNG
上面这个矩阵中, 0 表示每个顶点没有到达自己的路径. 1 表示两个顶点之间有路径, 无穷大表示两个顶点之间没有路径.
假如按照程序计数习惯, 行或列都从 0 数起.
第 0 行第 0 列为 0, 表示 A 到它本身之间没有路径(这是人为规定的, 因为 A 到它自身不需要路径).
第 0 行第 1 列为 1, 表示顶点 A 和 B 之间有路径.
第 0 行第 5 列为 1, 表示顶点 A 和顶点 F 之间有路径.
第 0 行其他列为无穷大, 表示 A 到其它点之间没有路径.
......
因为是无向图, 邻接矩阵必然有两个特点:
1 对角线 (左上角到右下角) 上的元素值全为 0. 表示每个点到它自身没有 (或不需要) 路径.
2 其它的元素关于对角线对称.
上面的邻接矩阵, 在编程时可以用二维数组来实现:
- arc[0][1] = arc[1][0] = 1;
- arc[0][5] = arc[5][0] =1;
- arc[1][2] = arc[2][1] = 1;
- arc[1][6] = arc[6][1] = 1;
- arc[1][8] = arc[8][1] = 1;
- arc[2][3] = arc[3][2] = 1;
- arc[2][8] = arc[8][2] = 1;
- arc[3][4] = arc[4][3] = 1;
- arc[3][6] = arc[6][3] = 1;
- arc[3][7] = arc[7][3] = 1;
- arc[3][8] = arc[8][3] = 1;
- arc[4][5] = arc[5][4] = 1;
- arc[4][7] = arc[7][4] = 1;
- arc[5][6] = arc[6][5] = 1;
- arc[6][7] = arc[7][6] = 1;
三, 深度优先遍历
可以使用递归的方法进行深度遍历.
观察图 (1) 中的左图, 假如从顶点 A 开始, 从 A 找到相邻的 B, 从 B 找到相邻的 C, 从 C 找到相邻的 D, 从 D 找到相邻的 E, 从 E 找到邻接点 F, 从 F 找到相邻的 G, 从 G 找到相邻的 H.
H 有三个相邻的点 D,E,G. 这三个点都已经遍历过了. 所以回退到上一顶点 G.
G 有三个相邻的顶点 D,F,H. 这三个点也都已经遍历过了. 回退到上一顶点 F.
F 有两个相邻的顶点 E,G, 都已经遍历过了. 回退到上个顶点 E.
E 点有两个相邻的顶点 D,F, 都已经遍历过了. 回退到上个顶点 D.
D 点有五个相邻的顶点 C,E,H,G,I. 除了 I 外, 其余四个顶点已经遍历过了. 所以这一次遍历 I.
I 遍历完之后回到 D 点, 从 D 点回到 C 点.
C 点有三个相邻的顶点 B,D,I, 都已经遍历过了, 回退到 B 点.
B 点有四个相邻的顶点 A,C,G,I, 都已经遍历过了, 回退到 A 点.
A 点有两个相邻的顶点 B,F, 都已经遍历过了. 递归都此结束.
得到深度优先遍历的顺序为: A B C D E F G H I
四, 广度优先遍历
广度优先遍历需要借助于另外的数据结构队列. 当把图中的顶点放到队列中时, 表示这个顶点被遍历了(可以把顶点的值打印出来).
用图 1 中的右图来分析广度优先遍历更方便, 因为右图的层次结构更明显.
3.PNG
起初, 把点 A 放入队列中, A 被遍历. 如上图中的 (1) 所示.
接着把队首元素 A 出队, 把 A 的下一层的顶点 B 和 F 移进队列, B 和 F 被遍历. 如上图中的 (2) 所示.
队首元素 B 出队, B 的下一层顶点 C,G,I 相继入队, C,G 和 I 被遍历. 如上图中的 (3) 所示.
队首元素 F 出队, F 的下一层顶点 E 入队, E 被遍历. 如上图中的 (5) 所示.
队首元素 C 出队, C 的下一层顶点 D 入队, D 被遍历. 如上图中的 (6) 所示.
队首元素 G 出队, G 的下一层有两个顶点: D 和 H.D 已在队列里, H 入队, H 被遍历. 如上图中的 (4) 所示.
队首元素 I 出队, I 的下一层顶点 D 已在队列里, 没有新顶点入队. 如上图中的 (7) 所示.
队首元素 E 出队, E 的下一层顶点 D 和 H 都已在队列里, 没有新顶点入队. 如上图中的 (8) 所示.
队首元素 D 出队, D 没有下一层顶点, 所以没有新顶点入队. 如上图中的 (9) 所示.
队首元素 H 出队, H 没有下一层顶点, 所以没有新顶点入队. 此时队列为空, 遍历结束.
最终, 广度优先遍历的顺序即入队列 (或出队列) 的顺序: A B F C G I E D H
五, 完整代码
- #include "stdio.h"
- #define OK 1
- #define ERROR 0
- #define TRUE 1
- #define FALSE 0
- #define MAXSIZE 9 /* 存储空间初始分配量 */
- #define MAXEDGE 15
- #define MAXVEX 9
- #define INFINITY 65535
- typedef int Status; /* Status 是函数的类型, 其值是函数结果状态代码, 如 OK 等 */
- typedef int Boolean; /* Boolean 是布尔类型, 其值是 TRUE 或 FALSE */
- typedef char VertexType; /* 顶点类型应由用户定义 */
- typedef int EdgeType; /* 边上的权值类型应由用户定义 */
- typedef struct
- {
- VertexType vexs[MAXVEX]; /* 顶点表 */
- EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵, 可看作边表 */
- int numVertexes, numEdges; /* 图中当前的顶点数和边数 */
- }MGraph;
- /* 用到的队列结构与函数 ********************************** */
- /* 循环队列的顺序存储结构 */
- typedef struct
- {
- int data[MAXSIZE];
- int front; /* 头位置标识, 相当于头指针 */
- int rear; /* 尾位置标识, 相当于尾指针. 若队列不为空, 指向队列尾元素的下一个位置 */
- }Queue;
- /* 初始化一个空队列 Q */
- Status InitQueue(Queue *Q)
- {
- Q->front=0;
- Q->rear=0;
- return OK;
- }
- /* 若队列 Q 为空队列, 则返回 TRUE, 否则返回 FALSE */
- Status QueueEmpty(Queue Q)
- {
- if(Q.front==Q.rear) /* 队列空的标志 */
- return TRUE;
- else
- return FALSE;
- }
- /* 若队列未满, 则插入元素 e 为 Q 新的队尾元素 */
- Status EnQueue(Queue *Q,int e)
- {
- if ((Q->rear+1)%MAXSIZE == Q->front) /* 队列满的判断 */
- return ERROR;
- Q->data[Q->rear]=e; /* 将元素 e 赋值给队尾 */
- Q->rear=(Q->rear+1)%MAXSIZE;/* rear 指针向后移一位置, 若到最后则转到数组头部 */
- return OK;
- }
- /* 若队列不为空, 则删除 Q 中队头元素, 用 e 返回其值 */
- Status DeQueue(Queue *Q,int *e)
- {
- if (Q->front == Q->rear) /* 队列空的判断 */
- return ERROR;
- *e=Q->data[Q->front]; /* 将队头元素赋值给 e */
- Q->front=(Q->front+1)%MAXSIZE; /* front 指针向后移一位置, 若到最后则转到数组头部 */
- return OK;
- }
- void CreateMGraph(MGraph *G)
- {
- int i, j;
- G->numEdges=15;
- G->numVertexes=9;
- /* 读入顶点信息, 建立顶点表 */
- G->vexs[0]='A';
- G->vexs[1]='B';
- G->vexs[2]='C';
- G->vexs[3]='D';
- G->vexs[4]='E';
- G->vexs[5]='F';
- G->vexs[6]='G';
- G->vexs[7]='H';
- G->vexs[8]='I';
- for (i = 0; i <G->numVertexes; i++)/* 初始化图 */
- {
- for ( j = 0; j <G->numVertexes; j++)
- {
- G->arc[i][j]=0;
- }
- }
- G->arc[0][1]=1;
- G->arc[0][5]=1;
- G->arc[1][2]=1;
- G->arc[1][6]=1;
- G->arc[1][8]=1;
- G->arc[2][3]=1;
- G->arc[2][8]=1;
- G->arc[3][4]=1;
- G->arc[3][6]=1;
- G->arc[3][7]=1;
- G->arc[3][8]=1;
- G->arc[4][5]=1;
- G->arc[4][7]=1;
- G->arc[5][6]=1;
- G->arc[6][7]=1;
- for(i = 0; i <G->numVertexes; i++)
- {
- for(j = i; j <G->numVertexes; j++)
- {
- G->arc[j][i] =G->arc[i][j];
- }
- }
- }
- Boolean visited[MAXVEX]; /* 访问标志的数组 */
- /* 邻接矩阵的深度优先递归算法 */
- void DFS(MGraph G, int i)
- {
- int j;
- visited[i] = TRUE;
- printf("%c", G.vexs[i]);/* 打印顶点, 也可以其它操作 */
- for(j = 0; j < G.numVertexes; j++)
- if(G.arc[i][j] == 1 && !visited[j])
- DFS(G, j);/* 对未访问的邻接顶点递归调用 */
- }
- /* 邻接矩阵的深度遍历算法 */
- void DFSTraverse(MGraph G)
- {
- int i;
- for(i = 0; i < G.numVertexes; i++)
- visited[i] = FALSE; /* 初始所有顶点状态都是未访问过状态 */
- for(i = 0; i < G.numVertexes; i++)
- if(!visited[i]) /* 对未访问过的顶点调用 DFS, 若是连通图, 只会执行一次 */
- DFS(G, i);
- }
- /* 邻接矩阵的广度遍历算法 */
- void BFSTraverse(MGraph G)
- {
- int i, j;
- Queue Q;
- for(i = 0; i < G.numVertexes; i++)
- visited[i] = FALSE;
- InitQueue(&Q); /* 初始化一辅助用的队列 */
- for(i = 0; i < G.numVertexes; i++) /* 对每一个顶点做循环 */
- {
- if (!visited[i]) /* 若是未访问过就处理 */
- {
- visited[i]=TRUE; /* 设置当前顶点访问过 */
- printf("%c", G.vexs[i]);/* 打印顶点, 也可以其它操作 */
- EnQueue(&Q,i); /* 将此顶点入队列 */
- while(!QueueEmpty(Q)) /* 若当前队列不为空 */
- {
- DeQueue(&Q,&i); /* 将队对元素出队列, 赋值给 i */
- for(j=0;j<G.numVertexes;j++)
- {
- /* 判断其它顶点若与当前顶点存在边且未访问过 */
- if(G.arc[i][j] == 1 && !visited[j])
- {
- visited[j]=TRUE; /* 将找到的此顶点标记为已访问 */
- printf("%c", G.vexs[j]); /* 打印顶点 */
- EnQueue(&Q,j); /* 将找到的此顶点入队列 */
- }
- }
- }
- }
- }
- }
- int main(void)
- {
- MGraph G;
- CreateMGraph(&G);
- printf("\n 深度遍历:");
- DFSTraverse(G);
- printf("\n 广度遍历:");
- BFSTraverse(G);
- return 0;
- }
运行结果:
深度遍历: A B C D E F G H I
广度遍历: A B F C G I E D H
来源: http://www.jianshu.com/p/ded75497a056