采用邻接表存储构造无向图
时间: 2023-10-03 12:09:31 浏览: 83
邻接表是一种常见的图的存储方式,特别适用于稀疏图。邻接表存储图的方法是将每个节点的邻居节点列表存储在该节点对应的链表中。
具体来说,我们可以用一个数组来存储所有节点,数组的每个元素代表一个节点。对于数组中的第i个元素,其对应的链表中存储了所有与节点i直接相连的节点。
下面是一个例子,展示了如何用邻接表存储一个无向图:
```
0
/ \
1---2
|
3
```
首先,我们需要定义一个Node类来表示图中的节点:
```python
class Node:
def __init__(self, val):
self.val = val
self.neighbors = []
```
然后,我们可以用一个字典来存储所有节点,字典的键为节点编号,值为节点对象。接下来,我们遍历所有的边,对于每条边 (u, v),我们将节点u的邻居列表中添加节点v,将节点v的邻居列表中添加节点u。
```python
def construct_graph(edges):
nodes = {}
for u, v in edges:
if u not in nodes:
nodes[u] = Node(u)
if v not in nodes:
nodes[v] = Node(v)
nodes[u].neighbors.append(nodes[v])
nodes[v].neighbors.append(nodes[u])
return nodes
```
通过这种方式,我们可以快速地构造一个无向图,并且可以方便地遍历每个节点的邻居。
阅读全文