图的遍历(深度优先遍历,DFS)

1.概念

图的遍历操作是从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次

（1）在图中，遍历的起始顶点是编号最小的顶点

（2）某个起点到达不了所有顶点，则多次调用访问所有顶点

（3）为避免遍历因回路而陷入死循环，附设置访问标志数组visited[n]（其中是对应所有的顶点下标，访问过设置为1；未访问过设置为0）

（4）所有结点的编号均从0开始

2.思路

（1）访问顶点v；

（2）从v的未被访问的邻接点中选取一个顶点w（选取规则是找相邻编号最小的结点），从w出发进行深度优先遍历；

（3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。

例如下图：（图片来自懒猫老师《数据结构》相关课程讲义）

伪代码：

寻找下一个访问点的方法：

（1）邻接矩阵：因为邻接矩阵的列的编号顺序是从小到大，所以寻找下一个访问点可以直接访问当前访问点对应行的第一个非零元素（w未被访问）

（2）邻接表：访问该点对应的边表，且前提是边表的所有结点是由下标从小到大进行排列

3.代码实现

3.1功能函数

（1）邻接矩阵的深度优先遍历

void DFSTraverse(int arc[][MAX_VERTEX], DataType *vertex, int *visited, int vertexNum,int v) { //v是遍历的起始位置的编号static int flag = 0;if (flag == 0) {//第一次需要初始化initvertex(vertexNum, visited);flag = 1;}visit(vertex, v); //输出访问过的顶点信息visited[v] = 1;for (int i = 0; i < vertexNum; i++) { //因为是邻接矩阵，所以编号的顺序本来就是由小到大的.所以不用遍历找if (arc[v][i] != 0 && visited[i] == 0)DFSTraverse(arc, vertex, visited, vertexNum, i); //二维数组传参，调用时实参直接写数组名}
}

（2）邻接表的深度优先遍历

void DFSTraverse(VertexNode *adjList, int *visited, int vertexNum, int v) {static int flag = 0;if (flag == 0) {//第一次需要初始化initvertex(vertexNum, visited);flag = 1;}visit(adjList, v); //输出访问过的顶点信息visited[v] = 1;ArcNode *p = adjList[v].firstEdge;while (p != NULL) {if (visited[p->adjvex] == 0)DFSTraverse(adjList, visited, vertexNum, p->adjvex);p = p->next;}
}
void initvertex(int vertexNum, int *visited) { //初始化visited函数for (int i = 0; i < vertexNum; i++)visited[i] = 0;
}void visit(VertexNode *adjList, int v) { //输出访问过的顶点信息printf("%d ", adjList[v].vertex);//记得改变输出时要改变数据类型
}void ranklist(VertexNode *adjList, int vertexNum) { //将边表进行升序的排序，便于遍历操作ArcNode *p, *q;int temp;for (int i = 0; i < vertexNum; i++) {p = adjList[i].firstEdge;q = p;while (p != NULL) {while (q != NULL) {if (p->adjvex > q->adjvex) {temp = p->adjvex;p->adjvex = q->adjvex;q->adjvex = temp;}q = q->next;}p = p->next;}}
}

3.2完整代码及测试

（1）邻接矩阵

1）图_邻接矩阵.h

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_VERTEX 10//最大的顶点个数
typedef int DataType;//以下是无向图的定义
void MGraph(DataType *vertex, int arc[][MAX_VERTEX], int vertexNum, int arcNum) { //初始化构造图（邻接矩阵法）printf("请逐个输入顶点的内容：");DataType x;DataType vi, vj; //构建邻接矩阵时，一条边的两个结点编号for (int i = 0; i < vertexNum; i++) { //顶点数组赋值scanf("%d", &x);vertex[i] = x;}for (int i = 0; i < vertexNum; i++) //初始化邻接矩阵for (int j = 0; j < vertexNum; j++)arc[i][j] = 0;int count = 1;for (int i = 0; i < arcNum; i++) { //依次输入每一条边printf("请输入第%d条边依附的两个顶点的编号：", count++);scanf("%d %d", &vi, &vj); //输入该边依附的顶点的编号arc[vi][vj] = 1; //置有边标志arc[vj][vi] = 1;}}void printMGraph(DataType *vertex, int arc[][MAX_VERTEX], int vertexNum) { //输出printf("vertex:");for (int i = 0; i < vertexNum; i++) {printf("%d ", vertex[i]);}printf("\n");printf("arc:\n");for (int i = 0; i < vertexNum; i++) {for (int j = 0; j < vertexNum; j++) {if (j == vertexNum - 1)printf("%d\n", arc[i][j]);elseprintf("%d ", arc[i][j]);}}}int isLinked(int arc[][MAX_VERTEX], int i, int j) { //两顶点i,j是否有边相连,1是相连，0是不相连if (arc[i][j] == 1)return 1;elsereturn 0;
}int nodeDepth(int arc[][MAX_VERTEX], int index, int vertexNum) { //任意一顶点的度//无向图任意遍历行\列求和int count = 0;for (int i = 0; i < vertexNum; i++) {if (arc[index][i] == 1)count++;}return count;
}void initvertex(int vertexNum, int *visited) { //初始化visited函数for (int i = 0; i < vertexNum; i++)visited[i] = 0;
}void visit(DataType *vertex, int v) { //输出访问过的顶点信息printf("%d ", vertex[v]);}void DFSTraverse(int arc[][MAX_VERTEX], DataType *vertex, int *visited, int vertexNum,int v) { //v是遍历的起始位置的编号static int flag = 0;if (flag == 0) {//第一次需要初始化initvertex(vertexNum, visited);flag = 1;}visit(vertex, v); //输出访问过的顶点信息visited[v] = 1;for (int i = 0; i < vertexNum; i++) { //因为是邻接矩阵，所以编号的顺序本来就是由小到大的.所以不用遍历找if (arc[v][i] != 0 && visited[i] == 0)DFSTraverse(arc, vertex, visited, vertexNum, i); //二维数组传参，调用时实参直接写数组名}
}

2）图的测试_邻接矩阵.c

#include "图_邻接矩阵.h"main() {DataType vertex[MAX_VERTEX];//储存所有的顶点int arc[MAX_VERTEX][MAX_VERTEX];//邻接矩阵，结点间的连通关系int vertexNum, arcNum; //结点个数，边的个数printf("输入顶点个数:");scanf("%d", &vertexNum);printf("输入边个数:");scanf("%d", &arcNum);MGraph(vertex, arc, vertexNum, arcNum);printMGraph(vertex, arc, vertexNum);printf("测试判断两顶点是否相连，请输入两个顶点下标:");int i, j;scanf("%d %d", &i, &j);if (isLinked(arc, i, j) == 1)printf("相连！\n");elseprintf("不相连！\n");printf("测试求顶点的度，请输入一个顶点下标:");int index;scanf("%d", &index);printf("该顶点的度为:%d\n", nodeDepth(arc, index, vertexNum));printf("测试邻接矩阵的深度优先遍历:\n");int visited[vertexNum];//判断结点是否访问过，访问过设置1，未访问过为0int v;printf("请输入深度优先遍历的第一个结点编号:");scanf("%d", &v);printf("深度优先遍历序列:");DFSTraverse(arc, vertex, visited, vertexNum, v);}

3）测试输出

测试用例：（无向图）

输出：（注意区分结点的内容和编号，结点数据从1开始，结点编号从0开始）

（2）邻接表

1）图_邻接表.h

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_VERTEX 10//最大的顶点个数
typedef char DataType;/*
当DataType为char时要特别注意输入时空格和换行符，分别利用getchar()
和fflush(stdin);来清空内存区
*/
typedef struct ArcNode { /*边表结点*/int adjvex;//边表数据域，即下标struct ArcNode *next; //指针域
} ArcNode;typedef struct VertexNode { /*顶点表结点*/DataType vertex;//顶点的数据ArcNode *firstEdge; //指向储存该顶点所连接所有结点的边表
} VertexNode;
void initVertex(DataType *, int);//以下是有向图的定义
void ALGraph(DataType *vertex, VertexNode *adjList, int vertexNum, int arcNum) { //初始化构造图（邻接表法）int vi, vj;int count = 0;initVertex(vertex, vertexNum);for (int i = 0; i < vertexNum; i++) { //初始化顶点表adjList[i].vertex = vertex[i];adjList[i].firstEdge = NULL;}for (int i = 0; i < arcNum; i++) {//输入边的信息储存在边表中printf("请输入第%d条边依附的两个顶点的编号(方向->)：", count++);fflush(stdin);//清除输入缓冲区（否则这里就会直接跳过scanf）
/*当DataType为int时要去掉上面这个语句*/scanf("%d %d", &vi, &vj); //输入该边依附的顶点的编号ArcNode *s;s = (ArcNode *)malloc(sizeof(ArcNode));if (s != NULL) {s->adjvex = vj;s->next = adjList[vi].firstEdge; //头插法建立链表adjList[vi].firstEdge = s;} elseprintf("init error!\n");}
}void initVertex(DataType *vertex, int vertexNum) {//输入函数printf("请逐个输入顶点的内容：");DataType x;for (int i = 0; i < vertexNum; i++) { //顶点数组赋值getchar();//吸收空格，当DataType为int时要去掉这个语句scanf("%c", &x);vertex[i] = x;}
}void printALGraph(VertexNode *adjList, int vertexNum) {printf("vertex  firstEdge\n");ArcNode *p ;for (int i = 0; i < vertexNum; i++) {printf("%3c -->", adjList[i].vertex);p = adjList[i].firstEdge;while (p != NULL) {printf("%d -->", p->adjvex);p = p->next;}printf("NULL\n");printf("\n");}
}int isLinked(VertexNode *adjList, int i, int j) { //两顶点i,j是否有边相连,1是相连，0是不相连ArcNode *p = adjList[i].firstEdge ;while (p != NULL) {if (p->adjvex == j)return 1;elsep = p->next;}p = adjList[j].firstEdge;while (p != NULL) {if (p->adjvex == i)return 1;elsep = p->next;}return 0;
}int nodeDepth(VertexNode *adjList, int index, int vertexNum) { //任意一顶点的度int count = 0;ArcNode *p = adjList[index].firstEdge;while (p != NULL) {count++;p = p->next;}return count;
}void freeArcNode(VertexNode *adjList, int vertexNum) {ArcNode *p;ArcNode *temp;for (int i = 0; i < vertexNum; i++) {p = adjList[i].firstEdge ;while (p != NULL) {temp = p;p = p->next;free(temp);}}
}void initvertex(int vertexNum, int *visited) { //初始化visited函数for (int i = 0; i < vertexNum; i++)visited[i] = 0;
}void visit(VertexNode *adjList, int v) { //输出访问过的顶点信息printf("%c ", adjList[v].vertex);//记得改变输出时要改变数据类型
}void DFSTraverse(VertexNode *adjList, int *visited, int vertexNum, int v) {static int flag = 0;if (flag == 0) {//第一次需要初始化initvertex(vertexNum, visited);flag = 1;}visit(adjList, v); //输出访问过的顶点信息visited[v] = 1;ArcNode *p = adjList[v].firstEdge;while (p != NULL) {if (visited[p->adjvex] == 0)DFSTraverse(adjList, visited, vertexNum, p->adjvex);p = p->next;}
}void ranklist(VertexNode *adjList, int vertexNum) { //将边表进行升序的排序，便于遍历操作ArcNode *p, *q;int temp;for (int i = 0; i < vertexNum; i++) {p = adjList[i].firstEdge;q = p;while (p != NULL) {while (q != NULL) {if (p->adjvex > q->adjvex) {temp = p->adjvex;p->adjvex = q->adjvex;q->adjvex = temp;}q = q->next;}p = p->next;}}
}

2）图的测试_邻接表.c

#include "图_邻接表.h"int main() {DataType vertex[MAX_VERTEX];//储存所有的顶点int vertexNum, arcNum; //结点个数，边的个数printf("输入顶点个数:");scanf("%d", &vertexNum);printf("输入边个数:");scanf("%d", &arcNum);VertexNode adjList[vertexNum];//顶点表ALGraph(vertex, adjList, vertexNum, arcNum);ranklist(adjList, vertexNum);printALGraph(adjList, vertexNum);printf("测试判断两顶点是否相连，请输入两个顶点下标:");int i, j;scanf("%d %d", &i, &j);if (isLinked(adjList, i, j) == 1)printf("相连！\n");elseprintf("不相连！\n");printf("测试求顶点的度，请输入一个顶点下标:");int index;scanf("%d", &index);printf("该顶点的度为:%d\n", nodeDepth(adjList, index, vertexNum));printf("测试邻接表的深度优先遍历:\n");int visited[vertexNum];//判断结点是否访问过，访问过设置1，未访问过为0int v;printf("请输入深度优先遍历的第一个结点编号:");scanf("%d", &v);printf("深度优先遍历序列:");DFSTraverse(adjList, visited, vertexNum, v);freeArcNode(adjList, vertexNum);
}

3）测试输出

测试用例：（有向图）