以邻接表的形式创建一个无向图
时间: 2023-11-24 15:08:22 浏览: 53
无向图的邻接表构建和遍历
5星 · 资源好评率100%
好的,以下是一个基于邻接表的无向图的创建过程:
假设我们有一个无向图,其中包含5个顶点和6条边,那么我们可以使用邻接表来表示它。首先,我们需要定义顶点类和边类。顶点类可以包含顶点的编号和与之相连的边,边类可以包含两个顶点和边的权重(如果有的话)。
```
class Vertex:
def __init__(self, n):
self.name = n
self.neighbors = list()
def add_neighbor(self, v):
if v not in self.neighbors:
self.neighbors.append(v)
self.neighbors.sort()
class Edge:
def __init__(self, v1, v2):
self.vertex1 = v1
self.vertex2 = v2
def __eq__(self, other):
return ((self.vertex1 == other.vertex1 and self.vertex2 == other.vertex2) or
(self.vertex1 == other.vertex2 and self.vertex2 == other.vertex1))
```
接下来,我们可以创建一个图类,该类包含一个字典,用于将顶点和顶点对象联系起来。我们还可以添加用于添加顶点和边的方法。
```
class Graph:
vertices = {}
edges = []
def add_vertex(self, vertex):
if isinstance(vertex, Vertex) and vertex.name not in self.vertices:
self.vertices[vertex.name] = vertex
return True
else:
return False
def add_edge(self, edge):
if isinstance(edge, Edge):
v1 = edge.vertex1
v2 = edge.vertex2
if v1 in self.vertices and v2 in self.vertices:
self.edges.append(edge)
self.vertices[v1].add_neighbor(v2)
self.vertices[v2].add_neighbor(v1)
return True
else:
return False
def print_graph(self):
for key in sorted(list(self.vertices.keys())):
print(key + str(self.vertices[key].neighbors))
```
现在我们可以创建一个图对象并添加顶点和边:
```
g = Graph()
a = Vertex('A')
g.add_vertex(a)
b = Vertex('B')
g.add_vertex(b)
c = Vertex('C')
g.add_vertex(c)
d = Vertex('D')
g.add_vertex(d)
e = Vertex('E')
g.add_vertex(e)
ab = Edge('A', 'B')
g.add_edge(ab)
ac = Edge('A', 'C')
g.add_edge(ac)
bd = Edge('B', 'D')
g.add_edge(bd)
cd = Edge('C', 'D')
g.add_edge(cd)
ce = Edge('C', 'E')
g.add_edge(ce)
de = Edge('D', 'E')
g.add_edge(de)
g.print_graph()
```
这将输出以下内容:
```
A['B', 'C']
B['A', 'D']
C['A', 'D', 'E']
D['B', 'C', 'E']
E['C', 'D']
```
这就是一个基于邻接表的无向图的创建过程。
阅读全文