【数据结构】24王道考研笔记——图

**图**

###1. 图的定义图是由顶点（也称为结点或元胞）和边组成的非线性数据结构。每个顶点代表一个实体，每条边代表两个顶点之间的关系。

###2. 图的基本概念* **顶点（Vertex）：** 每个顶点都有一个唯一的标识符。
* **边（Edge）：** 每条边连接两个顶点，表示它们之间的关系。每条边也可以有一个权值。
* **图的类型：**
* **无向图（Undirected Graph）：** 每条边都没有方向。
* **有向图（Directed Graph）：** 每条边都有方向。

###3. 图的存储结构* **邻接矩阵（Adjacency Matrix）：** 使用一个二维数组来表示图。每个顶点对应一个行和一列，若两个顶点之间有边，则相应位置为1；否则为0。
* **邻接链表（Adjacency List）：** 使用一个链表来存储每个顶点的邻居。

###4. 图的遍历* **深度优先搜索（Depth-First Search，DFS）：** 从起始顶点开始，沿着边向下探索，直到达叶子结点或回溯。
* **广度优先搜索（Breadth-First Search，BFS）：** 从起始顶点开始，沿着边向下扩展，但每层都要遍历完。

###5. 图的应用* **网络拓扑学：** 图可以用来表示网络结构。
* **交通规划：** 图可以用来表示城市交通网。
* **推荐系统：** 图可以用来表示用户之间的关系和兴趣。

###6. 常见图算法* **最短路径问题（Shortest Path Problem）：** 找到两个顶点之间的最短路径。
* **最小生成树问题（Minimum Spanning Tree Problem）：** 找到一个包含所有顶点且边权值最小的子图。

###7. 图的实现

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

 def add_edge(self, u, v):
 self.adj_matrix[u][v] =1 self.adj_matrix[v][u] =1 def dfs(self, start_vertex):
 visited = [False for _ in range(self.num_vertices)]
 stack = [start_vertex]
 visited[start_vertex] = True while stack:
 vertex = stack.pop()
 print(vertex, end=" ")

 for i in range(self.num_vertices):
 if self.adj_matrix[vertex][i] ==1 and not visited[i]:
 stack.append(i)
 visited[i] = True def bfs(self, start_vertex):
 visited = [False for _ in range(self.num_vertices)]
 queue = [start_vertex]
 visited[start_vertex] = True while queue:
 vertex = queue.pop(0)
 print(vertex, end=" ")

 for i in range(self.num_vertices):
 if self.adj_matrix[vertex][i] ==1 and not visited[i]:
 queue.append(i)
 visited[i] = True# Example usageg = Graph(5)
g.add_edge(0,1)
g.add_edge(0,2)
g.add_edge(1,3)
g.add_edge(2,4)

print("DFS Traversal:")
g.dfs(0)

print("
BFS Traversal:")
g.bfs(0)