经典的贪心策略 Prim算法，Kruskal算法求最小生成树，dijkstra求最短路径

最小生成树算法 用到的并查集 在之前博客写，图都是下面的，最小生成树无向就行了

/**
 * 文件名：GraphTest2.java
 * 时间：2max14年11月17日下午6:2max:1max
 * 作者：修维康
 */
package chapter9;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

import chapter8.DisjSets;//并查集

/**
 * 类名：Edeg 说明：边
 */
class Edge {
	public int v1;
	public int v2;
	public int dist;

	public Edge(int v1, int v2, int dist) {
		this.v1 = v1;
		this.v2 = v2;
		this.dist = dist;// 权值
	}

}

class DistComparator implements Comparator<Edge> {

	@Override
	public int compare(Edge o1, Edge o2) {
		// TODO Auto-generated method stub
		if (o1.dist > o2.dist)
			return 1;
		else if (o1.dist < o2.dist)
			return -1;
		return 0;
	}

}

public class GraphTest2 {

	public static final int max = Integer.MAX_VALUE;

	/**
	 * 方法名：dijkstra 说明：迪杰斯克拉算法，V代表源 g存储图的信息，dist[i]代表到v到i的权,prev[i]代表 顶点i的前一个顶点
	 */
	public static void Dijkstra(int v, int n, int[][] g, int[] dist, int[] prev) {
		boolean[] s = new boolean[n + 1];
		for (int i = 1; i <= n; i++) {
			dist[i] = g[v][i];
			s[i] = false;
			if (dist[i] == max)
				prev[i] = 0;
			else
				prev[i] = v;
		}
		s[v] = true;
		dist[v] = 0;
		// 从V-S中找到权值最小的边
		for (int i = 1; i < n; i++) {
			int temp = max;
			int u = v;
			for (int j = 1; j <= n; j++)
				if (!s[j] && temp > dist[j]) {
					temp = dist[j];
					u = j;
				}
			s[u] = true;
			// 更新
			for (int j = 1; j <= n; j++) {
				if (!s[j] && g[u][j] < max) {
					int newDist = dist[u] + g[u][j];
					if (newDist < dist[j]) {
						dist[j] = newDist;
						prev[j] = u;
					}
				}
			}
		}

	}

	/**
	 * 方法名：printPath 说明：打印最短路径
	 */
	public static void printPath(int[] prev, int v) {
		System.out.print(v + " ");
		while (prev[v] != 0) {
			System.out.print(prev[v] + " ");
			v = prev[v];
		}
	}

	/**
	 * 方法名：Prim 说明：最小生成树 Prim算法 lowcost[i]为顶点i到S集合中任意一点 最小的权值 closest[i]为
	 * S中与i顶点相连权值最小的顶点
	 */
	public static void Prim(int[][] g, int n) {
		boolean[] s = new boolean[n + 1];
		int[] lowcost = new int[n + 1];
		int[] closest = new int[n + 1];
		s[1] = true;
		lowcost[1] = 0;
		for (int i = 2; i <= n; i++) {
			lowcost[i] = g[1][i];
			closest[i] = 1;
			s[i] = false;
		}
		// 从V-S中找到与S中的顶点相连 且权值最小的点
		for (int i = 1; i < n; i++) {
			int min = max;
			int j = 1;
			for (int k = 2; k <= n; k++) {
				if (!s[k] && lowcost[k] < min) {
					min = lowcost[k];
					j = k;
				}
			}
			s[j] = true;
			System.out.println(j + "  " + closest[j]);
			// 重新更新 lowcost lowcost[i]为顶点i到S集合中任意一点 最小的权值
			for (int k = 2; k <= n; k++) {
				if (!s[k] && g[j][k] < lowcost[k]) {
					lowcost[k] = g[j][k];
					closest[k] = j;

				}
			}
		}

	}

	/**
	 * 方法名：Kruskal 说明：最小生成树 Kruskal算法
	 */
	public static void Kruskal(PriorityQueue<Edge> p, int n) {
		DisjSets ds = new DisjSets(n + 1);// 并查集
		Edge e;
		int edgesAccepted = 0;
		while (edgesAccepted < n - 1) {
			e = p.poll();
			int uset = ds.find(e.v1);
			int vset = ds.find(e.v2);
			if (uset != vset) {
				edgesAccepted++;
				System.out.println(e.v1 + " " + e.v2);
				ds.union1(uset, vset);
			}

		}

	}

	/**
	 * 方法名：main 说明：测试
	 */

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] g = new int[][] { { max, max, max, max, max, max, max, max },
				{ max, max, 2, max, 1, max, max, max },
				{ max, max, max, max, 3, 10, max, max },
				{ max, 4, max, max, max, max, 5, max },
				{ max, max, max, 2, max, 2, 18, 4 },
				{ max, max, max, max, max, max, max, 6 },
				{ max, max, max, max, max, max, max, max },
				{ max, max, max, max, max, max, 1, max } };
		// Graph graph = new Graph(g);
		int[] dist = new int[8];
		int[] prev = new int[8];
		Scanner in = new Scanner(System.in);
		System.out.println("请输入顶点号：");
		int v = in.nextInt();
		Dijkstra(v, 7, g, dist, prev);
		System.out.println("请输入目的顶点：");
		int n = in.nextInt();
		System.out.println("顶点" + v + "到顶点" + n + "的权值为" + dist[n]);
		printPath(prev, n);
		int[][] g2 = new int[][] { { max, max, max, max, max, max, max, max },
				{ max, max, 2, 4, 1, max, max, max },
				{ max, 2, max, max, 3, 10, max, max },
				{ max, 4, max, max, 2, max, 5, max },
				{ max, 1, 3, 2, max, 7, 8, 4 },
				{ max, max, 10, max, 7, max, max, 6 },
				{ max, max, max, 5, 8, max, max, 1 },
				{ max, max, max, max, 4, 6, 1, max } };
		Prim(g2, 7);
		PriorityQueue<Edge> p = new PriorityQueue<Edge>(12,
				new DistComparator());
		p.add(new Edge(1, 2, 2));
		p.add(new Edge(1, 4, 1));
		p.add(new Edge(2, 4, 3));
		p.add(new Edge(1, 3, 4));
		p.add(new Edge(3, 4, 2));
		p.add(new Edge(4, 5, 7));
		p.add(new Edge(2, 5, 10));
		p.add(new Edge(3, 6, 5));
		p.add(new Edge(4, 6, 8));
		p.add(new Edge(6, 7, 1));
		p.add(new Edge(4, 7, 4));
		p.add(new Edge(5, 7, 6));
		System.out.println("Kruskal算法：");
		Kruskal(p, 7);
	}
}

最小生成树，最短路径算法