Go语言视频零基础入门到精通

javalearner

为图的每个顶点所发出的边建立一个单链表，用一顶点数组存储每个单链表的头指针。
   

   
   

   

   
   

    程序一:
   

   

    import java.util.*;
class VNode{
  int from;//边的起点
  Edge first;//以from为起点的第一条边
  public VNode(int from){
    this.from=from;
    first=null;
  }
}
class Edge{
   int to;//边的终点  
   Edge next;//具有同一起点的下一条边
   public Edge(int to){
     this.to=to;
     next=null;
   }
}
public class Graph{
   int k;//图的顶点数
   VNode[] V;//顶点数组
   boolean[] visted;//记录某个顶点是否遍历过
   public Graph(int k,VNode[] v){
      this.k=k;
      this.V=v;
      visted = new boolean[k];
   }
   //从v0顶点出发广度优先遍历图
   private void BFS(int v0){
     Queue<Integer> que=new LinkedList<Integer>();
     que.add(v0);
     while(!que.isEmpty()){
       v0=que.poll();
       if(!visted[v0]){
          System.out.print(v0+"  ");
          visted[v0]=true;
       }
      Edge e=V[v0].first;
      while(e!=null){
          if(!visted[e.to]) que.add(e.to);
          e=e.next;
      }
     }
  }
  //邻接表深度优先搜索图
   private void DFS(int v0){
     visted[v0]=true;
     //访问顶点v0
     System.out.print(v0+"  ");
   
     Edge p=V[v0].first;
     while(p!=null){
       if(!visted[p.to]){
          DFS(p.to);
       }
       p=p.next;
    }
  }
  public static void main(String[] args){
     Scanner sc=new Scanner(System.in);
     int k=sc.nextInt();//图的顶点数
     int m=sc.nextInt();//图的边数
      VNode[] V=new VNode[k];
      for(int i=0;i<k;i++)
          V=new VNode(i);
      Edge e=null;Edge e1=null;
      int u=0;int v=0;
      for(int i=0;i<m;i++){
         u=sc.nextInt();//起点
         v=sc.nextInt();//终点
        e=new Edge(v);
        e.next=V.first;//插入到链表开头
        V.first=e;
       //对于无向图作对称处理
         e1=new Edge(u);
         e1.next=V[v].first;
         V[v].first=e1;
       }
       Graph gra=new Graph(k,V);
      // gra.BFS(0);
       gra.DFS(0);
     }
}     
[/code]
   

   

   
   

   

   
程序运行：
   
C:java>java  Graph
   
6
   
10
   
0 1
   
0 2
   
0 3
   
1 2
   
1 4
   
2 4
   
2 5
   
2 3
   
3 5
   
4 5
   
0  3  2  1  5  4(广搜）
   

   

   
C:java>java  Graph
   
6
   
10
   
0 1
   
0 2
   
0 3
   
1 2
   
1 4
   
2 4
   
2 5
   
2 3
   
3 5
   
4 5
   
0  3  5  4  2  1（深搜）
   

    程序二：
   

   

   

1. //邻接表实现图的广搜和深搜
   
2. import java.util.*;
   
3. public class Graph{
   
4.         static class Edge implements Comparable< Edge> {
   
5.                 int to;// 边的终点
   
6.                 public Edge(int t) {
   
7.                         to = t;
   
8.                 }
   
9.                 @Override
   
10.                 public int compareTo(Edge o) {
    
11.                         return to - o.to;
    
12.                 }
    
13.         }
    
14.         static class VNode {
    
15.                 int from;// 边的起点
    
16.                 PriorityQueue< Edge> pri = new PriorityQueue< Edge>();
    
17.                 public VNode(int v) {
    
18.                         from = v;
    
19.                 }
    
20.         }
    
21.       
    
22.         private VNode[] V;
    
23.         private int k;// 图的顶点个数
    
24.         private boolean[] visited;
    
25.         private boolean isfirst;
    
26.         public Graph(int k,VNode[] V){
    
27.                 this.V=V;
    
28.                 visited = new boolean[k];
    
29.                 isfirst = true;
    
30.         }
    
31.         public static void main(String[] args) {
    
32.                 Scanner sc = new Scanner(System.in);
    
33.                 int n;
    
34.                 n = sc.nextInt();
    
35.                 while (n-- > 0) {
    
36.                         int k = sc.nextInt();
    
37.                         int m = sc.nextInt();
    
38.                         int t = sc.nextInt();
    
39.                        
    
40.                         VNode[] V = new VNode[k];
    
41.                         for (int i = 0; i < k; i++)
    
42.                                 V[i] = new VNode(i);
    
43.                         for (int i = 0; i < m; i++) {
    
44.                                 int u = sc.nextInt();// 起点
    
45.                                 int v = sc.nextInt();// 终点
    
46.                                 Edge e = new Edge(v);
    
47.                                 V[u].pri.add(e);
    
48.                                 // 无向图的对称
    
49.                                 e = new Edge(u);
    
50.                                 V[v].pri.add(e);
    
51.                         }
    
52.                         //new Graph(k,V).bfs(t);
    
53.                         new Graph(k,V).dfs(t);
    
54.                         System.out.println();
    
55.                 }
    
56.         }
    
57.         // 广搜
    
58.         public  void bfs(int v0) {
    
59.                 boolean isfirst = true;
    
60.                 Queue< Integer> que = new LinkedList< Integer>();
    
61.                 que.add(v0);
    
62.                 while (!que.isEmpty()) {
    
63.                         v0 = que.poll();
    
64.                         if (!visited[v0]) {
    
65.                                 if (isfirst) {
    
66.                                         System.out.print(v0);
    
67.                                         isfirst = false;
    
68.                                 } else
    
69.                                         System.out.print(" " + v0);
    
70.                                 visited[v0] = true;
    
71.                         }
    
72.                        
    
73.                         while (!V[v0].pri.isEmpty()) {
    
74.                                 Edge e = V[v0].pri.poll();// 得到以v0为起点的终点链表
    
75.                                 if (!visited[e.to])
    
76.                                         que.add(e.to);
    
77.                         }
    
78.                 }
    
79.         }
    
80.         // 深搜
    
81.         public  void dfs(int v0) {
    
82.                // System.out.println("深搜");
    
83.                 visited[v0] = true;
    
84.                 if (isfirst) {
    
85.                         System.out.print(v0);
    
86.                         isfirst = false;
    
87.                 } else
    
88.                         System.out.print(" " + v0);
    
89.                
    
90.                 while (!V[v0].pri.isEmpty()) {
    
91.                         Edge p = V[v0].pri.poll();
    
92.                         if (!visited[p.to])
    
93.                                 dfs(p.to);
    
94.                 }
    
95.         }
    
96. }
    

复制代码

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/12/5/001031765.rar