? 本章承接上一章?具体的一些说明或者资料可以到上一章中寻找
1， 深度优先遍历
? ?说深度优先遍历之前 我们先说说走迷宫的走法，
?要探索迷宫中所有的通道，我们需要做以下几种事，
1）：选择一条没有标记过的通道，在你走过的路上铺一条绳子；
2）：标记所有你第一次路过的路口和通道；
3）：当来到一个标记的路口（有绳子的路口）时回退到上一个路口
4）：当回退到的路口已经没有可走的通道时继续回退。
这样绳子可以保证你总能找到一条出路，标记保证了你不会两次同时经历一条通道
?代码如下
class="java">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
?
相关文章
