图（邻接表）

/**
 * 文件名：Graph.java
 * 时间：2014年11月13日下午4:51:12
 * 作者：修维康
 */
package chapter9;

import java.util.*;

/**
 * 类名：Graph 说明：
 */
class Vertex
  
    {
	public AnyType value;
	public int indegree = 0;// 顶点的入度，拓扑排序的时候用到
	public LinkedList
   
     adjacent = new LinkedList
    
     (); public int topNum = 0;// 拓扑排序 private int size = 0; private int index = 0; public int dist = Integer.MAX_VALUE;// 到一个顶点的距离,开始默认都不可达 public boolean visited = false; public Vertex path = null; public Vertex(AnyType value) { this.value = value; } public void addAdj(Vertex v) { v.indegree++; adjacent.add(v); size++; } public Vertex next() { return adjacent.get(index++); } public boolean hasAdj() { int temp = index;//定义一个临时的变量，使其到尾部的时候在指向0 if(index == size) index = 0; return temp != size; } } class Graph { public ArrayList
     
      > vList = new ArrayList
      
       >(); public Graph() { Vertex
       
         v1 = new Vertex
        
         (1); Vertex
         
           v2 = new Vertex
          
           (2); Vertex
           
             v3 = new Vertex
            
             (3); Vertex
             
               v4 = new Vertex
              
               (4); Vertex
               
                 v5 = new Vertex
                
                 (5); Vertex
                 
                   v6 = new Vertex
                  
                   (6); Vertex
                   
                     v7 = new Vertex
                    
                     (7); v1.addAdj(v2); v1.addAdj(v3); v1.addAdj(v4); v2.addAdj(v4); v2.addAdj(v5); v3.addAdj(v6); v4.addAdj(v3); v4.addAdj(v6); v4.addAdj(v7); v5.addAdj(v4); v5.addAdj(v7); v7.addAdj(v6); vList.add(v1); vList.add(v2); vList.add(v3); vList.add(v4); vList.add(v5); vList.add(v6); vList.add(v7); } public String toString() { StringBuffer s = new StringBuffer(); Iterator
                     
                      > ite = vList.iterator(); System.out.println("v1 v2 v3 v4 v5 v6 v7 "); while (ite.hasNext()) s.append(ite.next().topNum + " "); return new String(s); } public String printDist() { StringBuffer s = new StringBuffer(); Iterator
                      
                       > ite = vList.iterator(); System.out.println("v1 v2 v3 v4 v5 v6 v7 "); while (ite.hasNext()) s.append(ite.next().dist + " "); return new String(s); } } public class GraphTest { /** * 方法名：topSort 说明：拓扑排序 是对无环图进行的 */ public static void topSort(Graph graph) { Queue
                       






                        > q = new LinkedList
                        
                         >(); Vertex v = findIndegreeZero(graph); if (v == null) { System.out.println("该图有环，无法进行拓扑排序"); return; } q.add(v); int count = 0; while (!q.isEmpty()) { Vertex w = q.poll(); w.topNum = ++count; while (w.hasAdj()) { Vertex e = w.next(); if (--e.indegree == 0) q.add(e); } } } private static Vertex
                         
                           findIndegreeZero(Graph graph) { for (Vertex
                          
                            v : graph.vList) { if (v.indegree == 0) return v; } return null; } /** * 方法名：unWeighted 说明：无权的最短路径 */ public static void unWeighted(Vertex s) { Queue
                           
                            > q = new LinkedList
                            
                             >(); s.dist = 0; q.add(s); while (!q.isEmpty()) { Vertex
                             
                               v = q.poll(); while (v.hasAdj()) { Vertex
                              
                                w = v.next(); if (!w.visited) { w.dist = v.dist + 1; w.visited = true; q.add(w); } } } } public static void main(String[] args) { Graph g = new Graph(); topSort(g); System.out.println(g); unWeighted(g.vList.get(0));// 各个顶点到0的路径； System.out.println(g.printDist()); } }