数据结构笔记：图 (邻接矩阵、广度优先、深度优先搜索)

发表于 | 分类于

概述

  1. 邻接矩阵
  2. 广度优先搜索
  3. 深度优先搜索
  4. 拓扑排序
小试牛刀
1
2
3
4
5
6
7
8
9
10
11
12
单选题
DFS on a graph, which situation means that the graph contains a loop 对图进行DFS，一下哪种情况意味着该图包含环路：
A. There has a TREE edge 有TREE边
B. There has a BACKWARD edge 有BACKWARD边
C. There has a FORWARD edge 有FORWARD边
D. There has a CROSS edge 有CROSS边

答案：B 
TREE边（树边）：DFS树的一部分，连接一个顶点到其未访问的邻居。这些边不表示环路。
BACKWARD边（后向边）：从一个顶点指向其在DFS树中的祖先的边。这种边的存在表示图中存在环路，因为它形成了一个从祖先到后代的路径，再加上这条边就构成了一个环。
FORWARD边（前向边）：从一个顶点指向其在DFS树中的后代（但不是直接孩子）的边。这种边不表示环路，因为它只是指向子孙，不会形成环。
CROSS边（交叉边）：连接不同DFS树或同一DFS树中无祖先-后代关系的顶点的边。这种边在无环图（如DAG）中可能存在，不直接表示环路。
邻接和关联

临接关系：顶点和顶点之间

关联关系：顶点和边之间

无向图和有向图
路径和环路

欧拉环路：一个经过所有的边一次且恰好一次（覆盖了图中所有的边）

image-20250705224546020

哈密尔顿环路

image-20250705224736718

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 单选题

The relationship between two vertices connected by a edge is called:两个通过一条边连起来的顶点之间的关系称为：B邻接

A. connected 相连
B. adjacent 邻接
C. related 关联
D. neighbor 邻居


The one-touch-drawing question is to find out: 一笔画问题即要找出：

A. Path 路径
B. Euler path 欧拉路径
C. Hamiltonian cycle 哈密尔顿环路
D. Simple cycle 简单环

邻接矩阵

如何在计算机中以数据结构表示并且实现图

邻接矩阵：n 行 n 列

关联矩阵：n 行 e 列

n 为节点的个数，e为边的个数。

image-20250705231425592

image-20250705231636843

顶点定义：

image-20250705231243553

边定义：

image-20250705231125730

邻接矩阵定义：

image-20250705232935768

顶点操作

image-20250705233056615

对于顶点 i ， 枚举其所有的邻接顶点 neighbor

image-20250705232244942

边操作：

image-20250705233300379

边插入：

image-20250705233412485

边删除：

image-20250705233517697

顶点动态操作：

image-20250705234305941

题：

1
图G包含n个顶点(n>0)，用邻接矩阵实现。在其中加入一个新的顶点后邻接矩阵增加了多少项？  2n + 1

广度优先搜索

Graph -> Tree

image-20250706185209525

image-20250706185633986

image-20250706185957358

对多连通域，可以遍历节点，如果节点为UNDISCOVERED，则BFS() 遍历。

每个连通域会执行一次BFS()

image-20250706191515831

复杂度

使用邻接表

image-20250706192948245

最短路径：

image-20250706194922789

image-20250706192858239

1
对于用邻接表实现的包含n个顶点e条边的图，BFS的时间复杂度为： O(n + e)

深度优先搜索

image-20250706234132873

框架：

image-20250706234321569

细节：

image-20250706234559465

无向图实例：

image-20250706235232601

有向图实例：

image-20250707000349992

嵌套引理：

image-20250707001024924

拓扑排序

任何有向无环图G中，必有一个零入度的顶点m

image-20250707004116371

习题

1
2
3
4
5
6
填空题
In a simple undigraph with 20 vertices, the maximum number of edges is:
在含20个顶点的简单无向图中，边的数量最多为：__190__

The degree of the vertex with the smallest degree at this time is:
此时度最小的顶点的度为：__19__
1
2
3
4
5
6
7
8
A total of 7 people took part in the banquet and a friendly handshake took place among the participants. The number of hands-on handshakes known to each of them is:
3, 1, 2, 2, 3, 1, 2

How many handshakes have occurred at the banquet?
某宴会一共有7个人参加，与会者之间进行了亲切的握手。已知他们中的每个人进行握手的次数分别为：
3, 1, 2, 2, 3, 1, 2

请问宴会上总共发生了多少次握手？  7

image-20250706175638313

image-20250706175731571

image-20250706180706474

7. 

1
2
用邻接矩阵实现含n个顶点e条边的图：
Space complexity: 空间复杂度：O(n^2)

8. 

1
Time complexity of deleting edge(i,j): 删除边(i, j)的时间复杂度：O(1)

9. 

1
Time complexity of traversing all the neighbors of vertex v: 遍历顶点v的所有邻居的时间复杂度：O(n)

10. 

1
访问顶点v中存储的数据的时间复杂度：O(1)

11. 

1
2
3
4
5
G是有向无环图，(u, v)是G中的一条由u指向v的边。对G进行DFS的结果是： C
A. dTime(u) > dTime(v)
B. dTime(u) < dTime(v)
C. fTime(u) > fTime(v)
D. fTime(u) < fTime(v)

12. 

1
2
3
4
5
下面是对一个简单无向图进行DFS后得到各顶点的dTime和fTime:
Vertex
顶点	a	b	c	d	e	f	g	h	i	j
dTime	1	2	3	10	17	4	6	5	9	7
fTime	20	19	16	11	18	15	13	14	12	8

image-20250707002829431

13.

填空题 (4分)

PS6_Q7.png

1
2
3
4
5
6
7
8
Starting from s, perform BFS on the above undigraph, order a~z between the neighbors of the same vertex, and find the dTime of the vertex
从s开始，对以上无向图进行BFS，同一顶点的邻居之间以a~z为序，求顶点的dTime
s的dTime = 1

a的dTime =__2__
b的dTime =__6__
e的dTime =__5__
f的dTime =__7__

14.

PS6_Q7.png

1
2
3
4
5
6
7
8
从s开始，对以上无向图进行DFS，同一顶点的邻居之间以a~z为序，求各顶点的dTime和fTime
s的dTime = 1
s的fTime = 16

c的dTime =__3__
c的fTime =__14__
g的dTime =__7__
g的fTime =__12__

zhangzezhong

学习自：清华大学邓俊辉老师《数据结构》课程第六章 图