1.图的建立及输出 任务:建立图的存储结构(图的类型可以是有向图、无向图、有向网、无向网),能够输入图的顶点和边的信息,并存储到相应存储结构中,然后输出图的相关信息。
时间: 2023-12-23 15:05:29 浏览: 28
好的,我可以帮助你解决这个问题。
图的存储结构有两种常见的方式,分别是邻接表和邻接矩阵。其中,邻接表适合表示稀疏图,而邻接矩阵适合表示稠密图。这里我们以邻接表为例,实现无向图的建立和输出。
```python
class Graph:
def __init__(self):
self.vertices = {} # 存储图的所有顶点
def add_vertex(self, vertex):
if vertex not in self.vertices:
self.vertices[vertex] = set()
def add_edge(self, v1, v2):
if v1 in self.vertices and v2 in self.vertices:
self.vertices[v1].add(v2)
self.vertices[v2].add(v1)
def __str__(self):
res = "Vertices:\n"
for vertex in self.vertices:
res += str(vertex) + " "
res += "\nEdges:\n"
for vertex in self.vertices:
res += str(vertex) + ": "
for neighbor in self.vertices[vertex]:
res += str(neighbor) + " "
res += "\n"
return res
# 测试样例
g = Graph()
g.add_vertex(1)
g.add_vertex(2)
g.add_vertex(3)
g.add_vertex(4)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(4, 1)
print(g)
```
以上代码中,`Graph` 类表示图,包含两个方法 `add_vertex` 和 `add_edge`,分别用来添加顶点和边。`add_vertex` 方法接受一个参数 `vertex`,表示要添加的顶点;`add_edge` 方法接受两个参数 `v1` 和 `v2`,表示要添加的边。在 `add_vertex` 方法中,我们使用字典来存储所有的顶点,字典的 key 是顶点的值,value 是与其相邻的所有顶点的集合。在 `add_edge` 方法中,我们检查要添加的两个顶点是否都已经存在于字典中,如果存在,则将它们相互连接起来。在 `__str__` 方法中,我们遍历字典中的所有顶点,输出它们的值以及与之相邻的所有顶点。