图论--深度优先遍历DFS

深度优先搜素一个作用 ： 找出一幅图中连通分量


 1 package Graph;
 2 /**深度优先遍历 递归的遍历 类似从根结点一直遍历到整副图*/
 3 public class DepthFirstPath {
 4     public  Graph G;
 5     public boolean [] marked;
 6     private int[] edgeTo;// 记录根结点到其点顶点的路径
 7     private int startpoint;
 8     public DepthFirstPath(Graph G,int s)
 9     {
10         this.G=G;
11         marked=new boolean[G.Vertex];//结点起始点从1开始
12         edgeTo=new int[G.Vertex];
13         this.startpoint=s;
14         dfs(G,s);
15         PrintPath(edgeTo);
16     }
17     public void PrintPath(int [] edgepath)
18     {
19         System.out.println();
20         for (int i=edgepath.length-1;i>=0;i--)
21         {    
22           System.out.print(i + "顶点到 0结点路径"+"  ");
23           for(int x=i;x!=startpoint;x=edgepath[x] )
24            { //反向遍历
25               System.out.print(x +" ");
26             
27            }
28           System.out.print(startpoint);
29           System.out.println();
30         }
31         System.out.println();
32     }
33     public void dfs(Graph G, int w)
34     {
35         marked[w]=true;
36         EdgeNode edge=G.graph[w].firstedge;
37          while(edge!=null)
38          {
39              if(!marked[edge.adjvex])
40                 
41                  {   
42                      dfs(G,edge.adjvex);
43                       edgeTo[edge.adjvex]=w;// 他的入度结点是
44                       System.out.print(edge.adjvex + " ");
45                  }
46              edge=edge.nextedge;
47          }
48         
49         
50     }
51     public static void main(String[] args) {
52         // TODO Auto-generated method stub
53             int array[][]={{0,1},{0,2},{0,5},{1,2},{5,3},{3,2},{3,4}};
54             int []weight={1,2,3,4,5,6,7};
55             int []vNum={0,1,2,3,4,5};
56             Graph G=new Graph(vNum,weight.length,array,weight);
57             G.PrintGraph(G.graph);
58             DepthFirstPath  d=new DepthFirstPath (G,0);
59             
60             
61     }

public void pathTo(int v,int start)
{
/**打印一结点到其他结点上的路径*/
Stack<Integer> path=new Stack<Integer>();
for(int i=v;i!=startpoint;i=edgeTo[i])
path.push(i);
path.push(start);

while(!path.isEmpty())
{
System.out.print(path.pop() +" ");
}
}

62 
63 }

0-->(1,1)  (2,2)  (5,3)  
1-->(2,4)  (0,1)  
2-->(0,2)  (1,4)  (3,6)  
3-->(2,6)  (4,7)  (5,5)  
4-->(3,7)  
5-->(3,5)  (0,3)  
4 5 3 2 1 
5顶点到 0结点路径  5 3 2 1 0
4顶点到 0结点路径  4 3 2 1 0
3顶点到 0结点路径  3 2 1 0
2顶点到 0结点路径  2 1 0
1顶点到 0结点路径  1 0
0顶点到 0结点路径  0