代码随想录算法训练营第三十六天

**代码随想录算法训练营 第三十六天**

今天是我们在代码随想录算法训练营的第36天。经过这么多天的学习和实践，我们已经掌握了一些基本的数据结构和算法知识。今天，我们将继续学习关于图论的一些内容。

**图论基础**

图论是一门研究图形结构的数学学科。图是由顶点（也称为结点）和边组成的。每个顶点代表一个实体，每条边代表两个顶点之间的关系。

在图论中，我们常常使用以下几个概念：

* **顶点**：图中的一个点，通常用来表示一个实体。
* **边**：连接两个顶点的线段，表示两个顶点之间的关系。
* **度**：一个顶点拥有的边数。
* **邻接**：两个顶点之间存在边。

**图的存储**

在实际应用中，我们需要将图存储起来，以便能够快速地访问和操作图中的数据。常用的图存储方法有：

* **邻接矩阵**：使用一个二维数组来表示图的结构，每个元素代表两个顶点之间是否存在边。
* **邻接链表**：使用一个链表来表示每个顶点的邻居。

下面是一个简单的例子，展示了如何使用邻接矩阵和邻接链表来存储一个图：

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

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

# 创建一个图，包含5个顶点g = Graph(5)

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

print("邻接矩阵:")
for row in g.adj_matrix:
 print(row)

print("
邻接链表:")
for i in range(g.num_vertices):
 print(f"顶点 {i} 的邻居：{g.adj_list[i]}")

在这个例子中，我们定义了一个 `Graph` 类来存储图的结构。我们使用邻接矩阵和邻接链表来表示图的结构，每个元素代表两个顶点之间是否存在边。

**图的遍历**

图的遍历是指访问图中的每个顶点一次的过程。在实际应用中，我们常常需要遍历图来完成某些任务。常用的图遍历算法有：

* **深度优先搜索（DFS）**：从一个起始顶点开始，沿着边向下探索直到叶子结点。
* **广度优先搜索（BFS）**：从一个起始顶点开始，沿着边向下探索，但每次只访问距离当前顶点最远的顶点。

下面是一个简单的例子，展示了如何使用 DFS 和 BFS 来遍历一个图：

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

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

 def dfs(self, start_vertex):
 visited = [False] * self.num_vertices stack = [start_vertex]
 visited[start_vertex] = True while stack:
 vertex = stack.pop()
 print(vertex, end=" ")

 for neighbor in self.adj_list[vertex]:
 if not visited[neighbor]:
 stack.append(neighbor)
 visited[neighbor] = True def bfs(self, start_vertex):
 visited = [False] * self.num_vertices queue = [start_vertex]
 visited[start_vertex] = True while queue:
 vertex = queue.pop(0)
 print(vertex, end=" ")

 for neighbor in self.adj_list[vertex]:
 if not visited[neighbor]:
 queue.append(neighbor)
 visited[neighbor] = True# 创建一个图，包含5个顶点g = Graph(5)

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

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

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

在这个例子中，我们定义了一个 `Graph` 类来存储图的结构。我们使用 DFS 和 BFS 来遍历图，访问每个顶点一次。

以上就是今天关于图论的一些内容。图论是一门非常重要的数学学科，它有很多实际应用。在实际应用中，我们常常需要将图存储起来，以便能够快速地访问和操作图中的数据。我们也可以使用 DFS 和 BFS 来遍历图，访问每个顶点一次。

希望以上内容对你有所帮助。如果你有任何问题或疑问，请随时告诉我，我会尽力回答你的问题。