python邻接表的实现
时间: 2023-11-05 12:12:16 浏览: 37
Python邻接表可以通过字典来实现,其中字典的key表示图中的节点,value则表示与该节点相连的所有节点。例如,表示A节点与B、C两个节点相连的邻接表可以表示为{'A': ['B', 'C']}。具体实现可以参考以下代码:
```
graph = {}
graph['A'] = ['B', 'C']
graph['B'] = ['D', 'E']
graph['C'] = ['F']
graph['D'] = []
graph['E'] = ['F']
graph['F'] = []
# 访问节点的所有邻居
print(graph['A'])
```
相关问题
python邻接表实现Graph
下面是 Python 中邻接表实现的一个 Graph 类的示例代码:
```python
class Graph:
def __init__(self):
self.vertList = {}
self.numVertices = 0
def addVertex(self, key):
self.numVertices += 1
newVertex = Vertex(key)
self.vertList[key] = newVertex
return newVertex
def getVertex(self, n):
if n in self.vertList:
return self.vertList[n]
else:
return None
def __contains__(self, n):
return n in self.vertList
def addEdge(self, f, t, weight=0):
if f not in self.vertList:
self.addVertex(f)
if t not in self.vertList:
self.addVertex(t)
self.vertList[f].addNeighbor(self.vertList[t], weight)
def getVertices(self):
return self.vertList.keys()
def __iter__(self):
return iter(self.vertList.values())
```
在这个示例中,Graph 类具有一个 vertList 实例变量,该变量是一个字典,用于存储该图中所有的顶点。numVertices 变量用于记录该图中顶点的数量。addVertex 方法用于向该图中添加一个顶点,getVertex 方法返回指定 id 的顶点,__contains__ 方法用于判断指定 id 的顶点是否在该图中。addEdge 方法用于向该图中添加一条边,getVertices 方法返回该图中所有顶点的 id,__iter__ 方法用于迭代该图中的所有顶点。
python实现邻接表
以下是Python实现邻接表的示例代码:
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_list = [[] for _ in range(num_vertices)]
def add_edge(self, source, dest):
self.adj_list[source].append(dest)
self.adj_list[dest].append(source)
def print_adj_list(self):
for i in range(self.num_vertices):
print(i, ":", " -> ".join([str(x) for x in self.adj_list[i]]))
```
这个示例代码中,我们定义了一个Graph类,其中包含了三个方法:
1. `__init__`方法:初始化一个空的邻接表,其中`num_vertices`表示图中顶点的数量,`adj_list`是一个列表,用于存储每个顶点及其相邻的所有顶点。
2. `add_edge`方法:用于向邻接表中添加一条边,其中`source`和`dest`分别表示边的起点和终点。
3. `print_adj_list`方法:用于打印邻接表,其中对于每个顶点,我们将其编号以及与其相邻的所有顶点打印出来。