请采用邻接表表示法实现无向图,要求: (1)建立图的邻接表存储结构; (2)实现邻接表表示法无向图的创建; (3)使用深度优先算法对上述无向图进行遍历并输出。
时间: 2024-12-06 14:25:41 浏览: 16
在计算机科学中,邻接表是一种常用的数据结构,用于表示无向图。它将每个顶点作为节点,并维护一个列表,这个列表包含与该顶点直接相连的所有其他顶点,即它们之间的边。以下是使用邻接表表示无向图的一种简单实现步骤:
1. **建立图的邻接表存储结构**:
- 定义两个数据结构:`Vertex` 类代表图中的每个顶点,它包含一个标识符(例如整数ID)和一个邻接列表;
- `AdjacencyList` 类,表示整个无向图,它维护一个字典(根据语言的不同可能是哈希表、映射等),键是顶点ID,值是一个列表,存储与之相邻的顶点列表。
```python
class Vertex:
def __init__(self, id):
self.id = id
self.neighbors = []
class AdjacencyList:
def __init__(self):
self.vertices = {}
# 示例:添加顶点和边
graph = AdjacencyList()
v1 = Vertex(1)
v2 = Vertex(2)
v3 = Vertex(3)
graph.vertices[1] = [v2]
graph.vertices[2] = [v1, v3]
graph.vertices[3] = [v2]
```
2. **实现无向图的创建**:
- 这里我们已经通过添加顶点和边完成了创建过程,可以根据需要动态地添加更多的顶点和边。
3. **使用深度优先搜索(DFS)遍历无向图**:
- DFS 是一种遍历图的算法,从某个顶点开始,访问其所有邻居,然后递归地访问他们未访问过的邻居。
- Python 代码示例:
```python
def dfs(vertex, visited=None):
if visited is None:
visited = set()
visited.add(vertex.id)
print(vertex.id) # 输出当前顶点
for neighbor in graph.vertices[vertex.id]:
if neighbor.id not in visited:
dfs(neighbor, visited)
# 调用函数开始遍历
dfs(v1)
```
阅读全文