无向图邻接表怎么写?
时间: 2024-04-15 10:21:28 浏览: 19
无向图的邻接表是一种常用的数据结构,用于表示无向图中各个顶点之间的关系。邻接表由一个数组和一组链表组成,数组的每个元素表示一个顶点,链表则表示与该顶点相邻的其他顶点。
下面是一个示例代码,演示了如何使用邻接表表示无向图:
```python
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_list = [None] * num_vertices
def add_edge(self, src, dest):
# 添加边,将顶点dest添加到顶点src的链表中
node = Node(dest)
node.next = self.adj_list[src]
self.adj_list[src] = node
# 由于是无向图,所以还需要将顶点src添加到顶点dest的链表中
node = Node(src)
node.next = self.adj_list[dest]
self.adj_list[dest] = node
def print_adj_list(self):
# 输出邻接表
for i in range(self.num_vertices):
print("顶点", i, "的邻接表:")
node = self.adj_list[i]
while node:
print(" ->", node.value, end="")
node = node.next
print()
# 创建一个无向图
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)
# 输出邻接表
g.print_adj_list()
```
运行以上代码,将会输出如下结果:
```
顶点 0 的邻接表:
-> 4 -> 1
顶点 1 的邻接表:
-> 4 -> 3 -> 2 -> 0
顶点 2 的邻接表:
-> 3 -> 1
顶点 3 的邻接表:
-> 4 -> 2 -> 1
顶点 4 的邻接表:
-> 3 -> 1 -> 0
```