编写一个程序,定义图的邻接表存储结构并创建无向图的邻接表,在此基础上对无向图进行深度优先遍历,最后在主函数中进行调用演示。
时间: 2024-05-06 19:19:08 浏览: 54
以下是 Python 语言实现:
``` python
# 定义节点类
class Node:
def __init__(self, val):
self.val = val
self.neighbor = []
# 定义图类
class Graph:
def __init__(self, n):
self.nodes = []
for i in range(n):
self.nodes.append(Node(i))
# 添加边
def add_edge(self, u, v):
self.nodes[u].neighbor.append(v)
self.nodes[v].neighbor.append(u)
# 深度优先遍历
def dfs(self, start):
visited = set()
self._dfs(start, visited)
def _dfs(self, cur, visited):
print(cur)
visited.add(cur)
for nei in self.nodes[cur].neighbor:
if nei not in visited:
self._dfs(nei, visited)
# 创建无向图
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
# 深度优先遍历
g.dfs(0)
```
输出结果为:
```
0
1
2
3
4
```
说明深度优先遍历顺序为 0 -> 1 -> 2 -> 3 -> 4。
阅读全文