数据结构 JAVA描述（七） 图的遍历+最小生成树

时间：2021-08-17 12:29:31

广度优先搜索(Breadth First Search,BFS)+深度优先搜索（Depth First Search,DFS）

为方便起见，将两种遍历写在了一个类中。

TraverseGraph 

package Graph;

import Queue.LinkQueue;

/**
 * @description 图的遍历(广度优先搜索 + 深度优先搜索) 
 * 
 * @date 2015年12月30日
 */
public class TraverseGraph {
// 访问标志数组
private static boolean[] visited;

/**
 * @description 广度优先搜索 
 * @date 2015年12月30日
 */
public static void BFSTraverse(IGraph G) throws Exception{
        visited = new boolean[G.getVexNum()];
// 初始化标志数组
for(int v = 0; v < G.getVexNum(); v++)
            visited[v] = false;

for(int v = 0; v < G.getVexNum(); v++)
if( !visited[v])
                BFS(G, v);
    }

private static void BFS(IGraph G, int v) throws Exception{ 
        visited[v] = true;
        System.out.println(G.getVex(v).toString() + " ");
        LinkQueue Q = new LinkQueue(); //辅助队列
        Q.offer(v); //v入队列
while( !Q.isEmpty()){
//队头元素出列并赋值给u
int u = (Integer)Q.poll();
for(int w = G.firstAdjVex(u); w >= 0; w = G.nextAdjVex(u, w)){
if( !visited[w]){
                    visited[w] = true;
                    System.out.println(G.getVex(w).toString() + " ");
                    Q.offer(w);
                }
            }
        }
    }

/**
 * @description 深度优先搜索 
 * @date 2015年12月30日
 */
public static void DFSTraverse(IGraph G) throws Exception{
        visited = new boolean[G.getVexNum()];
// 初始化标志数组
for(int v = 0; v < G.getVexNum(); v++)
            visited[v] = false;

for(int v = 0; v < G.getVexNum(); v++)
if( !visited[v])
                DFS(G, v);
    }

private static void DFS(IGraph G, int v) throws Exception{ 
        visited[v] = true;
        System.out.println(G.getVex(v).toString() + " ");
for(int w = G.firstAdjVex(v); w >= 0; w = G.nextAdjVex(v, w)){
if( !visited[w]){ 
                DFS(G, w);
            } 
        }
    }
}

最小生成树：

连通图的生成树是图的极小连通子图，它包含图中的全部顶点，但只有构成一棵树的边；生成树也是图的极大无回路子图，它的边集是关联图中的所有顶点而又没有形成回路的边。 一个有n个顶点的连通图的生成树只能有n-1条边。

克鲁斯卡尔算法：

设图 T = (V, E)是图G的最小生成树：

  • T的初始状态为T = （V, 空），即开始时，最小生成树T是图G的生成零图。

  • 将图G中的边按照权值从小到大的顺序依次选取，若选取的边未使生成树T形成回路，则加入E中；否则舍弃。直至E中包含了n-1条边为止。

该算法的时间复杂度为0（e log₂ e），即取决于图的边数e

普里姆算法：

参数介绍：

  • |u，v|表示两个顶点之间的距离

  • |u，V|表示顶点u到顶点集合V中所有顶点的距离中的最小值，由于要遍历V中所有顶点，所以时间复杂度是O（|V|）

  • |U，V|表示U中所有顶点到V中所有顶点之间距离的最小值，由于要遍历U和V中的所有顶点，所以时间复杂度是O（|UV|）

基本思想：

  • 设图 T = (V, E)是图G的最小生成树，从U=｛u0｝，E=空 开始，必存在一条边（u*，v*），使得|u*，v*| = |U，V|，将（u*，v*）加入边集E中，同时将v*加入到点集U中，知道U = V为止。

  • 需要一个辅助数组，用于记录U到V-U具有最小代价的边（u*，v*），针对每一个V-U中的顶点v，在辅助数组中存在一个相应分量closedge[i]，包括该边上的权lowcost（即该顶点到U的距离|v，U|）、该边依附在U中的顶点adjvex。
    需要说明的是，表面上计算closedge[i].lowcost = |v，U|的时间复杂度是O（|U|），但实际上U是在原有基础上逐步扩大的，当有一个新元素加入U时，其实只用将closedge[i].lowcost和新加的这个元素比较即可，时间复杂度是O（1）

MiniSpanTree 

package Graph;

/**
 * @description 最小生成树的描述 
 * @date 2015年12月30日
 */
public class MiniSpanTree {
private final static int INFINITY = Integer.MAX_VALUE;

/**
 * @description 内部类辅助记录从顶点集U到V-U的代价最小的边 
 * @date 2015年12月30日
 */
private class CloseEdge {
        Object adjVex;
int lowCost;

public CloseEdge(Object adjVex, int lowCost) {
super();
this.adjVex = adjVex;
this.lowCost = lowCost;
        }
    }

/**
 * @description 用普里姆算法从第u个顶点出发构造网G的最小生成树T，返回由生成树边组成的二维数组 
 * @date 2015年12月30日
 */
private Object[][] PRIM(MGraph G, Object u) throws Exception {
        Object[][] tree = new Object[G.getVexNum() - 1][2];
int count = 0;
        CloseEdge[] closeEdge = new CloseEdge[G.getVexNum()];
int k = G.locateVex(u);

// 初始化辅助数组
for (int j = 0; j < G.getVexNum(); j++) {
if (j != k)
                closeEdge[j] = new CloseEdge(u, G.getArcs()[k][j]);
        }
        closeEdge[k] = new CloseEdge(u, 0); // 初始化U={ u }
// 选择其余G。vexNum - 1 个顶点
for (int i = 1; i < G.getVexNum(); i++) {
// 求出下一个要并入U的顶点：第k个顶点
            k = getMinMum(closeEdge);

            tree[count][0] = closeEdge[k].adjVex; // 原U中的顶点
            tree[count][1] = G.getVexs()[k]; // 要加入U中的顶点
            count++;
            closeEdge[k].lowCost = 0; // 第k个顶点并入U后，其辅助数组值置为0

/*
 * 新顶点并入U后重新选择 因为并入了一个新的顶点到U中，那么对于每个在V-U的顶点到U的最小距离可能就会改变
 * 如原本U中有v0，V-U中有v1
 * ，v2,v3，那么closeEdge[1,2,3]有个值，现在v1并入了U中，V-U中还有v2，v3，
 * 那么closeEdge[1]
 * 置0，closeEdge[2,3]就要考虑v2——v1和v3——v1的距离并和原来的值做个比较，再取其最小的值
 */
for (int j = 0; j < G.getVexNum(); j++) {
if (G.getArcs()[k][j] < closeEdge[j].lowCost)
                    closeEdge[j] = new CloseEdge(G.getVex(k), G.getArcs()[k][j]);
            }
        }
return tree;
    }

/**
 * @description 在closeEdge中选出lowCost最小且不为0的顶点 
 * @date 2015年12月30日
 */
private int getMinMum(CloseEdge[] closeEdge) {
int min = INFINITY;
int v = -1;
for (int i = 0; i < closeEdge.length; i++) {
if (closeEdge[i].lowCost != 0 && closeEdge[i].lowCost < min) {
                min = closeEdge[i].lowCost;
                v = i;
            }
        }
return v;
    }

// 测试
public static void main(String[] args) throws Exception {
        Object[] vexs = { "v0", "v1", "v2", "v3", "v4", "v5" };
int[][] arcs = { { INFINITY, 7, 1, 5, INFINITY, INFINITY },
                { 7, INFINITY, 6, INFINITY, 3, INFINITY },
                { 1, 6, INFINITY, 7, 6, 4 },
                { 5, INFINITY, 7, INFINITY, INFINITY, 2 },
                { INFINITY, 3, 6, INFINITY, INFINITY, 7 },
                { INFINITY, INFINITY, 4, 2, 7, INFINITY }, };
        MGraph G = new MGraph(GraphKind.UDG, 6, 10, vexs, arcs);
        Object[][] tree = new MiniSpanTree().PRIM(G, "v1");
for(int i = 0; i < tree.length; i++)
            System.out.println(tree[i][0]+ "-" + tree[i][1]);
    }

}

测试分析图

数据结构 JAVA描述（七） 图的遍历+最小生成树

普里姆算法构造最小生成树过程：

closedege \ i 1 2 3 4 5 U V-U k
adjvex/lowcost v0 / 7 v0 / 1 v0 / 5 {v0} {v1, v2, v3, v4, v5} 2
adjvex/lowcost v2 / 6 0 v0 / 5 v2 / 6 v2 / 4 {v0, v2} {v1, v3, v4, v5} 5
adjvex/lowcost v2 / 6 0 v5 / 2 v2 / 6 0 {v0, v2, v5} {v1, v3, v4} 3
adjvex/lowcost v2 / 6 0 0 v2 / 6 0 {v0, v2, v3, v5} {v1, v4} 1
adjvex/lowcost 0 0 0 v1 / 3 0 {v0, v1, v2, v3, v5} {v4} 4
adjvex/lowcost 0 0 0 0 0 {v0, v1, v2, v3, v4, v5} null
标签：

相关文章