数据结构与算法-图（JAVA语言描述）

图的表示

对下图所示的无向图，可使用一个7X7的邻接矩阵表示：

final int mw = Integer.MAX_VALUE;
int[][] C = new int[][]{
                {0, 5, 2, mw, mw, mw, mw},
                {5, 0, mw, 1, 6, mw, mw},
                {2, mw, 0, 6, mw, 8, mw},
                {mw, 1, 6, 0, 1, 2, mw},
                {mw, 6, mw, 1, 0, mw, 7},
                {mw, mw, 8, 2, mw, 0, 3},
                {mw, mw, mw, mw, 7, 3, 0}
        };

图的遍历（BFS & DFS）

/**
 * 图
 */
public class Graph<T> {
    public static void main(String[] args) {
        final int mw = Integer.MAX_VALUE;
        int[][] graph = new int[][]{
                {0, 5, 2, mw, mw, mw, mw},
                {5, 0, mw, 1, 6, mw, mw},
                {2, mw, 0, 6, mw, 8, mw},
                {mw, 1, 6, 0, 1, 2, mw},
                {mw, 6, mw, 1, 0, mw, 7},
                {mw, mw, 8, 2, mw, 0, 3},
                {mw, mw, mw, mw, 7, 3, 0}
        };
        char[] vertexes = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        Graph<Character> theGraph = new Graph<>(vertexes, graph);
        //theGraph.dfs(0);
        //theGraph.bfs(1);
      
    }
    
    private static final int MAX_VERTS = 20;
    private Vertex[] vertexList;// 顶点数组
    private int adjMat[][];     // 邻接矩阵
    private int nVerts;         // 当前顶点总数
    private StackX theStack;
    private QueueX theQueueX;
    
    public Graph() {// 构造图
        vertexList = new Vertex[MAX_VERTS];

        adjMat = new int[MAX_VERTS][MAX_VERTS];
        nVerts = 0;
        for (int i = 0; i < MAX_VERTS; i++) {
            for (int j = 0; j < MAX_VERTS; j++) {
                adjMat[i][j] = 0;
            }
        }
        theStack = new StackX();
        theQueueX = new QueueX();
    }

    public Graph(char[] vertexList, int[][] adjMat) {
        if (vertexList.length != adjMat.length) {
            throw new RuntimeException("illegal argument");
        }

        this.adjMat = adjMat;
        this.nVerts = vertexList.length;
        theStack = new StackX();
        theQueueX = new QueueX();

        this.vertexList = new Vertex[nVerts];
        for (int i = 0; i < vertexList.length; i++) {
            this.vertexList[i] = new Vertex<>(vertexList[i]);
        }
    }

    public void addVertex(T lab) {// 添加顶点
        vertexList[nVerts++] = new Vertex<>(lab);
    }

    public void addEdge(int start, int end, int weight) {// 添加边
        adjMat[start][end] = weight;
    }

    public void displayVertex(int v) {// 打印数组中v位置下的顶点名
        System.out.print(vertexList[v].lable + "\t");
    }

    public int getAdjUnvisitedVertex(int v) {// 获取和v邻接的未访问的顶点
        for (int i = 0; i < nVerts; i++) {
            if (adjMat[v][i] > 0 && adjMat[v][i] < Integer.MAX_VALUE && !vertexList[i].wasVisited) {
                return i;
            }
        }
        return -1;
    }

    public void dfs(int start) {// 深度优先搜索
        vertexList[start].wasVisited = true;
        displayVertex(start);
        theStack.push(start);

        while (!theStack.isEmpty()) {
            int v = getAdjUnvisitedVertex(theStack.peek());
            if (v == -1) {
                theStack.pop();
            } else {
                vertexList[v].wasVisited = true;
                displayVertex(v);
                theStack.push(v);
            }
        }

        for (int i = 0; i < nVerts; i++) {
            vertexList[i].wasVisited = false;// 重置，防止后边再次使用dfs
        }
    }

    public void bfs(int start) {// 广度优先搜索
        vertexList[start].wasVisited = true;
        displayVertex(start);
        theQueueX.insert(start);
        int v2;

        while (!theQueueX.isEmpty()) {
            int v1 = theQueueX.remove();

            while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
                vertexList[v2].wasVisited = true;
                displayVertex(v2);
                theQueueX.insert(v2);
            }
        }

        for (int j = 0; j < nVerts; j++) {
            vertexList[j].wasVisited = false;
        }
    }

}

class StackX {// 自定义栈
    private static final int SIZE = 20;
    private int[] st;
    private int top;

    public StackX() {
        st = new int[SIZE];
        top = -1;
    }

    public void push(int j) {
        st[++top] = j;
    }

    public int pop() {
        if (top == 0) {
            return -1;
        }
        return st[--top];
    }

    public int peek() {
        return st[top];
    }

    public boolean isEmpty() {
        return (top == -1);
    }
}

class QueueX {
    private final int SIZE = 20;
    private int[] queArray;
    private int front;
    private int rear;

    public QueueX() {
        queArray = new int[SIZE];
        front = 0;
        rear = -1;
    }

    public void insert(int j) {// 入队
        if (rear == SIZE - 1) {
            rear = -1;
        }
        queArray[++rear] = j;
    }

    public int remove() {// 出队
        if (!isEmpty()) {
            return queArray[front++];
        } else {
            return -1;
        }
    }


    public boolean isEmpty() {
        return (rear + 1 == front);
    }
}

/**
 * 图的节点
 */
class Vertex<T> {
    /**
     * 节点名称
     */
    public T lable;
    /**
     * 是否已经被遍历
     */
    public boolean wasVisited;

    public Vertex(T lab) {
        lable = lab;
        wasVisited = false;
    }
}

最短路径

dijkstra

    public void dijkstra() { //最短路径
        int[] dis = new int[nVerts];    //距离表
        int[] prevs = new int[nVerts];  //前置节点

        vertexList[0].wasVisited = true;
        System.arraycopy(adjMat[0], 0, dis, 0, nVerts);

        while (true) {
            int min = Integer.MAX_VALUE;
            int index = -1;
            //找出最近顶点
            for (int i = 0; i < nVerts; i++) {

                if (!vertexList[i].wasVisited) {
                    if (dis[i] < min) {
                        index = i;
                        min = dis[i];
                    }
                }
            }

            //结束条件
            if (index == -1) break;

            //更新距离表
            vertexList[index].wasVisited = true;
            for (int i = 0; i < nVerts; i++) {
                if (adjMat[index][i] != Integer.MAX_VALUE) {
                    if (dis[i] > (min + adjMat[index][i])) {
                        dis[i] = min + adjMat[index][i];
                        prevs[i] = index;
                    }
                }
            }
        }
        //输出结果
        System.out.println(dis[nVerts - 1]);
        printPrevs(prevs, nVerts - 1);
    }

    private void printPrevs(int[] prev, int i) {
        if (i > 0) {
            printPrevs(prev, prev[i]);
        }
        System.out.print(vertexList[i].lable.toString() + "\t");

    }

Floyd

暑假，小哼准备去一些城市旅游。有些城市之间有公路，有些城市之间则没有，如下图。为了节省经费以及方便计划旅程，小哼希望在出发之前知道任意两个城市之前的最短路程。

上图中有4个城市8条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程，也就是求任意两个点之间的最短路径。这个问题这也被称为多源最短路径问题。
现在回到问题：如何求任意两点之间最短路径呢？通过之前的学习我们知道通过深度或广度优先搜索可以求出两点之间的最短路径。所以进行n2遍深度或广度优先搜索，即对每两个点都进行一次深度或广度优先搜索，便可以求得任意两点之间的最短路径。可是还有没有别的方法呢？

我们来想一想，根据我们以往的经验，如果要让任意两点（例如从顶点a点到顶点b）之间的路程变短，只能引入第三个点（顶点k），并通过这个顶点k中转即a->k->b，才可能缩短原来从顶点a点到顶点b的路程。那么这个中转的顶点k是1~n中的哪个点呢？甚至有时候不只通过一个点，而是经过两个点或者更多点中转会更短，即a->k1->k2b->或者a->k1->k2…->k->i…->b。比如上图中从4号城市到3号城市（4->3）的路程e[4][3]原本是12。如果只通过1号城市中转（4->1->3），路程将缩短为11（e[4][1]+e[1][3]=5+6=11）。其实1号城市到3号城市也可以通过2号城市中转，使得1号到3号城市的路程缩短为5（e[1][2]+e[2][3]=2+3=5）。所以如果同时经过1号和2号两个城市中转的话，从4号城市到3号城市的路程会进一步缩短为10。通过这个的例子，我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。

    public int[][] floyd() {
        int[][] C = new int[nVerts][nVerts];
        for (int i = 0; i < nVerts; i++) {
            System.arraycopy(adjMat[i], 0, C[i], 0, nVerts);
        }
        
        for (int k = 0; k < nVerts; k++) {
            for (int i = 0; i < nVerts; i++) {
                for (int j = 0; j < nVerts; j++) {
                    if (C[i][k] != Integer.MAX_VALUE && C[k][j] != Integer.MAX_VALUE 
                    &&  C[i][k] + C[k][j] < C[i][j]) {
                        C[i][j] = C[i][k] + C[k][j];
                    }

                }
            }
        }
        
        for (int i = 0; i < nVerts; i++) {
            for (int j = 0; j < nVerts; j++) {
                if (i == j) continue;
                if (C[i][j] == mw)
                    System.out.println(i + "到" + j + "之间没路径");
                else
                    System.out.println(i + "到" + j + "之间的最短路径长度为：" + C[i][j]);
            }
        }

        return C;
    }