给定一个图,设计一个程序,从键盘输入数据建立图的邻接表存储,从该图的某一顶点开始进行深度优先遍历和广度优先遍历。
时间: 2024-02-18 09:05:50 浏览: 80
新建 DOC 文档_实现图的邻接矩阵和邻接表存储_doc_图的遍历算法_
5星 · 资源好评率100%
好的,这是一个比较复杂的问题,我会尽力回答。首先,我们需要明确图的基本概念。
图是由节点(也称为顶点)和边组成的数据结构,通常用 G = (V, E) 表示,其中 V 表示节点的集合,E 表示边的集合。如果边是有向的,那么我们称之为有向图;如果边是无向的,那么我们称之为无向图。
邻接表是一种常见的图的存储方式,它将每个节点的所有邻居节点存储在一个链表中。对于无向图,邻接表中只需存储一条边就可以了;对于有向图,邻接表需要存储两条边,一条表示出边,一条表示入边。
接下来,我们可以按照以下步骤实现你所需的程序:
1. 定义节点类和边类。节点类中需要包含节点的名称和邻居节点列表,边类中需要包含起点和终点节点。
```python
class Node:
def __init__(self, name):
self.name = name
self.neighbors = []
class Edge:
def __init__(self, start, end):
self.start = start
self.end = end
```
2. 从键盘输入数据建立图的邻接表存储。我们可以定义一个函数,依次读入每个节点和它的邻居节点,并将它们加入邻接表中。
```python
def build_graph():
graph = {}
n = int(input("Enter the number of nodes: "))
for i in range(n):
name = input("Enter the name of node {}: ".format(i+1))
node = Node(name)
graph[name] = node
m = int(input("Enter the number of edges: "))
for i in range(m):
start_name = input("Enter the start node of edge {}: ".format(i+1))
end_name = input("Enter the end node of edge {}: ".format(i+1))
start_node = graph[start_name]
end_node = graph[end_name]
edge = Edge(start_node, end_node)
start_node.neighbors.append(end_node)
# 如果是无向图,需要加上下面这行代码
# end_node.neighbors.append(start_node)
return graph
```
3. 进行深度优先遍历。深度优先遍历是一种递归算法,它从起点节点开始,依次遍历它的所有邻居节点,直到遍历完整个图。为了防止死循环,我们需要使用一个 visited 集合来记录已经遍历过的节点。
```python
def dfs(node, visited):
visited.add(node)
print(node.name)
for neighbor in node.neighbors:
if neighbor not in visited:
dfs(neighbor, visited)
def dfs_traversal(graph):
visited = set()
for name, node in graph.items():
if node not in visited:
dfs(node, visited)
```
4. 进行广度优先遍历。广度优先遍历是一种迭代算法,它从起点节点开始,依次遍历它的所有邻居节点,然后再遍历它们的邻居节点,以此类推。为了实现这个算法,我们需要使用一个队列来保存待遍历的节点。
```python
from collections import deque
def bfs_traversal(graph):
visited = set()
queue = deque()
for name, node in graph.items():
if node not in visited:
visited.add(node)
queue.append(node)
while queue:
curr_node = queue.popleft()
print(curr_node.name)
for neighbor in curr_node.neighbors:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
```
这样,我们就完成了从键盘输入数据建立图的邻接表存储,并进行深度优先遍历和广度优先遍历的程序。
阅读全文