1.建立任意无向图,采用邻接矩阵存储,完成以下操作: (1)对该图进行深度优先遍历,并输出遍历结果; (2)对该图进行广度优先遍历,并输出遍历结果。
时间: 2024-02-18 08:03:21 浏览: 20
好的,我来为您解答这个问题。
首先,让我们来了解一下邻接矩阵。
邻接矩阵是一种用于表示图的方法,其中矩阵的行和列分别代表图中的顶点,矩阵中的元素代表两个顶点之间是否有边连接。如果顶点 i 和 j 之间有边连接,则邻接矩阵中第 i 行第 j 列的元素为 1;否则为 0。
下面是一个无向图的邻接矩阵表示:
```
0 1 2 3
0 0 1 1 0
1 1 0 1 1
2 1 1 0 1
3 0 1 1 0
```
其中,顶点 0、1、2、3 分别对应矩阵的行和列。
接下来,我们来讲解如何进行深度优先遍历和广度优先遍历。
深度优先遍历(Depth-First Search,DFS):从某个顶点出发,尽可能深地搜索图,直到无法继续为止,然后回溯到上一个顶点,再继续向下搜索,直到所有的顶点都被访问到为止。
广度优先遍历(Breadth-First Search,BFS):从某个顶点出发,依次访问其所有的邻居节点,然后再依次访问邻居节点的邻居节点,直到所有的顶点都被访问到为止。
下面是基于邻接矩阵实现的深度优先遍历和广度优先遍历的代码示例(使用 Python 语言实现):
```python
# 定义一个邻接矩阵表示的无向图
graph = [[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 0]]
# 深度优先遍历
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in range(len(graph)):
if graph[v][i] == 1 and not visited[i]:
dfs(graph, i, visited)
# 广度优先遍历
def bfs(graph, start):
queue = [start]
visited = [False] * len(graph)
visited[start] = True
while queue:
v = queue.pop(0)
print(v, end=' ')
for i in range(len(graph)):
if graph[v][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
# 测试代码
visited = [False] * len(graph)
dfs(graph, 0, visited)
print()
bfs(graph, 0)
```
运行结果如下:
```
0 1 2 3
0 1 2 3
```
其中,第一行是深度优先遍历的结果,第二行是广度优先遍历的结果。
希望我的回答能够帮助到您,若有疑问,请随时提出。