数据结构之图的广度、深度优先搜索
程序员文章站
2022-05-20 19:07:09
...
数据结构:图的遍历
1.图的搜索方式分为两种:
深度优先搜索(dfs):
类似于树的先根遍历,每次访问完当前结点后首先访问当前结点的第一个
邻接点,是一个递归的过程
广度优先搜索(bfs):
类似于树的按层次遍历,每次访问完当前结点后继续访问当前结点的所有
邻接点,通常与队列配合使用
2.注意事项:
因 图结构 结点间的关系是多对多的,所以可能存在 回路,所以在遍历时需要
用数组visited[]记录所访问过的结点,防出现死循环
3.图的遍历(邻接矩阵存储)
private String[] vexs=new String[] {"A","B","C","D","E"};
private int[][] g=new int[][] {
{0,1,0,1,0},{1,0,1,0,1},{0,1,0,1,1},
{1,0,1,0,0},{0,1,1,0,0}
};
private boolean[] visited=new boolean[vexs.length];
//输出结点并将对应标志设置为已访问
public void visit(int v) {
visited[v]=true;
System.out.println(vexs[v]);
}
//深度优先搜索
public void dfs(int v) {
visit(v);
for(int i=0;i<g[v].length;i++) {
if(g[v][i]==1&&!visited[i])
dfs(i);
}
}
//广度优先搜索
public void bfs(int v) {
Queue<Integer> q=new LinkedList<Integer>();
visit(v);
q.add(v);
while(!q.isEmpty()) {
int head=q.poll();
for(int j=0;j<g[head].length;j++) {
if(g[head][j]==1&&!visited[j]) {
visit(j);
q.add(j);
}
}
}
}
4.小结
邻接矩阵的存储结构:顶点数组+关系矩阵
在遍历过程中,需记录结点访问记录
广度优先搜索时队列中存放的是已访问过的结点
若需经过多次的深度或广度搜索才能访问完所有的顶点,则图是一个非连通图
推荐阅读
-
python数据结构之图深度优先和广度优先实例详解
-
Python数据结构与算法之图的广度优先与深度优先搜索算法示例
-
可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析
-
数据结构与算法-----BFS与DFS(广度优先搜索与深度优先搜索)
-
数据结构与算法_深度优先搜索(DFS)与广度优先搜索(BFS)详解
-
Java数据结构与算法:图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
-
【数据结构】图的遍历——深度优先搜索DFS、广度优先搜索BFS
-
Java数据结构与算法——深度优先搜索与广度优先搜索
-
数据结构与算法——广度和深度优先搜索
-
数据结构与算法————图的遍历DFS深度优先搜索和BFS广度优先搜索