java实现数据结构图

考虑一个任务安排的例子，比如有很多任务T1,T2,....
这些任务又是相互关联的，比如Tj完成前必须要求Ti已完成，这样T1,T2....序列关于这样的先决条件构成一个图，其中如果Ti必须要先于Tj完成，那么<Ti,Tj>就是该图中的一条路径，路径长度为1的就是一条边。
拓扑排序就是把这些任务按照完成的先后顺序排列出来。显然，这样的顺序可能不是唯一的，比如Tk，Tl如果没有在一条路径上，那么他们之间的顺序是任意的。
拓扑排序至少有两种解法

1）首先找出入度（连接到改点的边的数目）为零的顶点放入队列，然后依次遍历这些顶点，每次访问到其中的一个顶点时，把该定点关联到的其它顶点的边移去，也就是使得关联顶点的入度减1.如果减1后该定点入度也变为0了，那么把该定点加入队列下次从他开始处理，直到没有入度为0的定点了。
这里要注意，如果给定的图有回路那么，可能不会处理完所有顶点就退出了。

实现如下：

private final void calculateInDegrees(int[] inDegrees)
    {
        Arrays.fill(inDegrees, 0);
        for(int v=0;v<numVertexes;v++)
        {
            for(Edge e=firstEdge(v);isEdge(e);e=nextEdge(e))
            {
                inDegrees[toVertex(e)]++;
            }
        }
    }
    /**
     *
     * @param sortedVertexes
     */
    public void topologySort(int[] sortedVertexes)
    {
        //first calculate the inDegrees
        int[] inDegrees=new int[numVertexes];
        calculateInDegrees(inDegrees);
       
        Arrays.fill(visitTags, false);
       
        _IntQueue queue=new _IntQueue();
       
        for(int v=0;v<numVertexes-1;v++)
        {
            if(inDegrees[v]==0)queue.add(v);
        }
       
       
        int index=0;
        while(!queue.isEmpty())
        {
           
            int from=queue.remove();
            System.out.println("visit:"+from);
            sortedVertexes[index++]=from;
            for(Edge e=firstEdge(from);isEdge(e);e=nextEdge(e))
            {
               
                if(--inDegrees[toVertex(e)]==0)
                {
                    queue.add(toVertex(e));
                }
            }
        }
        if(index<numVertexes)
        {
            throw new IllegalArgumentException("There is a loop");
        }
       
    }
这里一开始计算了各个顶点的入度，计算的时候，每条边需要访问一次。
如果是相邻矩阵的存储方式，计算入度只需要计算每列的非零个数。
一般也可以静态的给出。

2）借助于图的深度优先周游，每次在回退到改顶点的时候把该顶点送入结果数组。
这样得到的数组恰好就是拓扑排序的逆序，因为最底层的节点是最先回退到的。
实现：
/**
     *
     * @param sortedVertexes
     */
    public void topologySort_byDFS(int[] sortedVertexes)
    {
        Arrays.fill(visitTags, false);
        int num=0;
        for(int i=0;i<numVertexes;i++)
        {
            if(!visitTags[i])num=do_topsort(i,sortedVertexes,num);
        }
       
    }



    private final int do_topsort(int v, int[] sortedVertexes, int num) {
        visitTags[v]=true;
       
        for(Edge e=firstEdge(v);isEdge(e);e=nextEdge(e))
        {
            if(!visitTags[toVertex(e)])num=do_topsort(toVertex(e),sortedVertexes,num);
        }
        num++;
        sortedVertexes[numVertexes-num]=v;
   
       
        return num;
    }



    /**
     * Given graph :
     *
     * C1 → C3 ← C2
     * ↓    ↓    ↓
     * C8    C4   C5
     * ↓    ↓    ↓
     * C9 → C7 ← C6
     */
    public static void testTopologySort()
    {
        DefaultGraph g=new DefaultGraph(9);
        g.setEdge(0, 1, 0);
        g.setEdge(2, 1, 0);
        g.setEdge(0, 3, 0);
        g.setEdge(1, 4, 0);
        g.setEdge(2, 5, 0);
        g.setEdge(3, 6, 0);
        g.setEdge(4, 7, 0);
        g.setEdge(5, 8, 0);
        g.setEdge(6, 7, 0);
        g.setEdge(8, 7, 0);
       
       
        g.assignLabels(new String[]{"C1","C3","C2","C8","C4","C5","C9","C7","C6"});
       
        int[] sorted=new int[g.vertexesNum()];
//        g.topologySort(sorted);
        g.topologySort_byDFS(sorted);
        System.out.println("Topology Sort Result==============:");
        for(int i=0;i<sorted.length;i++)System.out.print(g.getVertexLabel(sorted[i])+",");
        System.out.println();
    }

五 最短路径问题

最短路径问题分两类，一类是单源最短路径问题，就是从指定顶点出发到其他各点的最短距离，还有一类是
每两个顶点之间的最短距离，当然第二类也可以通过对每个顶点做一次单源最短路径求解，但是还有一种更优雅的方法（Floyd算法），这种方法一般使用相邻矩阵的实现方式，对每个顶点看它是不是能作为其它没两对顶点间的直接中间节点，如果能，那么再看是不是通过它的两两顶点的距离是不是减小了，若果是就更新这两对顶点间的距离，这样通过每次“贪婪的”找出局部最优解来得到全局最优解，可以算是一个动态规划的解法。
首先我们需要一个辅助类来保存距离，以及回溯路径的类：
public static class Dist implements Comparable<Dist>
    {
        public int preV;
        public int curV;
        public int distance;
       
        public Dist(int v)
        {
            this.curV=v;
            this.preV=-1;
            this.distance=Integer.MAX_VALUE;
        }
       
   
        @Override
        public int compareTo(Dist other) {
            return distance-other.distance;
        }
       
    }
下面给出第二类最短路径的解法（Floyd算法）Java实现：
@Override
    public void floyd(Dist[][] dists) {
        for(int i=0;i<numVertexes;i++)
        {
            dists[i]=new Dist[numVertexes];
            for(int j=0;j<numVertexes;j++)
            {
                dists[i][j]=new Dist(-1);//
                dists[i][j].preV=-1;
                if(i==j)
                    dists[i][j].distance=0;
               
                else
                   dists[i][j].distance=Integer.MAX_VALUE;
               
            }
        }
       
        for(int v=0;v<numVertexes;v++)
        {
            for(Edge e=firstEdge(v);isEdge(e);e=nextEdge(e))
            {
                int to=toVertex(e);
                dists[v][to].distance=e.getWeight();
                dists[v][to].preV=v;
            }
        }
       
        for(int v=0;v<numVertexes;v++)
        {
            for(int i=0;i<numVertexes;i++)
                for(int j=0;j<numVertexes;j++)
                {
                   
                    if((dists[i][v].distance!=Integer.MAX_VALUE)&&(dists[v][j].distance!=Integer.MAX_VALUE)&&(dists[i][v].distance+dists[v][j].distance<dists[i][j].distance))
                    {
                        dists[i][j].distance=dists[i][v].distance+dists[v][j].distance;
                        dists[i][j].preV=v;
                    }
                }
        }
       
    }

/**
     * A Graph example
     * we mark the vertexes  with 0,1,2,.14 from left to right , up to down
     * S-8-B-4-A-2-C-7-D
     * |    |     |     |     |
     * 3    3     1     2     5
     * |    |     |     |     |
     * E-2-F-6-G-7-H-2-I
     * |    |     |     |     |
     * 6    1     1     1     2
     * |    |     |     |     |
     * J-5-K-1-L-3-M-3-T
     *
     */
    public static void testFloyd() {
        DefaultGraph g=new DefaultGraph(15);
        g.setEdge(0, 1,;
        g.setEdge(1, 0,;//its a undirected graph
        g.setEdge(1, 2, 4);
        g.setEdge(2, 1, 4);
        g.setEdge(2, 3, 2);
        g.setEdge(3, 2, 2);
        g.setEdge(3, 4, 7);
        g.setEdge(4, 3, 7);
       
        g.setEdge(0, 5, 3);
        g.setEdge(5, 0, 3);
        g.setEdge(1, 6, 3);
        g.setEdge(6, 1, 3);
        g.setEdge(2, 7, 1);
        g.setEdge(7, 2, 1);
        g.setEdge(3, 8, 2);
        g.setEdge(8, 3, 2);
        g.setEdge(4, 9, 5);
        g.setEdge(9, 4, 5);
       
       
        g.setEdge(5, 6, 2);
        g.setEdge(6, 5, 2);
        g.setEdge(6, 7, 6);
        g.setEdge(7, 6, 6);
        g.setEdge(7, 8, 7);
        g.setEdge(8, 7, 7);
        g.setEdge(8, 9, 2);
        g.setEdge(9, 8, 2);
       
       
        g.setEdge(10, 5, 6);
        g.setEdge(5, 10, 6);
        g.setEdge(11, 6, 1);
        g.setEdge(6, 11, 1);
        g.setEdge(12, 7, 1);
        g.setEdge(7, 12, 1);
        g.setEdge(13, 8, 1);
        g.setEdge(8, 13, 1);
        g.setEdge(14, 9, 2);
        g.setEdge(9, 14, 2);
       
        g.setEdge(10, 11, 5);
        g.setEdge(11, 10, 5);
        g.setEdge(11, 12, 1);
        g.setEdge(12, 11, 1);
        g.setEdge(12, 13, 3);
        g.setEdge(13, 12, 3);
        g.setEdge(13, 14, 3);
        g.setEdge(14, 13, 3);
       
        g.assignLabels(new String[]{"S","B","A","C","D","E","F","G","H","I","J","K","L","M","T"});
       
        Dist[][] dists=new Dist[15][15];
        g.floyd(dists);
       
        System.out.println("Shortes path from S-T ("+dists[0][14].distance+")is:");
        Stack<String> stack=new Stack<String>();
        int i=0;
        int j=14;
        while(j!=i)
        {
           
            stack.push(g.getVertexLabel(j));
            j=dists[i][j].preV;
           
        }
        stack.push(g.getVertexLabel(i));
        while(!stack.isEmpty())
        {
            System.out.print(stack.pop());
            if(!stack.isEmpty())System.out.print("->");
        }
        System.out.println();
       

    }



单源最短路径问题的解法有Dijstra提出，所以也叫Dijstra算法。
它把顶点分为两个集合一个是已求出最短距离的顶点集合V1，另一类是暂未求出的顶点集合V2，而可以证明下一个将求出来（V2中到出发点最短距离值最小）的顶点的最短路径上的顶点除了该顶点不在V1中外其余顶点都在V1中。

如此，先把出发点放入V1中（出发点的最短距离当然也就是0），然后每次选择V2中到出发点距离最短的点加入V1，并把标记改点的最短距离.直到V2中没有顶点为止，详细的形式化证明见：
Dijstra算法证明

这里的实现我们使用最小值堆来每次从V2中挑出最短距离。

先给出最小值堆的实现：
package algorithms;

import java.lang.reflect.Array;

public class MinHeap<E extends Comparable<E>>
{
       
        private E[] values;
        int len;
       
        public MinHeap(Class<E> clazz,int num)
        {
           
            this.values=(E[])Array.newInstance(clazz,num);
            len=0;
        }
           
       
        public final E removeMin()
        {
            E ret=values[0];
            values[0]=values[--len];
            shift_down(0);
            return ret;
        }
   
       
        //insert to tail
        public final void insert(E val)
        {
            values[len++]=val;
            shift_up(len-1);
           
        }
       
        public final void rebuild()
        {
            int pos=(len-1)/2;
            for(int i=pos;i>=0;i--)
            {
                shift_down(i);
            }
        }
       
        public final boolean isEmpty()
        {
            return len==0;
        }
       
        /**
         * When insert element we  need shiftUp
         * @param array
         * @param pos
         */
        private final void shift_up(int pos)
        {
   
            E tmp=values[pos];
            int index=(pos-1)/2;
            while(index>=0)
            {
                if(tmp.compareTo(values[index])<0)
                {
                    values[pos]=values[index];
                    pos=index;
                    if(pos==0)break;
                    index=(pos-1)/2;
                }
                else break;
            }
            values[pos]=tmp;
        }
        private final void shift_down(int pos)
        {
           
            E tmp=values[pos];
            int index=pos*2+1;//use left child
            while(index<len)//until no child
            {
                if(index+1<len&&values[index+1].compareTo(values[index])<0)//right child is smaller
                {
                    index+=1;//switch to right child
                }
                if(tmp.compareTo(values[index])>0)
                {
                    values[pos]=values[index];
                    pos=index;
                    index=pos*2+1;
                   
                }
                else
                {
                    break;
                }
               
            }
            values[pos]=tmp;
           
                   
        }
    }
下面是基于最小值堆的最短路劲算法以及一个测试方法：


    public void dijstra(int fromV,Dist[] dists)
    {
        MinHeap<Dist> heap=new MinHeap<Dist>(Dist.class,numVertexes*2);
       
        for(int v=0;v<numVertexes;v++)
        {
            dists[v]=new Dist(v);
        }
       
        Arrays.fill(visitTags, false);
        dists[fromV].distance=0;
        dists[fromV].preV=-1;
        heap.insert(dists[fromV]);
        int num=0;
       
        while(num<numVertexes)
        {
            Dist dist=heap.removeMin();
            if(visitTags[dist.curV])
            {
                continue;
            }
            visitTags[dist.curV]=true;
            num++;
            for(Edge e=firstEdge(dist.curV);isEdge(e);e=nextEdge(e))
            {
                if(!visitTags[toVertex(e)]&&e.getWeight()+dist.distance<dists[toVertex(e)].distance)
                {
                   
                    dists[toVertex(e)].distance=e.getWeight()+dist.distance;
                    dists[toVertex(e)].preV=dist.curV;
                    heap.insert(dists[toVertex(e)]);
                   
                }
            }
           
        }
       
       
    }


   
    /**
     * A Graph example
     * we mark the vertexes  with 0,1,2,.14 from left to right , up to down
     * S-8-B-4-A-2-C-7-D
     * |   |   |   |   |
     * 3   3   1   2   5
     * |   |   |   |   |
     * E-2-F-6-G-7-H-2-I
     * |   |   |   |   |
     * 6   1   1   1   2
     * |   |   |   |   |
     * J-5-K-1-L-3-M-3-T
     *
     */
    public static void testDijstra()
    {
        DefaultGraph g=new DefaultGraph(15);
        g.setEdge(0, 1,;
        g.setEdge(1, 0,;//its a undirected graph
        g.setEdge(1, 2, 4);
        g.setEdge(2, 1, 4);
        g.setEdge(2, 3, 2);
        g.setEdge(3, 2, 2);
        g.setEdge(3, 4, 7);
        g.setEdge(4, 3, 7);
       
        g.setEdge(0, 5, 3);
        g.setEdge(5, 0, 3);
        g.setEdge(1, 6, 3);
        g.setEdge(6, 1, 3);
        g.setEdge(2, 7, 1);
        g.setEdge(7, 2, 1);
        g.setEdge(3, 8, 2);
        g.setEdge(8, 3, 2);
        g.setEdge(4, 9, 5);
        g.setEdge(9, 4, 5);
       
       
        g.setEdge(5, 6, 2);
        g.setEdge(6, 5, 2);
        g.setEdge(6, 7, 6);
        g.setEdge(7, 6, 6);
        g.setEdge(7, 8, 7);
        g.setEdge(8, 7, 7);
        g.setEdge(8, 9, 2);
        g.setEdge(9, 8, 2);
       
       
        g.setEdge(10, 5, 6);
        g.setEdge(5, 10, 6);
        g.setEdge(11, 6, 1);
        g.setEdge(6, 11, 1);
        g.setEdge(12, 7, 1);
        g.setEdge(7, 12, 1);
        g.setEdge(13, 8, 1);
        g.setEdge(8, 13, 1);
        g.setEdge(14, 9, 2);
        g.setEdge(9, 14, 2);
       
        g.setEdge(10, 11, 5);
        g.setEdge(11, 10, 5);
        g.setEdge(11, 12, 1);
        g.setEdge(12, 11, 1);
        g.setEdge(12, 13, 3);
        g.setEdge(13, 12, 3);
        g.setEdge(13, 14, 3);
        g.setEdge(14, 13, 3);
       
        g.assignLabels(new String[]{"S","B","A","C","D","E","F","G","H","I","J","K","L","M","T"});
       
        Dist[] dists=new Dist[15];
        g.dijstra(0, dists);
       
        System.out.println("Shortes path from S-T ("+dists[14].distance+")is:");
        Stack<String> stack=new Stack<String>();
        for(int v=dists[14].curV;v!=-1;v=dists[v].preV)
        {
            stack.push(g.getVertexLabel(v));
       
        }
        while(!stack.isEmpty())
        {
            System.out.print(stack.pop());
            if(!stack.isEmpty())System.out.print("->");
        }
        System.out.println();
       
       
    }