1 import java.util.Comparator;
2 import java.util.HashMap;
3 import java.util.LinkedList;
4 import java.util.List;
5 import java.util.Map;
6 import java.util.PriorityQueue;
7
8 public class test
9 {
10 public static void main(String[] args)
11 {
12 Graph g = new Graph();
13 /*for(Edge e : g.adjacencyMap.get(g.v6))
14 System.out.print(e.dst.name + " ");*/
15 MST_Prim(g, g.v1);
16 }
17
18 public static void MST_Prim(Graph g, Vertex s) //时间复杂度: O(elogv) e为边数 v为点数
19 {
20 PriorityQueue<Vertex> queue = new PriorityQueue<>(new Comparator<Vertex>()
21 {
22 public int compare(Vertex o1, Vertex o2)
23 {
24 return o1.key - o2.key; //最小堆
25 }
26 });
27 g.v1.key = Integer.MAX_VALUE;
28 g.v2.key = Integer.MAX_VALUE;
29 g.v3.key = Integer.MAX_VALUE;
30 g.v4.key = Integer.MAX_VALUE;
31 g.v5.key = Integer.MAX_VALUE;
32 g.v6.key = Integer.MAX_VALUE;
33 s.key = 0;
34 queue.add(g.v1);
35 queue.add(g.v2);
36 queue.add(g.v3);
37 queue.add(g.v4);
38 queue.add(g.v5);
39 queue.add(g.v6);
40 Vertex u;
41 int min_sum = 0;
42 while(!queue.isEmpty())
43 {
44 u = queue.poll(); //key值最小的先出队
45 u.isvisited = true;
46 if(u.key != 0)
47 {
48 System.out.print("(" + u.predecessor.name + "," + u.name + ")" + " ");
49 min_sum += u.key;
50 }
51 for(Edge e : g.adjacencyMap.get(u))
52 if(e.dst.isvisited == false && e.dst.key > e.weight)
53 {
54 e.dst.predecessor = u;
55 e.dst.key = e.weight;
56 queue.remove(e.dst); //最小堆化
57 queue.add(e.dst);
58 }
59 }
60 System.out.print("\n" + min_sum);
61 }
62 }
63
64 class Vertex
65 {
66 String name;
67 int key; //与当前点连接的边的最小权值
68 Vertex predecessor; //当前点的前驱
69 boolean isvisited; //是否出队
70
71 public Vertex(String name)
72 {
73 this.name = name;
74 this.key = Integer.MAX_VALUE;
75 this.predecessor = null;
76 this.isvisited = false;
77 }
78 }
79
80 class Edge
81 {
82 Vertex src;
83 Vertex dst;
84 int weight; //权值
85
86 public Edge(Vertex src, Vertex dst, int weight)
87 {
88 this.src = src; //起点
89 this.dst = dst; //终点
90 this.weight = weight;
91 }
92 }
93
94 class Graph
95 {
96 Vertex v1, v2, v3, v4, v5, v6;
97 Map<Vertex, List<Edge>> adjacencyMap;
98
99 public Graph()
100 {
101 v1 = new Vertex("v1");
102 v2 = new Vertex("v2");
103 v3 = new Vertex("v3");
104 v4 = new Vertex("v4");
105 v5 = new Vertex("v5");
106 v6 = new Vertex("v6");
107 adjacencyMap = new HashMap<>();
108
109 //v1的邻接边
110 Edge e12 = new Edge(v1, v2, 6);
111 Edge e13 = new Edge(v1, v3, 1);
112 Edge e14 = new Edge(v1, v4, 5);
113 List<Edge> v1N = new LinkedList<>();
114 v1N.add(e12);
115 v1N.add(e13);
116 v1N.add(e14);
117 adjacencyMap.put(v1, v1N);
118
119 //v2的邻接边
120 Edge e21 = new Edge(v2, v1, 6);
121 Edge e23 = new Edge(v2, v3, 5);
122 Edge e25 = new Edge(v2, v5, 3);
123 List<Edge> v2N = new LinkedList<>();
124 v2N.add(e21);
125 v2N.add(e23);
126 v2N.add(e25);
127 adjacencyMap.put(v2, v2N);
128
129 //v3的邻接边
130 Edge e31 = new Edge(v3, v1, 1);
131 Edge e32 = new Edge(v3, v2, 5);
132 Edge e34 = new Edge(v3, v4, 5);
133 Edge e35 = new Edge(v3, v5, 6);
134 Edge e36 = new Edge(v3, v6, 4);
135 List<Edge> v3N = new LinkedList<>();
136 v3N.add(e31);
137 v3N.add(e32);
138 v3N.add(e34);
139 v3N.add(e35);
140 v3N.add(e36);
141 adjacencyMap.put(v3, v3N);
142
143 //v4的邻接边
144 Edge e41 = new Edge(v4, v1, 5);
145 Edge e43 = new Edge(v4, v3, 5);
146 Edge e46 = new Edge(v4, v6, 2);
147 List<Edge> v4N = new LinkedList<>();
148 v4N.add(e41);
149 v4N.add(e43);
150 v4N.add(e46);
151 adjacencyMap.put(v4, v4N);
152
153 //v5的邻接边
154 Edge e52 = new Edge(v5, v2, 3);
155 Edge e53 = new Edge(v5, v3, 6);
156 Edge e56 = new Edge(v5, v6, 6);
157 List<Edge> v5N = new LinkedList<>();
158 v5N.add(e52);
159 v5N.add(e53);
160 v5N.add(e56);
161 adjacencyMap.put(v5, v5N);
162
163 //v6的邻接边
164 Edge e63 = new Edge(v6, v3, 4);
165 Edge e64 = new Edge(v6, v4, 2);
166 Edge e65 = new Edge(v6, v5, 6);
167 List<Edge> v6N = new LinkedList<>();
168 v6N.add(e63);
169 v6N.add(e64);
170 v6N.add(e65);
171 adjacencyMap.put(v6, v6N);
172 }
173 }