输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表示的无向图。 (2)对图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。
时间: 2023-12-14 15:40:13 浏览: 98
好的,这是一个图论问题,需要用到图的相关知识和算法。
首先,让我们来了解一下无向图和邻接表的概念:
无向图:由n个顶点和m条边组成的图,若图中任意两个顶点之间的边都是无向边,则称该图为无向图。
邻接表:邻接表是一种图的存储结构,它把每个顶点的所有邻接点存储起来,每个顶点对应一条链表,链表中存储该顶点的所有邻接点。
接下来,根据题目要求,我们可以编写如下代码来建立邻接表表示的无向图:
```python
# 输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表示的无向图
n, m = map(int, input().split()) # 顶点数和边数
graph = [[] for _ in range(n)] # 邻接表,每个顶点对应一个列表存储其邻接点
for i in range(m):
u, v = map(int, input().split()) # 顶点对
graph[u].append(v) # 添加v到u的邻接表中
graph[v].append(u) # 添加u到v的邻接表中
```
接下来,我们来实现深度优先搜索和广度优先搜索算法。
深度优先搜索(DFS):从起点开始,沿着一条路径直到不能再走为止,然后回溯到上一个节点,继续走未走过的路径,直到遍历完整个图。可以使用递归或栈实现。
广度优先搜索(BFS):从起点开始,先访问与其相邻的所有节点,然后依次访问与这些节点相邻的节点,直到遍历完整个图。可以使用队列实现。
下面是深度优先搜索和广度优先搜索的代码实现:
```python
# 深度优先搜索
def dfs(u, visited, res):
visited[u] = True # 标记该节点已被访问
res.append(u) # 将该节点加入遍历序列
for v in graph[u]: # 遍历u的所有邻接点
if not visited[v]:
dfs(v, visited, res) # 递归访问v
# 广度优先搜索
def bfs(u, visited, res):
queue = [u] # 存储待访问的节点
visited[u] = True # 标记该节点已被访问
while queue:
u = queue.pop(0) # 取出队首节点
res.append(u) # 将该节点加入遍历序列
for v in graph[u]: # 遍历u的所有邻接点
if not visited[v]:
queue.append(v) # 将未访问的邻接点加入队列
visited[v] = True # 标记该节点已被访问
```
最后,我们可以调用上面的函数进行遍历,并输出遍历序列:
```python
visited = [False] * n # 记录节点是否被访问过
res_dfs, res_bfs = [], []
for i in range(n):
if not visited[i]:
dfs(i, visited, res_dfs) # 从i节点开始进行深度优先遍历
bfs(i, visited, res_bfs) # 从i节点开始进行广度优先遍历
print(' '.join(map(str, res_dfs))) # 输出深度优先遍历序列
print(' '.join(map(str, res_bfs))) # 输出广度优先遍历序列
```
以上就是本题的完整代码实现。
阅读全文