1. 最小生成树

• 1.找到从最新的顶点到其他顶点的所有边，这些顶点不能在树的集合中，把这些边放入优先级队列中。

• 2.找出权值最小的边，把它和它所达到的顶点放入树的集合中。

1. //边界路径类，主要记录了边的始末顶点，以及边的权值

2. class Edge {

3.    public int srcVert; //index of vertex starting edge

4.    public int destVert; //index of vertex ending edge

5.    public int distance; //distance from src to dest

7.    public Edge(int sv, int dv, int d) {

8.        srcVert = sv;

9.        destVert = dv;

10.        distance = d;

11.    }

12. }

14. //自定义优先队列，用来存储边

15. class PriorityQ {

16.    private final int SIZE = 20;

17.    private Edge[] queArray; //存储边界的数组

18.    private int size;

20.    public PriorityQ() {

21.        queArray = new Edge[SIZE];

22.        size = 0;

23.    }

25.    public void insert(Edge item) { //有序的插入边界

26.        int j;

27.        for(j = 0; j < size; j++) { //找到插入的位置，从0到size-1，逐渐减小

28.            if(item.distance >= queArray[j].distance)

29.                break;

30.        }

31.        //比item.distance小的往后挪一位，给腾出个空间

32.        for(int k = size-1; k >= j; k--) {

33.            queArray[k+1] = queArray[k];

34.        }

35.        queArray[j] = item; //插入item

36.        size++;

37.    }

39.    public Edge removeMin() { //删除最小的边界并返回

40.        return queArray[--size];

41.    }

43.    public void removeN(int n) { //删除n位置的边界

44.        for(int j = n; j < size-1; j++) {

45.            queArray[j] = queArray[j+1];

46.        }

47.        size--;

48.    }

50.    public Edge peekMin() { //返回最小边界，不删除

51.        return queArray[size-1];

52.    }

54.    public Edge peekN(int n) { //返回n位置的边界

55.        return queArray[n];

56.    }

58.    public int size() {

59.        return size;

60.    }

62.    public boolean isEmpty() {

63.        return (size == 0);

64.    }

66.    public int find(int findDex) { //寻找特定disVert的边界索引

67.        for(int j = 0; j < size; j++) {

68.            if(queArray[j].destVert == findDex)

69.                return j;

70.        }

71.        return -1;

72.    }

73. }

75. //带权图类

76. public class WeightedGraph {

77.    private final int MAX_VERTS = 20; //最大顶点数

78.    private final int INFINITY = 100000; //最远距离...表示无法达到

79.    private Vertex[] vertexArray; //存储顶点的数组

80.    private int adjMat[][]; //存储顶点之间的边界

81.    private int nVerts; //顶点数量

82.    private int currentVert; //当前顶点索引

83.    private PriorityQ thePQ; //存储边的优先级队列

84.    private int nTree; //最小生成树中的顶点数量

86.    public WeightedGraph() {

87.        vertexArray = new Vertex[MAX_VERTS];

88.        adjMat = new int[MAX_VERTS][MAX_VERTS];

89.        for(int i = 0; i < MAX_VERTS; i++) {

90.            for(int j = 0; j < MAX_VERTS; j++) {

91.                adjMat[i][j] = INFINITY; //初始化所有边界无穷远

92.            }

93.        }

94.        thePQ = new PriorityQ();

95.    }

97.    public void addVertex(char lab) { //添加顶点

98.        vertexArray[nVerts++] = new Vertex(lab);

99.    }

101.    public void addEdge(int start, int end, int weight) {//添加带权边

102.        adjMat[start][end] = weight;

103.        adjMat[end][start] = weight;

104.    }

106.    public void displayVertex(int v) {

107.        System.out.print(vertexArray[v].label);

108.    }

110.    /*

111.     * 带权图的最小生成树,要选择一条最优的路径

112.     */

113.    public void MinSpanningTree() {

114.        currentVert = 0; //从0开始

115.        while(nTree < nVerts-1) { //当不是所有节点都在最小生成树中时

116.            //isInTree是上一节Vertex类中新添加的成员变量 private boolean isInTree;

117.               //表示有没有加入到树中，初始化为false

118. vertexArray[currentVert].isInTree = true; //将当前顶点加到树中

119.            nTree++;

121.            //往PQ中插入与当前顶点相邻的一些边界

122.            for(int i = 0; i < nVerts; i++) {

123.                if(i == currentVert) //如果是本顶点，跳出

124.                    continue;

125.                if(vertexArray[i].isInTree) //如果顶点i已经在树中，跳出

126.                    continue;

127.                int distance = adjMat[currentVert][i]; //计算当前顶点到i顶点的距离

128.                if(distance == INFINITY)

129.                    continue; //如果当前顶点与i顶点无穷远，跳出

130.                putInPQ(i, distance); //将i节点加入PQ中

131.            }

133.            if(thePQ.size() == 0) { //如果PQ为空，表示图不连接

134.                System.out.println("Graph not connected!");

135.                return;

136.            }

138.            Edge theEdge = thePQ.removeMin();

139.            int sourceVert = theEdge.srcVert;

140.            currentVert = theEdge.destVert;

142.            System.out.print(vertexArray[sourceVert].label);

143.            System.out.print(vertexArray[currentVert].label);

144.            System.out.print(" ");

145.        }

146.    }

148.    private void putInPQ(int newVert, int newDist) {

149.        int queueIndex = thePQ.find(newVert);//判断PQ中是否已经有到相同目的顶点的边界

150.        if(queueIndex != -1) { //如果有则与当前顶点到目的顶点的距离作比较，保留短的那个

151.            Edge tempEdge = thePQ.peekN(queueIndex);//get edge

152.            int oldDist = tempEdge.distance;

153.            if(oldDist > newDist) { //如果新的边界更短

154.                thePQ.removeN(queueIndex); //删除旧边界

155.                Edge theEdge = new Edge(currentVert, newVert, newDist);

156.                thePQ.insert(theEdge);

157.            }

158.        }

159.        else { //如果PQ中没有到相同目的顶点的边界

160.            Edge theEdge = new Edge(currentVert, newVert, newDist);

161.            thePQ.insert(theEdge);//直接添加到PQ

162.        }

163.    }

164. }

• 1.当前顶点放在树中。

• 2.连接这个顶点的边放到优先级队列中（如果合适）。

• 3.从优先级队列中删除权值最小的边，这条边的目的顶点变成当前顶点。

• 1.源点和终点相同；

• 2.终点在树中；

• 3.源点和终点之间没有边（邻接矩阵中对应的值等于无穷大）。

2. 最短路径问题

1. //DistPar类记录了当前顶点到起始顶点点的距离和当前顶点的父顶点

2. class DistPar {

3.    public int distance; //distance from start to this vertex

4.    public int parentVert; //current parent of this vertex

6.    public DistPar(int pv, int d) {

7.        distance = d;

8.        parentVert = pv;

9.    }

10. }

1. private DistPar[] sPath; //存储最短路径数据，存储的是上面的DistPar对象

2. private int startToCurrent; //到当前顶点的距离

1. /************************** 最短路径问题 ****************************/

2. /**

3. * path()方法执行真正的最短路径算法。

4. */

5. public void path() { //寻找所有最短路径

6.    /*

7.     * 源点总在vertexArray[]数组下标为0的位置，path()方法的第一个任务就是把这个顶点放入树中。

8.     * 算法执行过程中，将会把其他顶点也逐一放入树中。把顶点放入树中的操作是设置一下标志位即可。

9.     * 并把nTree变量增1，这个变量记录了树中有多少个顶点。

10.     */

11.    int startTree = 0; //从vertex 0开始

12.    vertexArray[startTree].isInTree = true;

13.    nTree = 1;

15.    /*

16.     * path()方法把邻接矩阵的对应行表达的距离复制到sPath[]中，实际总是先从第0行复制

17.     * 为了简单，假定源点的下标总为0。最开始，所有sPath[]数组中的父节点字段为A，即源点。

18.     */

19.    for(int i = 0; i < nVerts; i++) {

20.        int tempDist = adjMat[startTree][i];

21.        //sPath中保存的都是到初始顶点的距离，所以父顶点默认都是初始顶点，后面程序中会将其修改

22.        sPath[i] = new DistPar(startTree, tempDist);

23.    }

25.    /*

26.     * 现在进入主循环，等到所有的顶点都放入树中，这个循环就结束，这个循环有三个基本动作：

27.     * 1. 选择sPath[]数组中的最小距离

28.     * 2. 把对应的顶点（这个最小距离所在列的题头）放入树中，这个顶点变成“当前顶点”currentVert

29.     * 3. 根据currentVert的变化，更新所有的sPath[]数组内容

30.     */

31.    while(nTree < nVerts) {

32.        //1. 选择sPath[]数组中的最小距离

33.        int indexMin = getMin(); //获得sPath中的最小路径值索引

34.        int minDist = sPath[indexMin].distance; //获得最小路径

36.        if(minDist == INFINITY) {

37.            System.out.println("There are unreachable vertices");

38.            break;

39.        }

40.        //2. 把对应的顶点（这个最小距离所在列的题头）放入树中，这个顶点变成“当前顶点”currentVert

41.        else { //reset currentVert

42.            currentVert = indexMin;

43.            startToCurrent = sPath[indexMin].distance;

44.        }

45.        vertexArray[currentVert].isInTree = true;

46.        nTree++;

47.        //3. 根据currentVert的变化，更新所有的sPath[]数组内容

48.        adjust_sPath();

49.    }

50.    displayPaths();

52.    nTree = 0;

53.    for(int i = 0; i < nVerts; i++) {

54.        vertexArray[i].isInTree = false;

55.    }

56. }

58. //获取sPath中最小路径的索引

59. private int getMin() {

60.    int minDist = INFINITY;

61.    int indexMin = 0;

62.    for(int i = 0; i < nVerts; i++) {

63.        if(!vertexArray[i].isInTree && sPath[i].distance < minDist) {

64.            minDist = sPath[i].distance;

65.            indexMin = i;

66.        }

67.    }

68.    return indexMin;

69. }

71. /*调整sPath中存储的对象的值，即顶点到初始顶点的距离，和顶点的父顶点

72. * 这是Dijkstra算法的核心

73. */

74. private void adjust_sPath() {

75.    int column = 1;

76.    while(column < nVerts) {

77.        if(vertexArray[column].isInTree) {

78.            column++;

79.            continue;

80.        }

81.        int currentToFringe = adjMat[currentVert][column]; //获得当前顶点到其他顶点的距离，其他顶点不满足isInTree

82.        int startToFringe = startToCurrent + currentToFringe; //计算其他顶点到初始顶点的距离=当前顶点到初始顶点距离+当前顶点到其他顶点的距离

83.        int sPathDist = sPath[column].distance; //获得column处顶点到起始顶点的距离，如果不与初始顶点相邻，默认值都是无穷大

85.        if(startToFringe < sPathDist) {

86.            sPath[column].parentVert = currentVert; //修改其父顶点

87.            sPath[column].distance = startToFringe; //以及到初始顶点的距离

88.        }

89.        column++;

90.    }

91. }

92. //显示路径

93. private void displayPaths() {

94.    for(int i = 0; i < nVerts; i++) {

95.        System.out.print(vertexArray[i].label + "=");

96.        if(sPath[i].distance == INFINITY)

97.            System.out.print("infinity");

98.        else

99.            System.out.print(sPath[i].distance);

100.        char parent = vertexArray[sPath[i].parentVert].label;

101.        System.out.print("(" + parent + ") ");

102.    }

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

104. }

这里不仅仅有技术

测试代码请点击左下角“阅读原文”查看。