在之前我们描述了图的存储，今天我们来说一下图的遍历的操作
对图的遍历操作，我会用邻接矩阵和邻接表两种方式分别操作图的广度优先遍历和图的深度优先遍历。
首先，我们先来看比较好写的深度优先遍历。
图1.png
图2.png
上面两种图是一个图和对图的遍历操作的示意图，其中图2的绿色表示遍历节点的顺序，黄色的表示与上一个节点连接的其他节点。
邻接矩阵的深度优先遍历
先来说一下思路：
将图的顶点和边信息输入到图结构中;
创建一个visited 数组,用来标识顶点是否已经被遍历过.
初始化visited 数组,将数组中元素置为FALSE
选择顶点开始遍历.(注意非连通图的情况)
进入递归; 打印i 对应的顶点信息. 并将该顶点标识为已遍历.
循环遍历边表,判断当前arc[i][j] 是否等于1,并且当前该顶点没有被遍历过,则继续递归 DFS;
思路的核心就是利用一个数组，记录标示顶点是否有被遍历过，然后利用递归的思想，将符合条件的节点值打印出来
邻接矩阵的结构体的设置
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535
typedef struct {
VertexType vexs[MAXVEX];//顶点表
EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵，可看作边表
int numVertexs,numEdges;//图中当前的顶点数和边数
}MGraph;
构建一个邻接矩阵表，这边不再手动输入，怕手输入错误，省去一些麻烦
//构建一个邻接矩阵
void CreateMGraph(MGraph *G){
int i,j;
//1、确定图的顶点数以及边数
G->numEdges = 15;
G->numVertexs = 9;
//2、读入顶点信息，建立顶点表
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';
//3、初始化图中的边表
for (i = 0; i<G->numVertexs; i++) {
for (j = 0; j<G->numVertexs; j++) {
G->arc[i][j] = 0;
}
}
//4、添加连接信息
G->arc[0][1]=1;
G->arc[0][5]=1;
G->arc[1][2]=1;
G->arc[1][8]=1;
G->arc[1][6]=1;
G->arc[2][3]=1;
G->arc[2][8]=1;
G->arc[3][4]=1;
G->arc[3][7]=1;
G->arc[3][6]=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;
//5、无向图是对称矩阵，构成对称
for (i = 0; i<G->numVertexs; i++) {
for (j = 0; j<G->numVertexs; j++) {
G->arc[i][j] = G->arc[j][i];
}
}
}
遍历操作
//遍历
Boolean visited[MAXVEX];//访问标志的数组
//1. 标识顶点是否被标记过;
//2. 选择从某一个顶点开始(注意:非连通图的情况)
//3. 进入递归,打印i点信息,标识; 边表
//4. [i][j] 是否等于1,没有变遍历过visted
void DFS(MGraph G,int i){
visited[i] = TRUE;
printf("%c ",G.vexs[i]);
for (int j = 0; j<G.numVertexs; j++) {
if(G.arc[i][j] == 1&& !visited[j]){
DFS(G, j);
}
}
}
void DFSDisplay(MGraph G){
for (int i = 0; i<G.numVertexs; i++) {
visited[i] =FALSE;
}
for (int i = 0; i<G.numVertexs; i++) {
if(!visited[i])
DFS(G, i);
}
}
打印结果:
int main(int argc, const char * argv[]) {
// insert code here...
printf("邻接矩阵的深度优先遍历!\n");
MGraph G;
CreateMGraph(&G);
DFSDisplay(G);
printf("\n");
return 0;
}
输出结果
邻接矩阵的深度优先遍历!
A B C D E F G H I
Program ended with exit code: 0
邻接表的深度优先遍历
截屏2020-04-30 下午4.50.05.png
设计思路：
利用邻接矩阵将信息存储到邻接表中
创建一个visited 数组,用来标识顶点是否已经被遍历过.
初始化visited 数组,将数组中元素置为FALSE
选择顶点开始遍历.(注意非连通图的情况)
进入递归; 打印i 对应的顶点信息. 并将该顶点标识为已遍历.
循环遍历边表,判断当前顶点 是否等于1,并且当前该顶点没有被遍历过,则继续递归 DFS;
邻接表的深度优先遍历比邻接矩阵的深度优先遍历复杂很多
我这边也是为了避免手动输入，将邻接矩阵转化为邻接表。
邻接表结构是利用数组记录每个节点所连接的节点的链表，结构比较复杂，具体请看代码
#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 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 EdgeNode{
int adjvex; //邻接点域，存储该顶点对应下标
int weight; //用于存储权值，对于非网图可以不需要
struct EdgeNode *next; //链域，指向下一个邻接点
}EdgeNode;
//顶点表节点
typedef struct VertexNode{
int in;//顶点入对
char data; //顶点域，存储顶点信息
EdgeNode *firstedge;//边表头指针
}VertexNode,AdjList[MAXVEX];
typedef struct {
AdjList adjList;
int numVertexes,numEdges;//图中当前顶点数和边数
}graphAdjList,*GraphAdjList;
构建邻接矩阵和之前的邻接矩阵的构造一摸一样，这边就不重复写了
将邻接矩阵转化为邻接表
//利用邻接矩阵构建邻接表
void CreateALGraph(MGraph G,GraphAdjList *L){
//1、创建邻接表，并且设计邻接表的顶点数以及弧数
*L = (GraphAdjList)malloc(sizeof(graphAdjList));
(*L)->numVertexes = G.numVertexes;
(*L)->numEdges = G.numEdges;
//2、从邻接矩阵中将顶点信息输入
for (int i = 0; i<G.numVertexes; i++) {
//顶点入度为0
(*L)->adjList[i].in = 0;
//顶点信息
(*L)->adjList[i].data = G.vexs[i];
//顶点边表置空
(*L)->adjList[i].firstedge = NULL;
}
//3、建立边表
EdgeNode *e;
for (int i = 0; i<G.numVertexes; i++) {
for (int j = 0; j<G.numVertexes; j++) {
if(G.arc[i][j] == 1){
//创建边表中的邻近节点i->j
e = (EdgeNode *)malloc(sizeof(EdgeNode));
//邻接序号为j
e->adjvex = j;
//将当前节点指向adjList[i]的顶点边表上
e->next = (*L)->adjList[i].firstedge;
(*L)->adjList[i].firstedge = e;
//顶点j上的入度++
(*L)->adjList[j].in++;
}
}
}
}
邻接表的深度遍历操作,和之前的邻接矩阵的遍历操作基本上一摸一样，
Boolean visited[MAXSIZE];//访问标志的数组
//邻接表的深度优先递归算法
void DFS(GraphAdjList G,int i){
EdgeNode *p;
visited[i] = TRUE;
//打印顶点
printf("%c ",G->adjList[i].data);
p = G->adjList[i].firstedge;
while (p) {
if(!visited[p->adjvex]){
DFS(G, p->adjvex);
}
p = p->next;
}
}
//邻接表的深度遍历操作
void DFSDisplay(GraphAdjList G){
//1、将访问记录数组默认设置为false
for (int i = 0; i<G->numVertexes; i++) {
visited[i] = FALSE;
}
for (int i = 0; i<G->numVertexes; i++) {
if(!visited[i])
DFS(G, i);
}
}
打印结果
int main(int argc, const char * argv[]) {
// insert code here...
printf("邻接表的深度优先遍历\n");
MGraph G;
GraphAdjList GL;
CreateMGraph(&G);
CreateALGraph(G, &GL);
DFSDisplay(GL);
printf("\n");
return 0;
}
输出结果:
邻接表的深度优先遍历
A F G H E D I C B
Program ended with exit code: 0
接下来来实现一下图的广度优先遍历，还是一样，对邻接矩阵和邻接表都实现广度优先遍历操作
广度优先遍历的特点：
1、把根节点放到队列的末尾。
2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队 列的末尾。并把这个元素记为它下一级元素的前驱。
3、找到所要找的元素时结束程序。
4、如果遍历整个树还没有找到，结束程序.
截屏2020-04-30 下午4.56.53.png
用一个数组，标记每一个节点是否有被输出；再利用队列的思想，先将第一个节点打印输出，将第一个节点入队，判断队列是否为空，将入队的节点出队，再将与该节点相连的节点且未被标记过的节点入队，将队列出队，打印出队的那一个节点，直到最后一个节点打印结束
邻接矩阵的广度优先遍历
1、矩阵结构设计
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535
typedef struct {
VertexType vexs[MAXVEX];//顶点表
EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵，可看作边表
int numVertexes,numEdges;//图中当前的顶点数和边数
}MGraph;
2、构建邻接矩阵和之前的一摸一样，这边就不在写了
3、队列的初始化，入队，出队，判空操作
//1、需要用到的队列结构与相关功能函数
//循环队列的顺序存储结构
typedef struct{
int data[MAXSIZE];
int front;
int rear;
}Queue;
//初始化一个空队列
Status InitQueue(Queue *Q){
Q->front = 0;
Q->rear = 0;
return OK;
}
//若队列为空，则返回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;
Q->rear = (Q->front+1)%MAXSIZE;
return OK;
}
//若队列不空，则删除Q中对头元素，用e返回
Status DeQueue(Queue *Q,int *e){
if(Q->front == Q->rear)
return ERROR;
*e = Q->data[Q->front];
Q->front = (Q->front+1)%MAXSIZE;
return OK;;
}
4、广度优先遍历矩阵
Boolean visited[MAXVEX];
void BFSDisplay(MGraph G){
Queue q;
InitQueue(&q);
for (int i = 0; i<G.numVertexes; i++) {
visited[i] = FALSE;
}
for (int 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);
for (int 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(int argc, const char * argv[]) {
// insert code here...
printf("邻接矩阵的广度优先遍历!\n");
MGraph G;
CreateMGraph(&G);
BFSDisplay(G);
printf("\n");
return 0;
}
输出结果:
邻接矩阵的广度优先遍历!
A B F C G I D E H
Program ended with exit code: 0
邻接表的广度优先遍历
邻接表的广度遍历和邻接矩阵的广度优先遍历一样，同样利用队列的思想，只是两种方式结构不同
1、邻接表的结构设计
#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 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 EdgeNode{
int adjvex;//邻接点域
int weight;//用于存储权值
struct EdgeNode *next;//链域，指向下一个邻接点
}EdgeNode;
typedef struct VertexNode{
int in;
int data;
EdgeNode *firstedge;
}VertexNode,AdjList[MAXVEX];
typedef struct {
AdjList adjList;
int numVertexes,numEdges;
}GraphAdjList ,*graphAdjList;
2、构建邻接矩阵在上面有，且一摸一样，不重复写了。
3、将邻接矩阵转换成邻接表，在之前也写过，且一摸一样，不重复写了
4、队列的初始化，判空，入队，出队不再重复编写
5、邻接表的广度优先遍历，部分操作与之前的描述也一样，因此不再多余赘述
//邻接表广度优先遍历
Boolean visited[MAXSIZE];
void BFSDisplay(graphAdjList G){
EdgeNode *p;
Queue Q;
InitQueue(&Q);
for (int i = 0; i<G->numVertexes; i++) {
visited[i] = FALSE;
}
for (int i = 0; i<G->numVertexes; i++) {
if(!visited[i]){
visited[i] = TRUE;
printf("%c ",G->adjList[i].data);
}
EnQueue(&Q, i);
while (!QueueEmpty(Q)) {
DeQueue(&Q, &i);
p = G->adjList[i].firstedge;
while (p) {
if(!visited[p->adjvex]){
visited[p->adjvex] = TRUE;
printf("%c ",G->adjList[p->adjvex].data);
EnQueue(&Q, p->adjvex);
}
p = p->next;
}
}
}
}
打印结果
int main(int argc, const char * argv[]) {
// insert code here...
printf("邻接表的广度优先遍历!\n");
MGraph G;
graphAdjList L;
createMGraph(&G);
CreateALMGraph(G, &L);
BFSDisplay(L);
printf("\n");
return 0;
}
输出结果:
邻接表的广度优先遍历!
A F B G E H D I C
Program ended with exit code: 0
设图G有n个顶点和e条边
则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度为O(n^2)
而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为O(e)
图的深度或广度优先搜索遍历时的空间复杂度均为O(n)。
