图论——图的遍历_2124:图的遍历

一.图的基本概念

🍟1. 图的定义
图是由顶点(Vertex)集合和边(Edge)集合组成的数据结构，记作G=(V,E)，

其中：

V是顶点的有限非空集合

E是边的有限集合，边是顶点的有序对或无序对

🍕2. 图的分类
(1) 按边是否有方向
无向图：边没有方向，(v₁,v₂)和(v₂,v₁)表示同一条边

有向图：边有方向，表示从v₁指向v₂的边

(2) 按边是否有权重
无权图：边没有权重值

带权图(网络)：边有权重值

(3) 按是否允许自环和多边
简单图：无自环、无多重边

多重图：允许有多重边

 二、图的基本术语

邻接点：

两个顶点之间有边相连，则互为邻接点

度：

无向图：顶点的度是指与该顶点相连的边的数量

有向图：

入度：指向该顶点的边的数量

出度：从该顶点指出的边的数量

路径：顶点序列v₁,v₂,...,vₙ，其中(vᵢ,vᵢ₊₁)∈E

连通性：

无向图：任意两顶点间都有路径则称为连通图

有向图：任意两顶点间双向都有路径则称为强连通图

子图：图G\'的顶点和边都是图G的子集

生成树：包含图中所有顶点的极小连通子图(有n-1条边)

三、图的存储结构

🍸1. 邻接矩阵
使用二维数组表示图中顶点间的邻接关系

特点：

适合稠密图

查找两顶点间是否有边效率高(O(1))

浪费空间(稀疏图时)

🍹2. 邻接表
为每个顶点建立一个单链表，存储其邻接顶点

特点：

适合稀疏图

节省空间

查找两顶点间是否有边效率较低(O(n))

四、图的深度优先遍历

☘️ 1.基本思想：

\"一条路走到黑\"：从起始顶点出发，沿着一条路径尽可能深地访问顶点，直到到达没有未访问邻接点的顶点为止

回溯机制：当到达最深处后，回溯到上一个顶点，寻找其他未被访问的路径

递归实现：天然适合递归实现，也可以用栈来模拟递归过程

⭐️2.算法步骤：

访问起始顶点v，并标记v为已访问

查找v的第一个未被访问的邻接顶点w

如果w存在，则以w为新的起始顶点递归执行DFS

如果w不存在，则回溯到v的上一个顶点

重复上述过程，直到图中所有顶点都被访问

✨3.典型例题：

 【问题描述】根据输入信息创建图，采用邻接表的形式存储该图 (要求每个边链表中 都是按照邻接顶点的编号由小到大的顺序链接存储的)，并用深度优先遍历算法遍历该图，输出从编号最小顶点开始的遍历序列。各顶点的数据类型为int型。

【输入形式】仿照算法7.2的输入：

第1行输入图的结点个数n。第2行是图的各顶点数据。

之后的若干行(有向图为e行, 无向图为2e行) 依次输入各条边的弧尾、弧头的顶点编号。注意：因为算法7.2是按头插法建边链表的，所以要使得到的每个边链表中 都是按照邻接顶点的编号由小到大的顺序链接存储，就必须输入各边的顺序 首先是按照弧尾编号由小到大的顺序，并且输入弧尾相同的各边时 按照弧头顶点编号由大到小的顺序输入这些边，具体见样例输入。

最后一行输入-1和-1表示输入结束。
【输出形式】
图的深度优先遍历序列, 要求从编号最小顶点开始遍历, 输出各数据间用1个空格分隔.

【样例输入】
5

1(空格)2(空格)3(空格)4(空格)5

1(空格)3

1(空格)2

2(空格)4

2(空格)3

2(空格)1

3(空格)2

3(空格)1

4(空格)5

4(空格)2

5(空格)4

-1(空格)-1

【样例输出】

1(空格)2(空格)3(空格)4(空格)5(空格)

#includeusing namespace std;#define True 1 // 定义True为1，表示已访问#define False 0 // 定义False为0，表示未访问int visited[100]; // 访问标记数组，记录顶点是否被访问过// 边节点结构定义typedef struct ArcNode { int adjvex; // 该边指向的顶点位置(邻接顶点下标) struct ArcNode *nextarc; // 指向下一条边的指针} ArcNode;// 顶点节点结构定义typedef struct VertexNode { int data;  // 顶点数据 ArcNode *firstarc; // 指向该顶点第一条边的指针(邻接表头指针)} VertexNode;// 图的邻接表结构定义typedef struct { VertexNode vertex[1000]; // 顶点数组 int vexnum; // 图的顶点数 int arcnum; // 图的边数} AdjList;// 创建图的邻接表void creat(AdjList &G) { cin >> G.vexnum; // 输入顶点数量 // 初始化所有顶点 for(int i = 1; i > G.vertex[i].data; // 输入顶点数据 G.vertex[i].firstarc = NULL; // 初始化每个顶点的边链表为空 } // 输入图的边信息 while(1) { int v1, v2; cin >> v1 >> v2; // 输入边的两个顶点 // 输入-1 -1表示边输入结束 if(v1 == -1 && v2 == -1) break; else { // 创建新的边节点(头插法) ArcNode *p1 = (ArcNode *)malloc(sizeof(ArcNode)); p1->adjvex = v2; // 设置边指向的顶点 // 将新边节点插入到v1的边链表头部 p1->nextarc = G.vertex[v1].firstarc; G.vertex[v1].firstarc = p1; } }}// 深度优先搜索(DFS)递归实现void DFS(AdjList g, int v) { cout << g.vertex[v].data <adjvex]) DFS(g, p->adjvex); p = p->nextarc; // 移动到下一个邻接点 }}// 遍历整个图(处理非连通图情况)void TraverseGraph(AdjList g) { // 初始化所有顶点为未访问状态 for(int i = 1; i <= g.vexnum; i++) visited[i] = False; // 对每个顶点进行检查 for(int i = 1; i <= g.vexnum; i++) { // 如果顶点未被访问，则以该顶点为起点进行DFS if(!visited[i]) DFS(g, i); }}int main() { AdjList G; // 声明图的邻接表 creat(G); // 创建图 TraverseGraph(G); // 深度优先遍历图 return 0;}

 五、图的广度优先遍历

🦊1.基本思想：

\"层层推进\"：从起始顶点开始，先访问所有直接邻接点，然后再访问这些邻接点的邻接点

队列辅助：使用队列来存储待访问的顶点，保证按层次顺序访问

非递归实现：通常使用循环和队列实现，不需要递归

🦝2.算法步骤：

1）访问起始顶点v，标记v为已访问，并将v入队

2）当队列不为空时：
a. 出队一个顶点u
b. 访问u的所有未被访问的邻接点w，标记w为已访问，并将w入队

3）重复上述过程直到队列为空

🐱3.典型例题：

【问题描述】根据输入信息创建图，采用邻接表的形式存储该图，并用广度优先遍历算法遍历该图，输出遍历序列。

【输入形式】

第一行为图的结点个数n，第二行为图的顶点数据，之后的n行为邻接矩阵的内容，每行n个数表示。其中A[i][j]=1表示两个结点邻接，而A[i][j]=0表示两个结点无邻接关系。
【输出形式】
图的广度优先遍历序列

【样例输入】
 5

1 2 3 4 5 
 0 1 1 0 0
 1 0 1 1 0
 1 1 0 0 0
 0 1 0 0 1
 0 0 0 1 0

【输出形式】

1 2 3 4 5
【样例输入】

4

1 2 3 4

0 1 1 0

0 0 0 0

0 0 0 1

1 0 0 0

【样例输出】

1 2 3 4

#includeusing namespace std;#define True 1 // 定义True为1，表示已访问#define False 0 // 定义False为0，表示未访问int visited[100]; // 访问标记数组，记录顶点是否被访问过// 顶点结构定义（邻接矩阵用）typedef struct { int data; // 顶点数据} node;// 邻接矩阵结构定义typedef struct { int edges[100][100]; // 邻接矩阵，存放0和1表示边是否存在 int n; // 顶点数 node vexs[100]; // 顶点数组} Matrix;// 边节点结构定义（邻接表用）typedef struct ArcNode { int adjvex; // 该边指向的顶点位置 struct ArcNode *nextarc; // 指向下一条边的指针} ArcNode;// 顶点节点结构定义（邻接表用）typedef struct VertexNode { int data;  // 顶点数据 ArcNode *firstarc; // 指向该顶点第一条边的指针} VertexNode;// 邻接表结构定义typedef struct { VertexNode vertex[100]; // 顶点数组 int vexnum; // 顶点数 int arcnum; // 边数} AdjList;// 创建邻接矩阵void creat(Matrix &g, int a[100][100], int n) { int i, j; g.n = n; // 设置顶点数 // 复制邻接矩阵数据 for(i = 0; i < n; i++) { for(j = 0; j < n; j++) g.edges[i][j] = a[i][j]; }}// 将邻接矩阵转换为邻接表void ToList(Matrix g, AdjList &G, int b[100]) { int i, j; ArcNode *p; // 初始化邻接表顶点 for(i = 0; i < g.n; i++) { G.vertex[i].data = b[i]; // 设置顶点数据 G.vertex[i].firstarc = NULL; // 初始化边链表为空 } // 转换邻接矩阵为邻接表（使用头插法） for(i = 0; i = 0; j--) { if(g.edges[i][j] != 0) { // 如果存在边 // 创建新边节点 p = (ArcNode *)malloc(sizeof(ArcNode)); p->adjvex = j; // 设置邻接顶点 // 头插法插入边 p->nextarc = G.vertex[i].firstarc; G.vertex[i].firstarc = p; } } } G.vexnum = g.n; // 设置顶点数}// 广度优先搜索(BFS)实现void BFS(AdjList G, int v) { ArcNode *p; int q[100]; // 循环队列 int front = 0; // 队首指针 int rear = 0; // 队尾指针 int j; // 访问起始顶点 cout << G.vertex[v].data <adjvex] == 0) { // 如果邻接点未被访问 // 访问并标记 cout <adjvex].data <adjvex] = True; // 入队 rear = (rear + 1) % 100; q[rear] = p->adjvex; } p = p->nextarc; // 移动到下一条边 } }}int main() { int n; // 顶点数 int data[100]; // 顶点数据数组 int a[100][100]; // 邻接矩阵数据 cin >> n; // 输入顶点数 // 初始化访问标记数组 for(int i = 0; i < n; i++) visited[i] = False; // 输入顶点数据 for(int i = 0; i > data[i]; // 输入邻接矩阵 for(int i = 0; i < n; i++) { for(int j = 0; j > a[i][j]; } Matrix g; // 邻接矩阵 AdjList G; // 邻接表 // 创建邻接矩阵 creat(g, a, n); // 将邻接矩阵转换为邻接表 ToList(g, G, data); // 从顶点0开始进行BFS遍历 BFS(G, 0); return 0;}

中国机械库最核心关键字