`
lovnet
  • 浏览: 6670393 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

java算法:图遍历(深度优先和广度优先)

 
阅读更多

java算法:图遍历

递归图形遍历或深度优先搜索,系统地访问图中所有的结点的方法,如,树的遍历,也是很多递归算法的基础。

访问v,递归地访问每个附属于v的(未访问过的)结点,如果图是连通的,则最终能到达所有的结点。

例1:深度优先搜索

Java代码 复制代码
  1. privatevoiddfs(intk){
  2. visit(k);
  3. visited[k]=true;
  4. for(Nodet=adj[k];t!=null;t=t.next){
  5. if(!visited[t.v]){
  6. dfs(t.v);
  7. }
  8. }
  9. }

使用邻接表表示法在具有V个顶点和E条边的图中进行深度优先搜索所需要的时间与V+E成比例。

例2:广度优先搜索

Java代码 复制代码
  1. voidbfs(intk){
  2. IntQueueq=newIntQueue(v*v);
  3. q.put(k);
  4. while(!q.empty()){
  5. if(!visited[k=q.get()]){
  6. Nodet;
  7. visit(k);
  8. visited[k]=true;
  9. for(t=adj[k];t!=null;t=t.next){
  10. if(!visited[t.v]){
  11. q.put(t.v);
  12. }
  13. }
  14. }
  15. }
  16. }
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics