图的创建及遍历(DFS和BFS)python代码
时间: 2024-03-20 08:41:48 浏览: 15
好的,这里是Python实现图的创建及遍历(DFS和BFS)的完整代码示例:
邻接表实现:
```python
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def dfs(self, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
print(vertex)
for neighbor in self.graph[vertex]:
if neighbor not in visited:
stack.append(neighbor)
def bfs(self, start):
visited = set()
queue = [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
print(vertex)
for neighbor in self.graph[vertex]:
if neighbor not in visited:
queue.append(neighbor)
```
邻接矩阵实现:
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_matrix = [[0] * 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):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
print(vertex)
for neighbor in range(self.num_vertices):
if self.adj_matrix[vertex][neighbor] == 1 and neighbor not in visited:
stack.append(neighbor)
def bfs(self, start):
visited = set()
queue = [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
print(vertex)
for neighbor in range(self.num_vertices):
if self.adj_matrix[vertex][neighbor] == 1 and neighbor not in visited:
queue.append(neighbor)
```
注意:这是简单的示例代码,实际应用中可能需要考虑更多的情况,比如图中是否有环、是否有孤立节点等。