已知一个带权有向图,其存储结构为邻接表结构 ,设计一算法,由键盘输入数据,建立邻接表,并将其输出。 用例说明: 第一行输入图的顶点数; 第二行输入顶点信息; 第三行以后,按照顺序,每个顶点对应一行,按行输入该顶点对应边的信息(位置 1 权值 1 位置 2 权值 2 ……. ,以 -1 结束)。 输出格式中,代表链表节点的信息是:(边)权值,参见下面用例。
时间: 2024-02-02 08:03:28 浏览: 26
以下是一个实现该算法的Python代码:
```python
class Node:
def __init__(self, val, weight):
self.val = val
self.weight = weight
self.next = None
class Graph:
def __init__(self, n):
self.n = n
self.adj = [None] * n
def add_edge(self, u, v, w):
node = Node(v, w)
node.next = self.adj[u]
self.adj[u] = node
def print_graph(self):
for i in range(self.n):
print(f"Vertex {i}: ", end="")
node = self.adj[i]
while node:
print(f"({node.val}, {node.weight}) -> ", end="")
node = node.next
print("None")
n = int(input("请输入图的顶点数:"))
graph = Graph(n)
print("请输入顶点信息:")
vertices = input().split()
print("请按行输入每个顶点对应的边信息(以-1结束):")
for i in range(n):
print(f"请输入顶点{i}的边信息:")
edges = input().split()
j = 1
while edges[j] != "-1":
v = int(edges[j - 1])
w = int(edges[j])
graph.add_edge(i, v, w)
j += 2
graph.print_graph()
```
这个算法的基本思路是,定义一个`Node`类表示链表节点,包含节点值、边权值和指向下一个节点的指针。然后定义一个`Graph`类表示图,包含图的顶点数和邻接表。在输入每个顶点对应的边信息时,将每条边添加到起点对应的链表中。最后输出每个顶点对应的链表即可。