图数据结构-图深度遍历和广度遍历
程序员文章站
2022-06-06 21:56:43
...
一,图的两种算法
本章承接上一章 具体的一些说明或者资料可以到上一章中寻找
1, 深度优先遍历
说深度优先遍历之前 我们先说说走迷宫的走法,
要探索迷宫中所有的通道,我们需要做以下几种事,
1):选择一条没有标记过的通道,在你走过的路上铺一条绳子;
2):标记所有你第一次路过的路口和通道;
3):当来到一个标记的路口(有绳子的路口)时回退到上一个路口
4):当回退到的路口已经没有可走的通道时继续回退。
这样绳子可以保证你总能找到一条出路,标记保证了你不会两次同时经历一条通道
代码如下
package com.lxy.datastructure.graph; public class DepthFirstSearch { private boolean[] marked;//是否被访问过 private int count;//与s联通的顶点 public DepthFirstSearch(Graph g,int s) { marked=new boolean[g.getV()]; dfs(g,s); } private void dfs(Graph g,int v){ marked[v]=true; count++; for(int w:g.adj(v)){ if(!marked(w))dfs(g, w); } } public boolean marked(int w){ return marked[w]; } public int count(){ return count; } }
2,广度优先遍历
1,取队列中的下一个顶点v并标记它
2,将与v相邻的所有未被标记的顶点加入;
重复以上步骤
代码如下
package com.lxy.datastructure.graph; import com.lxy.datastructure.queue.Queue; import com.lxy.datastructure.stack.Stack; public class BreadthFirstPaths { private boolean[] marked;//访问标记 private int[] edgeTo;// private int s;//起点 public BreadthFirstPaths(Graph g,int s){ this.s=s; marked=new boolean[g.getV()]; edgeTo=new int[g.getV()]; bfs(g,s); } private void bfs(Graph g,int v){ Queue<Integer> queue=new Queue<Integer>(); marked[v]=true; queue.push(v); while(!queue.isEmpty()){ int h=queue.pop(); for(int w:g.adj(h)){ if(!marked(w)){ queue.push(w); marked[w]=true; edgeTo[w]=h; } } } } public boolean marked(int v){ return marked[v]; } public boolean hasPathTo(int v){ return marked[v]; } public Iterable<Integer> pathTo(int v){ if(!hasPathTo(v)) return null; Stack<Integer> path=new Stack<Integer>(); for(int x=v;x!=s;x=edgeTo[x]){ path.push(x); } path.push(s); return path; } }
测试用例
package com.lxy.datastructure.graph; import java.io.File; import java.util.Arrays; import java.util.Iterator; import org.junit.Before; import org.junit.Test; import com.lxy.datastructure.queue.Queue; import edu.princeton.cs.introcs.In; import edu.princeton.cs.introcs.StdOut; public class GraphTest { String basePath=System.getProperty("user.dir"); File file1=null; File file2=null; Graph g1 =null; @Before public void setup(){ file1=new File(basePath,"data/graph/mediumG.txt"); file2=new File(basePath,"data/graph/tinyG.txt"); In in = new In(file2); g1=new Graph(in); } @Test public void testPrintGraph(){ System.out.println(g1.toString()); } /** * 深度优先遍历 */ @Test public void depthFirstPath(){ int s =0; DeptFirstPaths path=new DeptFirstPaths(g1, s); for (int v = 0; v < g1.getV(); v++) { if (path.hasPathTo(v)) { StdOut.printf("%d to %d: ", s, v); for (int x : path.pathTo(v)) { if (x == s) StdOut.print(x); else StdOut.print("-" + x); } StdOut.println(); } else { StdOut.printf("%d to %d: not connected\n", s, v); } } System.out.println(Arrays.toString(path.getEdgeTo())); for(Iterator<Integer> it=path.pathTo(6).iterator();it.hasNext();){ System.out.println(it.next()); } } /** * 广度优先遍历 */ @Test public void testBreadthFirstPath(){ int s =0; BreadthFirstPaths path=new BreadthFirstPaths(g1, s); for (int v = 0; v < g1.getV(); v++) { if (path.hasPathTo(v)) { StdOut.printf("%d to %d: ", s, v); for (int x : path.pathTo(v)) { if (x == s) StdOut.print(x); else StdOut.print("-" + x); } StdOut.println(); } else { StdOut.printf("%d to %d: not connected\n", s, v); } } } }
输出结果
广度优先遍历输出结果 0 to 0: 0 0 to 1: 0-1 0 to 2: 0-2 0 to 3: 0-5-3 0 to 4: 0-5-4 0 to 5: 0-5 0 to 6: 0-6 0 to 7: not connected 0 to 8: not connected 0 to 9: not connected 0 to 10: not connected 0 to 11: not connected 0 to 12: not connected 深度优先遍历输出结果 0 to 0: 0 0 to 1: 0-1 0 to 2: 0-2 0 to 3: 0-5-4-3 0 to 4: 0-5-4 0 to 5: 0-5 0 to 6: 0-5-4-6 0 to 7: not connected 0 to 8: not connected 0 to 9: not connected 0 to 10: not connected 0 to 11: not connected 0 to 12: not connected
上一篇: jvm知识点-java内存模型
下一篇: jvm知识点-内存结构区