数据结构图的最小生成树：普里姆，以及最短路径：迪杰斯特拉算法_最小生成树可以有回路嘛

基于《数据结构Java语言描述》1、 最小生成树：
从最小生成树的定义可知，构造有n个顶点的无向连通带权图的最小生成树，必须满足以下三个条件：
(1)构造的最小生成树必须包括n个顶点；
(2)构造的最小生成树中有且仅有n-1条边；
(3)构造的最小生成树中不能存在回路。
普里姆算法：要圈不要一边。


Prim算法

//顶点定义
public class MinSpanTreeNode {
    public int vertex;//顶点
    public int weight;//权值
    public MinSpanTreeNode(){
        super();
    }
    public MinSpanTreeNode(int vertex,int weight){
        super();
        this.vertex=vertex;
        this.weight=weight;
    } }
1
2
3
4
5
6
7
8
9
10
11
12

//算法实现类
public class Prim {
	static final int maxWeight = 10000;// 权值无穷大
	public static void prim(AMGraph<Character> g, MinSpanTreeNode[] minSpanTree)
			throws Exception {
		int n = g.getNumOfVertices();// 图中顶点个数
		int minCost;// 最小权值
		int[] lowCost = new int[n];//
		int k = 0;
		for (int i = 1; i < n; i++) {
			lowCost[i] = g.getWeight(0, i);// lowCost的初始值:第0行的值
		}
		MinSpanTreeNode temp = new MinSpanTreeNode();
		// 从顶点0出发构造最小生成树
		temp.vertex = 0;
		minSpanTree[0] = temp;// 保存顶点0
		lowCost[0] = -1;// 表示顶点加入集合U
		for (int i = 1; i < n; i++) {
			// 寻找当前最小权值的边以及所对应的另一端顶点k
			minCost = maxWeight;
			for (int j = 1; j < n; j++) {
				if (lowCost[j] < minCost && lowCost[j] > 0) {
					minCost = lowCost[j];
					k = j;					
				}
			}			
			MinSpanTreeNode curr = new MinSpanTreeNode();
			curr.vertex = k;// 保存顶点k
			curr.weight = minCost;// 保存相应权值
			minSpanTree[i] = curr;
			lowCost[k] = -1;// 标记顶点k
			// 根据加入集合U的顶点k修改lowCost中的值
			for (int j = 1; j < n; j++) {
				if (g.getWeight(k, j) < lowCost[j]) {
					lowCost[j] = g.getWeight(k, j);
				}
			}			
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

//测试代码类
public class TestPrim {	
	
	public static void createGraph(AMGraph<Character> g, Character[]v,int n,Edge[] edge,int e)throws Exception{
		//static成员方法，用所给参数创建邻接矩阵类对象g
		//v为所有顶点集合，n为顶点个数，edge为边的集合，e为边的数目
		for(int k=0;k<n;k++){
			g.insertVertex(v[k]);
		}
		for(int k=0;k<e;k++){
			g.insertEdge(edge[k].i, edge[k].j, edge[k].weight);
		}
	}
	public static void main(String[] args) {
		int n=7,e=20;
		AMGraph<Character> g=new AMGraph<>(n);		
		Character[] v={'A','B','C','D','E','F','G'};
		Edge[] edge={new Edge(0, 1, 60),new Edge(1, 0, 60),
				new Edge(0, 2, 50),new Edge(2, 0, 50),
				new Edge(1, 3, 52),new Edge(3, 1, 52),
				new Edge(1, 4, 45),new Edge(4, 1, 45),
				new Edge(2, 3, 65),new Edge(3, 2, 65),
				new Edge(2, 5, 40),new Edge(5, 2, 40),
				new Edge(3, 4, 42),new Edge(4, 3, 42),
				new Edge(3, 5, 50),new Edge(5, 3, 50),
				new Edge(3, 6, 30),new Edge(6, 3, 30),
				new Edge(5, 6, 70),new Edge(6, 5, 70)
		};	
		try {
			createGraph(g, v, n, edge, e);
			MinSpanTreeNode[] minSpanTree=new MinSpanTreeNode[7];
			Prim.prim(g, minSpanTree);//调用Prim方法
			//输出Prim算法得到的最小生成树的顶点序列和权值序列
			System.out.println("初始顶点为="+g.getValue(minSpanTree[0].vertex));
			for(int i=1;i<n;i++){
				System.out.print("顶点="+g.getValue(minSpanTree[i].vertex));
				System.out.println(" 边的权值="+minSpanTree[i].weight);
				
			}
		} catch (Exception e1) {
			// TODO Auto-generated catch block
			e1.printStackTrace();
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

2、 最短路径单：
前言：在一个图中，若从一个顶点到另外一个顶点存在路径，路径长度就是一条路径上所经过的边的数目。图中从一个顶点到另外一个顶点可能存在多条路径，路径长度最短的那条路径叫做最短路径，其路径长度称为最短路径长度或最短距离。
迪杰斯特拉：怕圈，三边不能成圈。
（1）用迪杰斯特拉（Dijkstra）算法求下图G中顶点A到其余各顶点的最短距离

Dijkstra算法实现

package com.my.bean;
public class Dijkastra {
	static final int maxWeight = 10000;// 权值无穷大
	public static void dijkastra(AMGraph<Character> g,int v,int[] distance,int[] path)throws Exception{
		//带权图g从下标v0顶点到其他顶点的最短距离distance
		//目标顶点的前一个顶点下标path
		int n=g.getNumOfVertices();
		boolean[] selected=new boolean[n];//selected用来存放n个顶点的标记,默认为false
		int minDis,u=0;		
		//初始化
		selected[v]=true;//将源点v加入S
		for(int i=1;i<n;i++){
			distance[i]=g.getWeight(v, i);
			if(i!=v&&distance[i]<maxWeight){
				path[i]=v;//初始的目标顶点的前一个顶点均为v
			}else{
				path[i]=-1;
			}
		}				
		//在当前顶点集V-S中选取具有最短距离的顶点u
		for(int i=1;i<n;i++){
			minDis=maxWeight;
			for(int j=0;j<n;j++){
				if(selected[j]==false&& distance[j]<minDis){
					u=j;
					minDis=distance[j];
				}
			}			
			//当已不存在路径是算法结束；此语句对于非连通图是必须的
			if(minDis==maxWeight)return;
			
			selected[u]=true;//标记顶点u已从集合V-S中加入到S中
		
			//修改从v0到其他顶点的最短距离和最短路径
			for(int j=0;j<n;j++){
				if(selected[j]==false&&g.getWeight(u, j)<maxWeight&&distance[u]+g.getWeight(u, j)<distance[j]){
					distance[j]=distance[u]+g.getWeight(u, j);
					path[j]=u;
				}
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

如有不对请指正！