欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 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