(3)设计一段程序,通过扫描graph.txt,在计算机内存中创建一张对应的有向图。对于“邻接表”,可以按照“出边”、“入边”、或者“出边+入边”的方式构建与每一个顶点相关联的边的链表。
时间: 2023-08-25 11:04:20 浏览: 36
以下是一个简单的 Python 程序,可以读取 graph.txt 文件,并在内存中创建一个有向图,使用邻接表表示法以出边的方式构建每个顶点相关联的边的链表。
```python
class Node:
def __init__(self, val):
self.val = val
self.next = None
class Graph:
def __init__(self):
self.adj_list = {}
def add_edge(self, src, dest):
if src not in self.adj_list:
self.adj_list[src] = None
new_node = Node(dest)
new_node.next = self.adj_list[src]
self.adj_list[src] = new_node
def print_graph(self):
for vertex in self.adj_list:
print(vertex, end=": ")
head = self.adj_list[vertex]
while head:
print(f"{head.val} ->", end=" ")
head = head.next
print("None")
graph = Graph()
# 读取 graph.txt 文件
with open("graph.txt") as f:
for line in f:
src, dest = map(int, line.strip().split())
graph.add_edge(src, dest)
# 打印有向图
graph.print_graph()
```
假设 graph.txt 文件中包含以下内容:
```
1 2
1 3
2 4
3 4
4 1
```
程序的输出应该是:
```
1: 3 -> 2 -> None
2: 4 -> None
3: 4 -> None
4: 1 -> None
```
可以看到,程序成功地读取了 graph.txt 文件的内容,并在内存中创建了一个有向图。通过邻接表表示法以出边的方式构建每个顶点相关联的边的链表,程序成功地将有向图打印了出来。
相关推荐
![](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)
![](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)