已知一个带权有向图,其存储结构为邻接表结构 ,设计一算法,由键盘输入数据,建立邻接表,并将其输出。 用例说明: 第一行输入图的顶点数; 第二行输入顶点信息; 第三行以后,按照顺序,每个顶点对应一行,按行输入该顶点对应边的信息(位置 1 权值 1 位置 2 权值 2 ……. ,以 -1 结束)。 输出格式中,代表链表节点的信息是:(边)权值,参见下面用例。例子:输入 4 a b c d 1 1 2 4 -1 2 2 3 9 -1 3 6 -1 0 3 1 5 2 8 -1,输出a (0,2)4 (0,1)1 b (1,3)9 (1,2)2 c (2,3)6 d (3,2)8 (3,1)5 (3,0)3
时间: 2024-01-25 09:04:17 浏览: 14
下面是Python的实现代码:
```python
class Node:
def __init__(self, v, w):
self.v = v
self.w = w
self.next = None
class Graph:
def __init__(self):
self.head = []
def add_edge(self, u, v, w):
node = Node(v, w)
node.next = self.head[u]
self.head[u] = node
def print_graph(self, vertexes):
for i in range(vertexes):
print(chr(i + ord('a')), end=' ')
node = self.head[i]
while node:
print(f"({node.v}, {node.w})", end=' ')
node = node.next
print()
if __name__ == '__main__':
vertexes = int(input())
vertex_info = input().split()
g = Graph()
for i in range(vertexes):
g.head.append(None)
for i in range(vertexes):
edges = list(map(int, input().split()))
j = 1
while edges[j] != -1:
g.add_edge(i, edges[j - 1], edges[j])
j += 2
g.print_graph(vertexes)
```
输入的第一行表示顶点数,第二行表示顶点信息,第三行以后是每个顶点对应的边信息。我们使用一个链表数组来存储邻接表,链表的节点是一个包含顶点和权值的元组。
在 `add_edge` 函数中,我们将边插入到对应顶点的链表头部。
在 `print_graph` 函数中,我们遍历每个顶点的链表,输出对应的边信息。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)