图的数据结构、原理详解及算法实现

public class G2 {

    public static void main(String[] args) {
        // 1、无向图
        // 定点数组vertex
        String[] v1 = new String[]{"V0", "V1", "V2", "V3"};

        // 矩阵表示边的关系edge 其中1表示两个顶点之间存在关系，0表示无关，不存在顶点间的边。
        int[][] e1 = new int[][]{
            {0, 1, 1, 1},
            {1, 0, 1, 0},
            {1, 1, 0, 1},
            {1, 0, 1, 0}
        };

        System.out.println("输出无向图：");

        for (int i = 0; i < v1.length; i++) {
            System.out.print(v1[i] + "t");
        }

        System.out.println();

        for (int i = 0; i < v1.length; i++) {
            for (int j = 0; j < v1.length; j++) {
                System.out.print(e1[i][j] + "t");
            }
            System.out.println();
        }

        System.out.println("--------------------");

        // 2、有向图
        String[] v2 = new String[]{"V0", "V1", "V2", "V3"};

        int[][] e2 = new int[][]{
            {0, 0, 0, 1},
            {1, 0, 1, 0},// V1的出度为2
            {1, 1, 0, 0},// V2的出度为2
            {0, 0, 0, 0}
            // V1的入度为1
        };

        System.out.println("输出有向图：");
        for (int i = 0; i < v2.length; i++) {
            System.out.print(v2[i] + "t");
        }

        System.out.println();

        for (int i = 0; i < v2.length; i++) {
            for (int j = 0; j < v2.length; j++) {
                System.out.print(e2[i][j] + "t");
            }
            System.out.println();
        }

        System.out.println("--------------------");
        
        // 3、网，每条边上带有权的图就叫做网
        String[] v3 = new String[]{"V0", "V1", "V2", "V3", "V4"};

        // m表示不可达
        int m = 65535;
        int[][] e3 = new int[][]{
            {0, m, m, m, 6},
            {9, 0, 3, m, m},
            {2, m, 0, 5, m},
            {m, m, m, 0, 1},
            {m, m, m, m, 0}
        };

        System.out.println("输出网：");

        for (int i = 0; i < v3.length; i++) {
            System.out.print(v3[i] + "t");
        }

        System.out.println();

        for (int i = 0; i < v3.length; i++) {
            for (int j = 0; j < v3.length; j++) {
                System.out.print(e3[i][j] + "t");
            }
            System.out.println();
        }
    }
}

输出无向图：
V0 V1 V2 V3
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0
--------------------
输出有向图：
V0 V1 V2 V3
0 0 0 1
1 0 1 0
1 1 0 0
0 0 0 0
--------------------
输出网：
V0 V1 V2 V3 V4
0 65535 65535 65535 6
9 0 3 65535 65535
2 65535 0 5 65535
65535 65535 65535 0 1
65535 65535 65535 65535 0

public static void createGraph(AlGraph g) {
    g.vexnum = sc.nextInt();
    g.edgenum = sc.nextInt();
    
    for (int i = 0; i < g.vexnum; i++) {
        g.vex[i] = new VexNode();
        g.vex[i].data = sc.next();
        g.vex[i].first = null;
    }

    String u, v;

    while (g.edgenum-- > 0) {
        u = sc.next();
        v = sc.next();
        int i = locateVex(g, u);
        int j = locateVex(g, v);
        
        if (i != -1 && j != -1) {
            insertEdge(g, i, j);
        } else {
            System.out.println("错误");
            g.edgenum++;
        }
    }
}

import java.util.Scanner;

public class A {

    private static final int MaxVnum = 100;

    private static Scanner sc = new Scanner(System.in);

    public static class AdjNode {
        int v;
        AdjNode next;
    }

    public static class VexNode {
        String data;
        AdjNode first;
    }

    public static class AlGraph {
        VexNode vex[] = new VexNode[MaxVnum];
        int vexnum, edgenum;
    }

    public static int locateVex(AlGraph g, String x) {
        for (int i = 0; i < g.vexnum; i++) {
            if (g.vex[i].data.equals(x)) {
                return i;
            }
        }
        
        return -1;
    }

    public static void insertEdge(AlGraph g, int i, int j) {
        AdjNode s = new AdjNode();
        s.v = j;
        s.next = g.vex[i].first;
        g.vex[i].first = s;
    }

    public static void createGraph(AlGraph g) {
        g.vexnum = sc.nextInt();
        g.edgenum = sc.nextInt();

        for (int i = 0; i < g.vexnum; i++) {
            g.vex[i] = new VexNode();
            g.vex[i].data = sc.next();
            g.vex[i].first = null;
        }

        String u, v;

        while (g.edgenum-- > 0) {
            u = sc.next();
            v = sc.next();

            int i = locateVex(g, u);
            int j = locateVex(g, v);

            if (i != -1 && j != -1) {
                insertEdge(g, i, j);
            } else {
                System.out.println("错误");
                g.edgenum++;
            }
        }
    }

    public static void print(AlGraph g) {
        for (int i = 0; i < g.vexnum; i++) {
            System.out.print(g.vex[i].data);
            AdjNode t = g.vex[i].first;

            while (t != null) {
                System.out.print("->[" + t.v + "]");
                t = t.next;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        AlGraph g = new AlGraph();
        createGraph(g);
        print(g);
    }
}
/*
4 5
a b c d
a b
a d
b c
d b
d c
*/

public class Solution {
    private static class Node {
        /**
         * 节点值
         */        public int value;     
  
        /**
         * 左节点
         */        public Node left;

        /**
         * 右节点
         */        public Node right;
        
        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public static void dfs(Node treeNode) {
        if (treeNode == null) {
            return;
        }

        // 遍历节点
        process(treeNode);

        // 遍历左节点
        dfs(treeNode.left);

        // 遍历右节点
        dfs(treeNode.right);
    }
}

**   
 * 使用栈来实现 dfs   
 * @param root   
 */     
public static void dfsWithStack(Node root) {
    if (root == null) {
        return;     
    }  
     
    Stack<Node> stack = new Stack<>();
    // 先把根节点压栈
    stack.push(root);
    while (!stack.isEmpty()) {
        Node treeNode = stack.pop();     
        // 遍历节点     
        process(treeNode)     
     
        // 先压右节点     
        if (treeNode.right != null) {
            stack.push(treeNode.right);     
        }  
     
        // 再压左节点     
        if (treeNode.left != null) {
            stack.push(treeNode.left);     
        }  
    }  
}

/**
 * 使用队列实现 bfs
 * @param root
 */private static void bfs(Node root) {
    if (root == null) {
        return;
    }
    Queue<Node> stack = new LinkedList<>();
    stack.add(root);
     
    while (!stack.isEmpty()) {
        Node node = stack.poll();
        System.out.println("value = " + node.value);
        Node left = node.left;
        if (left != null) {
            stack.add(left);
        }
        Node right = node.right;
        if (right != null) {
            stack.add(right);
        }
    }
}

/*
 * 拓扑排序
 *
 * 返回值：
 *     -1 -- 失败(由于内存不足等原因导致)
 *      0 -- 成功排序，并输入结果
 *      1 -- 失败(该有向图是有环的)
 */public class ListDG {
    // 邻接表中表对应的链表的顶点
    private class ENode {
        int ivex; // 该边所指向的顶点的位置
        ENode nextEdge; // 指向下一条弧的指针
    }

    // 邻接表中表的顶点
    private class VNode {
        char data; // 顶点信息
        ENode firstEdge; // 指向第一条依附该顶点的弧
    }

    private VNode[] mVexs; // 顶点数组
    ...
}

public int topologicalSort() {
    int index = 0;
    int num = mVexs.size();
    int[] ins; // 入度数组
    char[] tops; // 拓扑排序结果数组，记录每个节点的排序后的序号。
    Queue<Integer> queue; // 辅组队列
  
    ins   = new int[num];
    tops  = new char[num];
    queue = new LinkedList<Integer>();
  
    // 统计每个顶点的入度数  
    for(int i = 0; i < num; i++) {
        ENode node = mVexs.get(i).firstEdge;
        while (node != null) {
            ins[node.ivex]++;
            node = node.nextEdge;
        }
    }
  
    // 将所有入度为0的顶点入队列
    for(int i = 0; i < num; i ++)
        if(ins[i] == 0)
            queue.offer(i); // 入队列
  
    while (!queue.isEmpty()) { // 队列非空
        int j = queue.poll().intValue(); // 出队列。j是顶点的序号
        tops[index++] = mVexs.get(j).data; // 将该顶点添加到tops中，tops是排序结果
        ENode node = mVexs.get(j).firstEdge; // 获取以该顶点为起点的出边队列
  
        // 将与"node"关联的节点的入度减1；
        // 若减1之后，该节点的入度为0；则将该节点添加到队列中。
        while(node != null) {
            // 将节点(序号为node.ivex)的入度减1。
            ins[node.ivex]--;
            // 若节点的入度为0，则将其"入队列"
            if( ins[node.ivex] == 0)
                queue.offer(node.ivex); // 入队列
  
            node = node.nextEdge;
        }
    }
  
    if(index != num) {
        System.out.printf("Graph has a cyclen");
        return 1;
    }
  
    // 打印拓扑排序结果
    System.out.printf("== TopSort: ");
    for(int i = 0; i < num; i ++)
        System.out.printf("%c ", tops[i]);
    System.out.printf("n");
  
    return 0;
}

#define T_MAX_SIZE 100
#define T_ERROR -1
#define T_OK 1
#define MAX_VEX_COUNT 100
#define INT_INFINITY 65535
typedef int TStatus;
// 顶点类型
typedef int VertexType;
// 权值类型
typedef int EdgeType;

typedef struct EdgeNode {
    // 邻接点域 存储邻接点对应的顶点下标
    int adjvex;
    // 权值
    int weight;
    struct EdgeNode *next;
} EdgeNode;

typedef struct VertexNode {
    VertexType data;
    // 指向边表的第一个结点
    EdgeNode *firstEdge;
    // 入度
    int inDegree;
} VertexNode, AdjList[MAX_VEX_COUNT];

typedef struct {
    // 顶点数组
    AdjList adjList;
    int vertexNum, edgeNum;
} AdjListGraph;

typedef struct {
    // 起点下标 终点下标 权值
    int startIndex, endIndex, weight;
} EdgeInfo;

void initEdgeInfos(int edgesNum, int starts[], int ends[], int weights[], EdgeInfo edges[]) {
    for (int i = 0; i < edgesNum; i++) {
        EdgeInfo *eInfo = (EdgeInfo *)malloc(sizeof(EdgeInfo));
        eInfo->startIndex = starts[i];
        eInfo->endIndex = ends[i];
        eInfo->weight = weights[i];
        edges[i] = *eInfo;
    }
}

void initAdjListGraph(AdjListGraph *graph, int vertexNum, int edageNum, VertexType vertexes[], EdgeInfo edges[]) {
    graph->vertexNum = vertexNum;
    graph->edgeNum = edageNum;
    
    // 写入顶点数组 先将firstEdge置为NULL
    for (int i = 0; i < vertexNum; i++) {
        graph->adjList[i].data = vertexes[i];
        graph->adjList[i].firstEdge = NULL;
        graph->adjList[i].inDegree = 0;
    }
    
    EdgeNode *eNode;
    for (int i = 0; i < edageNum; i++) {
        // 先生成边的结尾结点
        eNode = (EdgeNode *)malloc(sizeof(EdgeNode));
        eNode->adjvex = edges[i].endIndex;
        eNode->weight = edges[i].weight;
        // 头插法
        eNode->next = graph->adjList[edges[i].startIndex].firstEdge;
        graph->adjList[edges[i].startIndex].firstEdge = eNode;
        graph->adjList[edges[i].endIndex].inDegree += 1;
    }
}

void printAdjListGraph(AdjListGraph graph) {
    for (int i = 0; i < graph.vertexNum; i++) {
        printf("n");
        EdgeNode *eNode = graph.adjList[i].firstEdge;
        printf("顶点: %d 入度: %d 边表:", graph.adjList[i].data, graph.adjList[i].inDegree);
        while (eNode) {
            printf("%d->%d(w:%d) ", graph.adjList[i].data, eNode->adjvex, eNode->weight);
            eNode = eNode->next;
        }
    }
    printf("n");
}

// 事件最早发生时间数组
int *etvs;
// 存储拓扑序列
int *topoStack;
int top2;

TStatus topologicalOrder(AdjListGraph *graph) {
    etvs = (int *)malloc(sizeof(int) * graph->vertexNum);
    int *stack = (int *)malloc(sizeof(int) * graph->vertexNum);
    int top = -1;
    // 将入度为0的顶点入栈
    for (int i = 0; i < graph->vertexNum; i++) {
        if (graph->adjList[i].inDegree == 0) {
            top += 1;
            stack[top] = i;
        }
        etvs[i] = 0;
    }
    
        
    // 栈顶元素
    int stackTop;
    // 记录输出的顶点个数
    int count;
    
    // 存储拓扑排序
    topoStack = (int *)malloc(sizeof(int) * graph->vertexNum);
    top2 = -1;
    
    EdgeNode *eNode;
    while (top != -1) {
        stackTop = stack[top];
        top -= 1;
        top2 += 1;
        topoStack[top2] = stackTop;

        count += 1;
        eNode = graph->adjList[stackTop].firstEdge;
        while (eNode) {
            if (!(--graph->adjList[eNode->adjvex].inDegree)) {
                stack[++top] = eNode->adjvex;
            }
            // 得出每一个顶点 事件的最早发生时间
            // 顶点不同路径之间比较 得到最大值 从上一个顶点到当前顶点有不同的路径 找出最大值
            if (etvs[stackTop] + eNode->weight > etvs[eNode->adjvex]) {
                etvs[eNode->adjvex] = etvs[stackTop] + eNode->weight;
            }
            eNode = eNode->next;
        }
    }
    
    if (count < graph->vertexNum) {
        return T_ERROR;
    }
    
    return T_OK;
}

// 事件最晚发生时间数组
int *ltvs;

void getKeyPath(AdjListGraph *graph) {
    ltvs = (int *)malloc(sizeof(int) * graph->vertexNum);
    
    // 默认把事件最晚发生时间都设置为最大的开始时间
    for (int i = 0; i < graph->vertexNum; i++) {
        ltvs[i] = etvs[graph->vertexNum-1];
    }
    
    // 计算事件最迟发生时间数组
    int stackTop;
    EdgeNode *eNode;
    while (top2 != -1) {
        stackTop = topoStack[top2];
        top2 -= 1;
        eNode = graph->adjList[stackTop].firstEdge;
        while (eNode) {
            // 最晚开始时间 = 下一个结点的开始时间 - 路径权值
            if (ltvs[eNode->adjvex] - eNode->weight < ltvs[stackTop]) {
                ltvs[stackTop] = ltvs[eNode->adjvex] - eNode->weight;
            }
            eNode = eNode->next;
        }
    }
 
    
    int ete, lte;
    for (int i = 0; i < graph->vertexNum; i++) {
        eNode = graph->adjList[i].firstEdge;
        while (eNode) {
            ete = etvs[i];
            lte = ltvs[eNode->adjvex] - eNode->weight;
            // 最早开始时间等于最晚开始时间 则该路径就为关键路径
            if (ete == lte) {
                printf("<V%d-V%d> length:%dn", graph->adjList[i].data, graph->adjList[eNode->adjvex].data, eNode->weight);
            }
            eNode = eNode->next;
        }
    }
}

void keyPathTest() {
    int vertexNumber = 10;
    int edgeNumber   = 13;
    int starts[]     = {0, 0, 1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 8};
    int ends[]       = {1, 2, 4, 3, 3, 5, 4, 6, 7, 7, 9, 8, 9};
    int weights[]    = {3, 4, 6, 5, 8, 7, 3, 9, 4, 6, 2, 5, 3};

    EdgeInfo *eInfos = malloc(sizeof(EdgeInfo) * edgeNumber);
    initEdgeInfos(edgeNumber, starts, ends, weights, eInfos);
    
    AdjListGraph graph;
    VertexType vertexes[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
    initAdjListGraph(&graph, vertexNumber, edgeNumber, vertexes, eInfos);
    
    TStatus st = topologicalOrder(&graph);
    printf("n%s是AOV网n", st == T_OK ? "": "不");
    getKeyPath(&graph);
}

是AOV网

<V0-V2> length:4
<V2-V3> length:8
<V3-V4> length:3
<V4-V7> length:4
<V7-V8> length:5
<V8-V9> length:3

// 边的结构体
private static class EData {
    char start; // 边的起点
    char end; // 边的终点
    int weight; // 边的权重
  
    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
}

public class MatrixUDG {
    private int mEdgNum; // 边的数量

    private char[] mVexs; // 顶点集合

    private int[][] mMatrix; // 邻接矩阵

    private static final int INF = Integer.MAX_VALUE; // 最大值
    ...
}  

/*
 * 克鲁斯卡尔（Kruskal)最小生成树
 *
public void kruskal(){
  
    int index=0; // rets数组的索引

    int[]vends=new int[mEdgNum]; // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点

    EData[]rets=new EData[mEdgNum]; // 结果数组，保存kruskal最小生成树的边

    EData[]edges; // 图对应的所有边

    // 获取"图中所有的边"
    edges=getEdges();

    // 将边按照"权"的大小进行排序(从小到大)
    sortEdges(edges,mEdgNum);

    for(int i=0;i<mEdgNum; i++){
        int p1=getPosition(edges[i].start); // 获取第i条边的"起点"的序号
        int p2=getPosition(edges[i].end); // 获取第i条边的"终点"的序号
        int m=getEnd(vends,p1); // 获取p1在"已有的最小生成树"中的终点
        int n=getEnd(vends,p2); // 获取p2在"已有的最小生成树"中的终点

        // 如果m!=n，意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路
        if(m!=n){
            vends[m]=n; // 设置m在"已有的最小生成树"中的终点为n
            rets[index++]=edges[i]; // 保存结果
        }
    }

    // 统计并打印"kruskal最小生成树"的信息
    int length=0;
    for(int i=0;i<index; i++){
        length+=rets[i].weight;
        System.out.printf("Kruskal=%d: ",length);
        for(int i=0;i<index; i++){
            System.out.printf("(%c,%c) ",rets[i].start,rets[i].end);
            System.out.printf("n");
         }
    }
}

import java.util.Arrays;  
    
/**  
 * @description: 普里姆算法（Prim算法）示例
 */    
public class PrimAlgorithm {  
    public static void main(String[] args) {  
        //定义图的各个顶点的值    
        char[] data=new char[]{'A','B','C','D','E','F','G'};  
        //根据图的各个顶点的值，获取图对应的顶点个数    
        int verxs=data.length;  
        //使用二维数组表示邻接矩阵的关系 ，10000:表示两个点不连通    
        int[][] weight=new int[][]{  
                {10000,5,7,10000,10000,10000,2},    
                {5,10000,10000,9,10000,10000,3},    
                {7,10000,10000,10000,8,10000,10000},    
                {10000,9,10000,10000,10000,4,10000},    
                {10000,10000,8,10000,10000,5,4},    
                {10000,10000,10000,4,5,10000,6},    
                {2,3,10000,10000,4,6,10000} 
        };  
        //创建Graph对象    
        Graph graph = new Graph(verxs);  
        //创建MinTree对象    
        MinTree minTree=new MinTree();  
        //创建图的邻接矩阵    
        minTree.createGraph(graph,verxs,data,weight);  
        //显示图的邻接矩阵    
        System.out.println("图的邻接矩阵----------------------");  
        minTree.showGraph(graph);  
        //测试普里姆算法    
        System.out.println("普里姆算法==============");  
        minTree.prim(graph,0);  
    } 
} 
    
/**   
* @Description: 创建最小生成树->村庄的图
*/    
class MinTree{  
    /**  
    * @Description:  创建图的邻接矩阵  
    * @Param:  graph 图对象  
    *          verxs 图对应的顶点个数  
    *          data  图的各个顶点的值  
    *          weight 图的邻接矩阵
    */    
    public void createGraph(Graph graph, int verxs, char[] data, int[][] weight){  
        for(int i=0;i<verxs;i++){  
            graph.data[i]=data[i];  
            for(int j=0;j<verxs;j++){  
                graph.weight[i][j]=weight[i][j];  
            } 
        } 
    } 
    
    // 显示图的邻接矩阵    
    public void showGraph(Graph graph) {  
        for(int[] link: graph.weight) {  
            System.out.println(Arrays.toString(link));  
        } 
    }

    /**   
    * @Description:  prim算法，得到最小生成树  
    * @Param:  graph 图  
    *           v     表示从图的第几个顶点开始生成'A'->0 'B'->1...
    */    
    public void prim(Graph graph, int v) {  
        //visited[] 标记结点(顶点)是否被访问过,visited[] 默认元素的值都是0, 表示没有访问过    
        int visited[] = new int[graph.verxs];  
        //把当前这个结点标记为已访问    
        visited[v] = 1;  
        //h1 和 h2 记录两个顶点的下标    
        int h1 = -1;  
        int h2 = -1;  
        int minWeight = 10000; //将 minWeight 初始成一个大数，后面在遍历过程中，会被替换    
        int sumMinWeight=0;//所有对应边的最小权值的总和    
        for(int k = 1; k < graph.verxs; k++) { //因为有 graph.verxs顶点，普利姆算法结束后，有 graph.verxs-1边 
            //这个是确定每一次生成的子图 ，和哪个结点的距离最近    
            for(int i = 0; i < graph.verxs; i++) { // i结点表示被访问过的结点    
                for(int j = 0; j< graph.verxs;j++) { //j结点表示还没有访问过的结点    
                    if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {  
                        //替换minWeight(寻找已经访问过的结点和未访问过的结点间的权值最小的边)    
                        minWeight = graph.weight[i][j];  
                        h1 = i;  
                        h2 = j;  
                    }
                }
            }
            // 退出双重for循环后就找到一条边是最小    
            System.out.println("对应的边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight);  
            sumMinWeight += minWeight;  
            // 将当前这个结点标记为已经访问    
            visited[h2] = 1;  
            // minWeight 重新设置为最大值 10000    
            minWeight = 10000;  
        }
        System.out.println("所有对应边的最小权值的总和="+sumMinWeight);  
    }  
}

/**   
* @Description: 创建图
*/     
class Graph{  
    int verxs;//图的节点个数    
    char[] data;//存放图节点的数据    
    int[][] weight; //存放边，表示邻接矩阵    
    
    //构造函数    
    public Graph(int verxs){
        this.verxs=verxs;  
        data=new char[verxs];  
        weight=new int[verxs][verxs];  
    }
}

public class MatrixUDG {
    private int mEdgNum; // 边的数量

    private char[] mVexs; // 顶点集合

    private int[][] mMatrix; // 邻接矩阵

    private static final int INF = Integer.MAX_VALUE; // 最大值
    ...
}

/** 
 * Dijkstra最短路径。即，统计图中"顶点vs"到其它各个顶点的最短路径。 
 * 
 * 参数说明： 
 * vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。 
 * prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。 
 * dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短路径的长度。 
 */  
  
public void dijkstra(int vs,int[]prev,int[]dist){
  
    // flag[i]=true表示"顶点vs"到"顶点i"的最短路径已成功获取  
    boolean[]flag=new boolean[mVexs.length];

    // 初始化  
    for(int i=0;i<mVexs.length;i++){
        flag[i]=false; // 顶点i的最短路径还没获取到。  
        prev[i]=0; // 顶点i的前驱顶点为0。  
        dist[i]=mMatrix[vs][i]; // 顶点i的最短路径为"顶点vs"到"顶点i"的权。  
    }

    // 对"顶点vs"自身进行初始化  
    flag[vs]=true;
    dist[vs]=0;

    // 遍历mVexs.length-1次；每次找出一个顶点的最短路径。  
    int k=0;
    for(int i=1;i<mVexs.length;i++){

        // 寻找当前最小的路径；  
        // 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。  
        int min=INF;
        for(int j=0;j<mVexs.length;j++){
            if(flag[j]==false&&dist[j]<min){
                min=dist[j];
                k=j;
             }
         }

        // 标记"顶点k"为已经获取到最短路径 
        flag[k]=true;
        // 修正当前最短路径和前驱顶点  
        // 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。  
        for(int j=0;j<mVexs.length;j++){
            int tmp=(mMatrix[k][j]==INF?INF:(min+mMatrix[k][j]));
            if(flag[j]==false&&(tmp<dist[j])){
                dist[j]=tmp;
                prev[j]=k;
            }
        }
    }

    // 打印dijkstra最短路径的结果  
    System.out.printf("dijkstra(%c): n",mVexs[vs]);
    for(int i=0;i<mVexs.length;i++){
         System.out.printf(" shortest(%c, %c)=%dn",mVexs[vs],mVexs[i],dist[i]);
    }
}

import java.util.Arrays; 

public class Floyd {

    public static void main(String[] args) {
        char[] vertex = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
        int[][] arr = new int[vertex.length][vertex.length];
        final int N = 100;
        arr[0] = new int[] { 0, 5, 7, N, N, N, 2 };
        arr[1] = new int[] { 5, 0, N, 9, N, N, 3 };
        arr[2] = new int[] { 7, N, 0, N, 8, N, N };
        arr[3] = new int[] { N, 9, N, 0, N, 4, N };
        arr[4] = new int[] { N, N, 8, N, 0, 5, 4 };
        arr[5] = new int[] { N, N, N, 4, 5, 0, 6 };
        arr[6] = new int[] { 2, 3, N, N, 4, 6, 0 };
        Graph gp = new Graph(vertex, arr, vertex.length);
        gp.floyd();
        gp.show();
    }
}

// 创建图
class Graph {
    private char[] vertex;

    private int[][] dis; // 从顶点出发到其他节点的距离

    private int[][] pre; // 目标节点的前驱节点
    
    // 顶点数组 邻接矩阵 长度大小
    public Graph(char[] vertex, int[][] dis, int len) {
        this.vertex = vertex;
        this.dis = dis;
        this.pre = new int[len][len];
        
        // 对pre数组进行初始化
        for (int i = 0; i < len; i++) {
            Arrays.fill(pre[i], i);
        }
    }

    public void show() {
        char[] vertex = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };

        for (int i = 0; i < dis.length; i++) {
            for (int j = 0; j < dis.length; j++) {
                System.out.print(vertex[pre[i][j]] + "  ");
            }
            System.out.println();
            
            for (int j = 0; j < dis.length; j++) {
                System.out.print("( " + vertex[i] + " -> " + vertex[j] + " 的最短路径 " + dis[i][j] + " )    ");
            }
            System.out.println();
        }
    }

    // 弗洛伊德算法
    public void floyd() {
        int len = 0;
        // 从中间节点进行遍历
        for (int k = 0; k < dis.length; k++) {
            // 对出发节点进行遍历
            for (int i = 0; i < dis.length; i++) {
                // 遍历终点节点
                for (int j = 0; j < dis.length; j++) {
                    len = dis[i][k] + dis[k][j]; 
                    if (len < dis[i][j]) {
                        dis[i][j] = len;
                        pre[i][j] = pre[k][j];
                    }
                }
            }
        }
    }
}