数据结构 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