图数据结构-图深度遍历和广度遍历

一,图的两种算法

  本章承接上一章 具体的一些说明或者资料可以到上一章中寻找

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