用Python或者c语言 写广度优先和深度优先搜索
用Python或者c语言 写广度优先和深度优先搜索 图（图用邻接矩阵表示）
矩阵代码如下
图一是BFS（广度优先搜索）在树的情况下的执行过程，从A出发，搜索A的第二层，发现有B，C，D（必须从左到右搜索），再搜索B的第二层，发现B的第二层没有元素，再搜索C的第二层，发现有E，F，放置于D后面，再搜索D的第二层，发现有G，放置于F后面，再往下搜索E，F，G，发现只有G有第二层H和I，所以最后得到：
A B C D E F G H I
图二是BFS（广度优先搜索）在图的情况下的执行过程，假设从A出发，第二层是B和C，先搜索B的第二层，发现有D，再搜索C的第二层，发现只有E了，最后D，E中只有D有第二层F，所以最后得到：
A B C D E F
⚠️：这里不可以是：A B C E D F，因为必须先搜索B的第二层再搜索C的第二层
同理以E为起始点可以得到：E C D A B F（不同的起始点的路径不同）
BFS在python中实现运用了Queue（队列）将搜索结果进行排列
DFS（深度优先搜索）：
图4 DFS
图5 stack of DFS
图4是DFS（深度优先搜索）在图的情况下的执行过程，其规则是从起始点往下走，走到底再返回，直到走完所有点：
从起始点A出发->B->C->D->F(此时到底了，返回)->E->C(此时所有点都走完了)
DFS在python中实现运用了Stack（栈）将搜索结果进行堆砌：
将起始点A先放入栈->拿出A，A后可以选择走B和C->将B，C放入栈->拿出B，B之后只能走D->将D放入栈->拿出D，D之后可以走E，F->将E，F放入栈->拿出F，F之后到底了->无放入->拿出E->拿出C
最后得到 A B D F E C （不同的起始点的路径不同）
完整python代码解析
从‘A’出发:
BFS得到A B C D E F (答案不唯一)
DFS得到A B D F E C (答案不唯一）
用字典的映射去表示图2
>>> graph = {
... 'A': ['B', 'C'],
... 'B': ['A', 'C', 'D'],
... 'C': ['A', 'B', 'D', 'E'],
... 'D': ['B', 'C', 'E', 'F'],
... 'E': ['C', 'D'],
... 'F': ['D']
... }
>>> graph.keys()-------返回图上所有节点的名称，顺序不固定
dict_keys(['A', 'B', 'C', 'D', 'E', 'F'])
>>> graph['E']------看看E的连接点
['C', 'D']
1
2
3
4
5
6
7
8
9
10
11
12
13
数组可以动态加东西，用append()，动态删东西用pop()
>>> queue = []
>>> queue.append('A')---在列表末端添加元素
>>> queue.append('B')
>>> queue.append('C')
>>> queue
['A', 'B', 'C']
>>> queue.pop(0)---删除第一个元素并返回
'A'
>>> queue
['B', 'C']
>>> queue.pop()----删除最后一个元素并返回
'C'
>>> queue
['B']
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
graph = {
'A': ['B', 'C'],
'B': ['A', 'C', 'D'],
'C': ['A', 'B', 'D', 'E'],
'D': ['B', 'C', 'E', 'F'],
'E': ['C', 'D'],
'F': ['D']
}
# input一个graph和起始点s
def BFS(graph, s):
#创建队列
queue = []
#将起始点s放入队列，假设起始点为‘A’
queue.append(s)
#set():创建一个无序不重复元素集，可进行关系测试，删除重 复数据,还可以计算交集、差集、并集
seen = set()
#'A'我们已经见过，放入seen
seen.add(s)
#当队列不是空的时候
while len(queue) > 0:
#将队列的第一个元素读出来，即‘A’
vertex = queue.pop(0)
#graph['A']就是A的相邻点：['B','C'],将其储存到nodes
nodes = graph[vertex]
#遍历nodes中的元素，即['B','C']
for w in nodes:
#如果w没见过
if w not in seen:
queue.append(w)
#加入seen表示w我们看见过了
seen.add(w)
print(vertex)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
执行过程：
step 1:queue=[‘A’]->seen=[‘A’]->queue=[ ]->vertex=‘A’->nodes=[‘B’,‘C’]->queue=[‘B’,‘C’]->seen=[‘A’,‘B’,‘C’]->return ‘A’
step 2:vertex=‘B’->queue=[‘C’]->nodes=[‘A’, ‘C’, ‘D’]->queue=[‘C’‘D’]->seen=[‘A’,‘B’,‘C’,‘D’]->return’B’
step 3:vertex=‘C’->queue=[‘D’]->nodes=[‘A’, ‘B’, ‘D’, ‘E’]->queue=[‘D’‘E’]->seen=[‘A’,‘B’,‘C’,‘D’‘E’]->return’C’
…
"DFS的方法就是将BFS中的队列改成栈即可"
def DFS(graph, s):
stack = []
stack.append(s)
seen = set()
seen.add(s)
while len(stack) > 0:
vertex = stack.pop()
nodes = graph[vertex]
for w in nodes:
if w not in seen:
stack.append(w)
seen.add(w)
print(vertex)
print(DFS(graph, 'A'))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
求最短路径问题：
求A到E的最短路径，我们用parent建一个表，表显示每个点的前一个点是哪个点，这样我们先找E的前一个点为C，C的前一个点为A，A前没有点了，因此A到E的最短路径为A->C->E
# 用字典表示S的前一个点为空
parent = {s: None}
之前w的前一个点就是vertex，因此：
parent[w] = vertex
将这两行代码加入之前的代码中：
1
2
3
4
5
完整代码为：
def BFS(graph, s):
queue = []
queue.append(s)
seen = set()
seen.add(s)
parent = {s: None}
while len(queue) > 0:
vertex = queue.pop(0)
nodes = graph[vertex]
for w in nodes:
if w not in seen:
queue.append(w)
seen.add(w)
parent[w] = vertex
print(vertex)
return parent
"测试从‘E’出发"
parent = BFS(graph, 'E')
for key in parent:
print(key, parent[key])
DFS深度优先搜索实现代码：
#include <stdio.h>
#include <stdlib.h>
#define MAXV 4
// 定义图的邻接矩阵
typedef struct {
int verNum, egdeNum; // 顶点个数、边条数
char vertex[MAXV]; // 顶点
int matrix[MAXV][MAXV]; // 邻接矩阵
} MGraph;
// 初始化图
void Init_MGraph(MGraph &G) {
G.verNum = MAXV;
G.egdeNum = MAXV;
G.vertex[0] = 'A';
G.vertex[1] = 'B';
G.vertex[2] = 'C';
G.vertex[3] = 'D';
// 初始化邻接矩阵
int num[MAXV][MAXV] = {
{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}
};
for (int i = 0; i < MAXV; i++) {
for (int j = 0; j < MAXV; j++) {
G.matrix[i][j] = num[i][j];
}
}
}
// 寻找下一个相邻的顶点,存在则返回下标，否则返回-1
int FindNextVertex(MGraph &G, int vexRow, int* visited) {
if (vexRow >= G.verNum) {
return -1;
}
for (int i = 0; i < G.verNum; i++) {
if (G.matrix[vexRow][i] != 0 && !visited[i]) {
return i;
}
}
return -1;
}
// 寻找所有相邻的顶点,存在则返回下标，否则返回-1
int* FindAllNextVertex(MGraph &G, int vexRow, int* visited) {
if (vexRow >= G.verNum) {
return NULL;
}
int* num = (int *)malloc(G.verNum * sizeof(int));
for (int i = 0; i < G.verNum; i++) {
if (G.matrix[vexRow][i] != 0 && !visited[i]) {
num[i] = i;
} else {
num[i] = -1;
}
}
return num;
}
// DFS深度优先搜索
void DFS_MGraph(MGraph &G, int numSeq, int *visited, int flag) {
if (numSeq < G.verNum && !visited[numSeq]) {
printf("当前电影: %c, 序号: %d\n", G.vertex[numSeq], numSeq);
visited[numSeq] = 1;
// DFS 访问下一个顶点
if (flag) {
int seq = FindNextVertex(G, numSeq, visited);
if (seq != -1) {
DFS_MGraph(G, seq, visited, flag);
}
} else {
int* seq = FindAllNextVertex(G, numSeq, visited);
int num = 0;
for (int i = 0; i < G.verNum; i++) {
if(seq[i] != -1) {
num++;
}
}
if (num) {
printf("\n请从以下序号中选择观影顺序:\n");
for (int i = 0; i < G.verNum; i++) {
if(seq[i] != -1) {
printf("电影序号: %d\n", seq[i]);
}
}
int seq;
scanf("%d", &seq);
DFS_MGraph(G, seq, visited, flag);
}
free(seq);
}
}
}
void DFS(MGraph &G, int numSeq, int flag) {
int visited[MAXV];
// 初始化全局变量
for (int i = 0; i < MAXV; i++) {
visited[i] = 0;
}
DFS_MGraph(G, numSeq, visited, flag);
for (int i = 0; i < G.verNum; i++) {
if (!visited[i]) {
DFS_MGraph(G, i, visited, flag);
}
}
}
int main() {
MGraph G;
Init_MGraph(G);
int seq;
// DFS访问
printf("\n请输入开始访问的顶点序号(0-3):");
scanf("%d", &seq);
DFS(G, seq, 1);
// DFS看电影顺序
printf("\n请输入要观影的序号(0-3):");
scanf("%d", &seq);
DFS(G, seq, 0);
return 0;
}
具体运行效果：
图的广度和深度优先路径搜索算法(python实现)‘
可以借鉴下
https://blog.csdn.net/a15608445683/article/details/125803928
首先创建邻接矩阵，邻接矩阵的样式查了百度百科：
下面的函数就用于生成这样的一个邻接矩阵：
def creat_matrix():
nodes = ['Mary Poppins', 'The Sound of Music', 'Enchanted', 'Up', 'The Star', 'Arrival', 'Cars', 'Toy Story', 'Coco', 'Pinocchio']
Actors = ['J.A.','C.P.','A.A.','J.R.','T.H.','K.K.','T.A.']
Actors_Movie = [ ['Mary Poppins','The Sound of Music','Enchanted'],
['The Sound of Music','Up','The Star'],
['Enchanted','Arrival'],
['Up','Cars','Toy Story','Coco'],
['Toy Story','Pinocchio'],
['The Star','Pinocchio'],
['Toy Story','Cars']]
# matrix = [[0,1,0,1,0,0,0,0,0,0],
# [1,0,1,0,0,0,0,0,0,0],
# [0,1,0,0,0,0,0,0,0,0],
# [1,0,0,0,1,0,0,0,1,0],
# [0,0,0,1,0,1,0,0,0,1],
# [0,0,0,0,1,0,1,0,0,0],
# [0,0,0,0,0,1,0,1,1,0],
# [0,0,0,0,0,0,1,0,1,0],
# [0,0,0,1,0,0,1,1,0,1],
# [0,0,0,0,0,0,0,0,0,0]]
for i in range(len(nodes)):
Adjacency_Matrix.append([0]*len(nodes))
# 更新顶点相邻关系
for i in Actors_Movie:
for j in i:
for k in i:
if not k==j:
Adjacency_Matrix[nodes.index(j)][nodes.index(k)] = 1
# 邻接矩阵打印测试
# print(Adjacency_Matrix)
广搜和深搜算法的讲解我看下面有兄弟贴了链接，直接百度搜索也搜的到，这里我写了一个深搜的例子，针对这个题目的全部代码如下：
#邻接矩阵百度百科
#https://baike.baidu.com/item/%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5/9796080
# 创建一个空的列表作为邻接矩阵
Adjacency_Matrix = []
# 所有可行方案存入下面的列表中
movie_out_all=[]
def dfs(node_index,movie_list,step=1):
"""
node_index :整数型，指当前的节点（电影） 0-9分别对应 nodes列表中的十个电影
move_list: 一个列表，用作搜索过程中存储已列入计划的节点
step:整数型
"""
if step == 1:
movie_list[step-1] = node_index
reflash = 0
for i in range(len(Adjacency_Matrix[node_index])):
temp_list = movie_list[:step]
if Adjacency_Matrix[node_index][i] != 0 and i not in temp_list:
movie_list[step] = i
dfs(i,movie_list,step+1)
reflash = 1
if reflash == 0:
movie_list_out = movie_list[:step]
movie_out_all.append(movie_list_out)
print(movie_list_out)
def creat_matrix():
nodes = ['Mary Poppins', 'The Sound of Music', 'Enchanted', 'Up', 'The Star', 'Arrival', 'Cars', 'Toy Story', 'Coco', 'Pinocchio']
Actors = ['J.A.','C.P.','A.A.','J.R.','T.H.','K.K.','T.A.'] # 这个列表暂时没用上
Actors_Movie = [ ['Mary Poppins','The Sound of Music','Enchanted'],
['The Sound of Music','Up','The Star'],
['Enchanted','Arrival'],
['Up','Cars','Toy Story','Coco'],
['Toy Story','Pinocchio'],
['The Star','Pinocchio'],
['Toy Story','Cars']]
# matrix = [[0,1,0,1,0,0,0,0,0,0],
# [1,0,1,0,0,0,0,0,0,0],
# [0,1,0,0,0,0,0,0,0,0],
# [1,0,0,0,1,0,0,0,1,0],
# [0,0,0,1,0,1,0,0,0,1],
# [0,0,0,0,1,0,1,0,0,0],
# [0,0,0,0,0,1,0,1,1,0],
# [0,0,0,0,0,0,1,0,1,0],
# [0,0,0,1,0,0,1,1,0,1],
# [0,0,0,0,0,0,0,0,0,0]]
for i in range(len(nodes)):
Adjacency_Matrix.append([0]*len(nodes))
# 更新顶点相邻关系
for i in Actors_Movie:
for j in i:
for k in i:
if not k==j:
Adjacency_Matrix[nodes.index(j)][nodes.index(k)] = 1
# 邻接矩阵打印测试
# print(Adjacency_Matrix)
if __name__ == "__main__":
creat_matrix() # 生成矩阵用
movie_list=[0]*len(Adjacency_Matrix[0]) # 用于搜索过程中存储可行的节点（电影）
index = input("请输入首先要看的电影序号（0-9）:")
dfs(int(index),movie_list) # 深搜
# print("所有可行的看电影规划：")
# print(movie_out_all)
运行结果：
关于题目中所说的“当有多个选项时让用户选择”这一功能，请自行完善添加。
代码中或有不规范的地方还望指正，有什么疑问可以继续互相交流。
python实现：
# 定义图
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
def bfs(graph, start, end):
# 创建一个队列，用于存储需要访问的结点
queue = []
# 将源点加入队列
queue.append(start)
# 创建一个集合，用于存储已访问的结点
visited = set()
# 循环遍历队列
while queue:
# 从队列中取出队首结点
node = queue.pop(0)
# 判断是否到达目标点
if node == end:
return True
# 将队首结点的所有相邻结点加入队列
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
# 未找