邻接表 python
时间: 2023-08-16 17:17:24 浏览: 252
邻接表是一种用于表示图的数据结构,它通过将每个顶点与其相邻的顶点列表关联起来来表示图。在Python中,可以使用类来实现邻接表。
首先,我们需要创建一个Vertex类来存储顶点信息。该类包含一个data属性用于存储顶点的数据,以及一个firstEdge属性用于指向该顶点的第一条边。\[3\]
接下来,我们需要创建一个Edge类来存储边的信息。该类包含一个adjVex属性用于存储相邻顶点的索引,以及一个next属性用于指向下一条边。\[2\]
然后,我们可以创建一个LinkedGraph类来构造邻接表。在构造函数中,我们需要传入顶点列表和边列表作为参数。在构造过程中,我们可以根据边列表的信息来构建邻接表。\[1\]
最后,我们可以创建一个测试类来输出邻接表。在测试类中,我们可以创建一个LinkedGraph对象,并调用其print方法来输出邻接表。\[1\]
以下是一个示例代码:
```python
class Vertex(object):
def __init__(self, data):
self.data = data
self.firstEdge = None
class Edge(object):
def __init__(self, adjVex):
self.adjVex = adjVex
self.next = None
class LinkedGraph(object):
def __init__(self, vers, edges):
self.vertexList = \[\]
for v in vers:
self.vertexList.append(Vertex(v))
for e in edges:
v1 = self.vertexList\[vers.index(e\[0\])\]
v2 = self.vertexList\[vers.index(e\[1\])\]
edge1 = Edge(vers.index(e\[1\]))
edge2 = Edge(vers.index(e\[0\]))
edge1.next = v1.firstEdge
edge2.next = v2.firstEdge
v1.firstEdge = edge1
v2.firstEdge = edge2
def print(self):
for v in self.vertexList:
print(v.data, end=": ")
edge = v.firstEdge
while edge:
print(self.vertexList\[edge.adjVex\].data, end=" ")
edge = edge.next
print()
if __name__ == "__main__":
vers = \['A', 'B', 'C', 'D', 'E', 'F', 'G'\]
edges = \[\['A', 'C'\], \['A', 'D'\], \['B', 'E'\], \['B', 'F'\], \['C', 'E'\], \['C', 'G'\], \['D', 'F'\]\]
g = LinkedGraph(vers, edges)
g.print()
```
这段代码会输出以下邻接表:
```
A: C D
B: E F
C: A E G
D: A F
E: B C
F: B D
G: C
```
这就是使用邻接表构造无向图的Python代码。希望对你有帮助!
#### 引用[.reference_title]
- *1* *2* *3* [Python之邻接表(数据结构)](https://blog.csdn.net/wn2001/article/details/117513377)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insert_down1,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]