王道考研数据结构第七章知识点总结

**王道考研数据结构第七章知识点总结**

第七章是《王道考研数据结构》中的最后一章，主要内容包括图的基本概念、图的存储方式、图的遍历以及最短路径问题等。下面我们将对这些知识点进行详细的总结和分析。

**7.1 图的基本概念**

图是由顶点（也称为节点）和边组成的数据结构，每个顶点代表一个实体，每条边代表两个顶点之间的关系。图可以分为有向图和无向图，根据边的方向不同而定。

* 有向图：每条边都有方向，表示从一个顶点到另一个顶点的关系。
* 无向图：每条边没有方向，表示两个顶点之间的关系。

**7.2 图的存储方式**

图可以使用邻接矩阵、邻接链表或边数组来存储。下面我们将对这些存储方式进行详细的分析和代码示例：

###1. 邻接矩阵邻接矩阵是用一个二维数组来表示图的结构，每个顶点对应一个行和一列，值为1表示有边，0表示没有边。

class Graph:
 def __init__(self, n):
 self.n = n self.adj_matrix = [[0] * n for _ in range(n)]

 def add_edge(self, u, v):
 self.adj_matrix[u][v] =1# 创建一个图，顶点数为5g = Graph(5)

# 添加边g.add_edge(0,1)
g.add_edge(1,2)
g.add_edge(2,3)
g.add_edge(3,4)

# 打印邻接矩阵for row in g.adj_matrix:
 print(row)

###2. 邻接链表邻接链表是用一个链表来表示图的结构，每个顶点对应一个链表，值为1表示有边，0表示没有边。

class Graph:
 def __init__(self, n):
 self.n = n self.adj_list = [[] for _ in range(n)]

 def add_edge(self, u, v):
 self.adj_list[u].append(v)

# 创建一个图，顶点数为5g = Graph(5)

# 添加边g.add_edge(0,1)
g.add_edge(1,2)
g.add_edge(2,3)
g.add_edge(3,4)

# 打印邻接链表for i in range(g.n):
 print(f"顶点 {i} 的邻接链表：", g.adj_list[i])

###3. 边数组边数组是用一个一维数组来表示图的结构，每个元素代表一个边，包含两个顶点。

class Graph:
 def __init__(self, n):
 self.n = n self.edges = []

 def add_edge(self, u, v):
 self.edges.append((u, v))

# 创建一个图，顶点数为5g = Graph(5)

# 添加边g.add_edge(0,1)
g.add_edge(1,2)
g.add_edge(2,3)
g.add_edge(3,4)

# 打印边数组for edge in g.edges:
 print(edge)

**7.3 图的遍历**

图的遍历是指按照一定规则访问每个顶点的过程。常见的遍历方法有深度优先搜索（DFS）和广度优先搜索（BFS）。

###1. 深度优先搜索（DFS）

深度优先搜索是一种从根节点开始，沿着树的深度一直探索到叶子结点，然后回溯到上一个结点继续探索的过程。

class Graph:
 def __init__(self, n):
 self.n = n self.adj_list = [[] for _ in range(n)]

 def add_edge(self, u, v):
 self.adj_list[u].append(v)

 def dfs(self, start):
 visited = [False] * self.n stack = [start]
 while stack:
 node = stack.pop()
 if not visited[node]:
 print(node)
 visited[node] = True for neighbor in reversed(self.adj_list[node]):
 stack.append(neighbor)

# 创建一个图，顶点数为5g = Graph(5)

# 添加边g.add_edge(0,1)
g.add_edge(1,2)
g.add_edge(2,3)
g.add_edge(3,4)

# 进行深度优先搜索g.dfs(0)

###2. 广度优先搜索（BFS）

广度优先搜索是一种从根节点开始，沿着树的宽度一直探索到叶子结点，然后回溯到上一个结点继续探索的过程。

class Graph:
 def __init__(self, n):
 self.n = n self.adj_list = [[] for _ in range(n)]

 def add_edge(self, u, v):
 self.adj_list[u].append(v)

 def bfs(self, start):
 visited = [False] * self.n queue = [start]
 while queue:
 node = queue.pop(0)
 if not visited[node]:
 print(node)
 visited[node] = True for neighbor in self.adj_list[node]:
 queue.append(neighbor)

# 创建一个图，顶点数为5g = Graph(5)

# 添加边g.add_edge(0,1)
g.add_edge(1,2)
g.add_edge(2,3)
g.add_edge(3,4)

# 进行广度优先搜索g.bfs(0)

**7.4 最短路径问题**

最短路径问题是指在图中找到从一个顶点到另一个顶点的最短路径。常见的算法有迪杰斯特拉算法和弗洛伊德算法。

###1. 迪杰斯特拉算法迪杰斯特拉算法是一种用于求解最短路径问题的算法，适用于带权图。

class Graph:
 def __init__(self, n):
 self.n = n self.adj_list = [[] for _ in range(n)]

 def add_edge(self, u, v, w):
 self.adj_list[u].append((v, w))

 def dijkstra(self, start):
 visited = [False] * self.n distance = [float('inf')] * self.n distance[start] =0 for _ in range(self.n -1):
 for u in range(self.n):
 if not visited[u]:
 for v, w in self.adj_list[u]:
 if distance[v] > distance[u] + w:
 distance[v] = distance[u] + w min_distance = float('inf')
 min_index = -1 for i in range(self.n):
 if not visited[i] and distance[i] < min_distance:
 min_distance = distance[i]
 min_index = i visited[min_index] = True# 创建一个图，顶点数为5g = Graph(5)

# 添加边g.add_edge(0,1,3)
g.add_edge(1,2,4)
g.add_edge(2,3,2)
g.add_edge(3,4,6)

# 进行迪杰斯特拉算法g.dijkstra(0)

###2. 弗洛伊德算法弗洛伊德算法是一种用于求解最短路径问题的算法，适用于带权图。

class Graph:
 def __init__(self, n):
 self.n = n self.adj_list = [[] for _ in range(n)]

 def add_edge(self, u, v, w):
 self.adj_list[u].append((v, w))

 def floyd(self):
 distance = [[float('inf')] * self.n for _ in range(self.n)]
 for i in range(self.n):
 distance[i][i] =0 for u in range(self.n):
 for v, w in self.adj_list[u]:
 distance[u][v] = min(distance[u][v], w)
 for k in range(self.n):
 for i in range(self.n):
 for j in range(self.n):
 distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

# 创建一个图，顶点数为5g = Graph(5)

# 添加边g.add_edge(0,1,3)
g.add_edge(1,2,4)
g.add_edge(2,3,2)
g.add_edge(3,4,6