🌐 AI搜索 & 代理 主页
Skip to content

Commit b4439df

Browse files
author
Lord-of-Algorithms
committed
Implement Prim’s algorithm for MST construction
1 parent 43e6ee6 commit b4439df

File tree

7 files changed

+528
-0
lines changed

7 files changed

+528
-0
lines changed

‎src/graph/WeightedGraph.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package graph;
2+
3+
/**
4+
* Represents a weighted graph capable of adding edges.
5+
*/
6+
public interface WeightedGraph extends Graph {
7+
/**
8+
* Adds a weighted edge between two vertices in the graph.
9+
*
10+
* @param source The source vertex of the edge.
11+
* @param destination The destination vertex of the edge.
12+
* @param weight The weight of the edge.
13+
*/
14+
void setEdge(Vertex source, Vertex destination, int weight);
15+
}

‎src/graph/mst/prim/EdgePriorityQueue.java‎

Lines changed: 145 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,145 @@
1+
package graph.mst.prim;
2+
3+
import graph.Edge;
4+
import graph.Vertex;
5+
6+
import java.util.NoSuchElementException;
7+
8+
/**
9+
* A priority queue specifically designed for storing and retrieving edges based on their weights,
10+
* where the edge with the smallest weight is always prioritized for retrieval.
11+
*/
12+
public class EdgePriorityQueue {
13+
14+
private final int maxSize;
15+
private final Edge[] edges;
16+
private int currentSize;
17+
18+
/**
19+
* Constructs a priority queue with a specified maximum size.
20+
*
21+
* @param maxSize the maximum number of edges the queue can hold
22+
* @throws IllegalArgumentException if maxSize is less than or equal to zero
23+
*/
24+
public EdgePriorityQueue(int maxSize) {
25+
if (maxSize <= 0) {
26+
throw new IllegalArgumentException("Maximum size must be greater than 0");
27+
}
28+
this.maxSize = maxSize;
29+
edges = new Edge[maxSize];
30+
}
31+
32+
/**
33+
* Checks if the queue is empty.
34+
*
35+
* @return true if the queue has no elements, false otherwise
36+
*/
37+
public boolean isEmpty() {
38+
return currentSize == 0;
39+
}
40+
41+
/**
42+
* Checks if the queue is full.
43+
*
44+
* @return true if the queue is at maximum capacity, false otherwise
45+
*/
46+
boolean isFull() {
47+
return currentSize == maxSize;
48+
}
49+
50+
/**
51+
* Adds an edge to the queue in a position that maintains the order of edge weights.
52+
* This method ensures that the queue is sorted such that the edge with the smallest weight can be
53+
* retrieved first, maintaining a priority queue where smaller weights signify higher priority.
54+
* It is performed in O(n) time, where n is the number of edges in the queue.
55+
*
56+
* @param edge the edge to add
57+
* @throws IllegalStateException if the queue is full
58+
*/
59+
public void add(Edge edge) {
60+
if (isFull()) {
61+
throw new IllegalStateException("Queue is full");
62+
}
63+
int i;
64+
for (i = 0; i < currentSize; i++) {
65+
if (edges[i].getWeight() <= edge.getWeight()) {
66+
// Break when find the edge with smaller weight
67+
break;
68+
}
69+
}
70+
// Move elements with smaller weight right on one position
71+
System.arraycopy(edges, i, edges, i + 1, currentSize - i);
72+
edges[i] = edge;
73+
currentSize++;
74+
}
75+
76+
/**
77+
* Retrieves, but does not remove, the smallest weight edge in the queue.
78+
*
79+
* @return the smallest weight edge, or null if the queue is empty
80+
*/
81+
Edge peekSmallest() {
82+
return currentSize == 0 ? null : edges[currentSize - 1];
83+
}
84+
85+
/**
86+
* Retrieves and removes the smallest weight edge in the queue.
87+
*
88+
* @return the smallest weight edge
89+
* @throws NoSuchElementException if the queue is empty
90+
*/
91+
public Edge pollSmallest() {
92+
if (isEmpty()) {
93+
throw new NoSuchElementException("Queue is empty");
94+
}
95+
return edges[--currentSize];
96+
}
97+
98+
/**
99+
* Replaces one edge with another and maintains the queue's order.
100+
* The replacement is performed in O(n) time, where n is the number of edges in the queue
101+
*
102+
* @param target the edge to be replaced
103+
* @param replacement the new edge to insert
104+
* @throws NoSuchElementException if the target edge is not found
105+
*/
106+
public void replace(Edge target, Edge replacement) {
107+
int index = -1;
108+
for (int i = 0; i < currentSize; i++) {
109+
if (edges[i].equals(target)) {
110+
index = i;
111+
break;
112+
}
113+
}
114+
if (index == -1) {
115+
throw new NoSuchElementException("Edge not found");
116+
}
117+
// Removing the old edge
118+
System.arraycopy(edges, index + 1, edges, index, currentSize - index - 1);
119+
currentSize--;
120+
// Adding the new edge in sorted order
121+
add(replacement);
122+
}
123+
124+
/**
125+
* Finds an edge with a specific destination.
126+
* The search is performed in O(n) time, where n is the number of edges in the queue.
127+
*
128+
* @param destination the vertex destination of the edge to find
129+
* @return the edge with the specified destination, or null if no such edge exists
130+
*/
131+
public Edge findEdgeWithDestination(Vertex destination) {
132+
int index = -1;
133+
for (int i = 0; i < currentSize; i++) {
134+
if (edges[i].getDestination().equals(destination)) {
135+
index = i;
136+
break;
137+
}
138+
}
139+
if (index != -1) {
140+
return edges[index];
141+
} else {
142+
return null;
143+
}
144+
}
145+
}

‎src/graph/mst/prim/graph/PrimGraph.java‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package graph.mst.prim.graph;
2+
3+
import graph.Edge;
4+
import graph.Vertex;
5+
import graph.WeightedGraph;
6+
7+
import java.util.List;
8+
9+
/**
10+
* Extends the functionality of a basic weighted graph to provide methods
11+
* specifically useful for implementing Prim's algorithm.
12+
*/
13+
public interface PrimGraph extends WeightedGraph {
14+
/**
15+
* Retrieves a list of all edges originating from a specified vertex.
16+
*/
17+
List<Edge> getEdgesForSource(Vertex source);
18+
19+
/**
20+
* Checks if a specific vertex is part of the graph.
21+
*
22+
* @return true if the vertex is present in the graph, false otherwise
23+
*/
24+
boolean containsVertex(Vertex vertex);
25+
26+
/**
27+
* Returns the total number of vertices in the graph.
28+
*/
29+
int getVertexCount();
30+
}

‎src/graph/mst/prim/graph/PrimListGraph.java‎

Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
package graph.mst.prim.graph;
2+
3+
import graph.Edge;
4+
import graph.Vertex;
5+
6+
import java.util.ArrayList;
7+
import java.util.HashMap;
8+
import java.util.List;
9+
import java.util.Map;
10+
11+
/**
12+
* Implements the PrimGraph interface using an adjacency list to represent the graph.
13+
*/
14+
public class PrimListGraph implements PrimGraph {
15+
16+
private final Map<Vertex, List<Edge>> adjacencyList;
17+
18+
public PrimListGraph() {
19+
adjacencyList = new HashMap<>();
20+
}
21+
22+
/**
23+
* Adds a vertex to the graph. Initializes an empty list for
24+
* edges if the vertex is new.
25+
*/
26+
@Override
27+
public void addVertex(Vertex vertex) {
28+
if (vertex == null) {
29+
throw new IllegalArgumentException("Vertex cannot be null.");
30+
}
31+
adjacencyList.putIfAbsent(vertex, new ArrayList<>());
32+
}
33+
34+
/**
35+
* Adds or updates an edge between two specified vertices with the given weight.
36+
* Since the edge properties are immutable, updating an edge will involve
37+
* removing the old edge and adding a new one.
38+
*/
39+
@Override
40+
public void setEdge(Vertex source, Vertex destination, int weight) {
41+
if (source == null || destination == null) {
42+
throw new IllegalArgumentException("Source or destination vertex cannot be null.");
43+
}
44+
45+
if (source == destination) {
46+
throw new IllegalArgumentException("Cannot add an edge from a vertex to itself.");
47+
}
48+
49+
if (!adjacencyList.containsKey(source) || !adjacencyList.containsKey(destination)) {
50+
throw new IllegalArgumentException("Both vertices must be added to the graph before connecting them.");
51+
}
52+
53+
List<Edge> edges = adjacencyList.get(source);
54+
List<Edge> reverseEdges = adjacencyList.get(destination);
55+
56+
// Remove existing edge if it exists and add new one with updated weight
57+
replaceOrUpdateEdge(edges, source, destination, weight);
58+
replaceOrUpdateEdge(reverseEdges, destination, source, weight);
59+
}
60+
61+
/**
62+
* Replaces an existing edge between specified source and destination vertices or
63+
* adds a new edge if no existing edge is found.
64+
*/
65+
private void replaceOrUpdateEdge(List<Edge> edgeList, Vertex source, Vertex destination, int weight) {
66+
Edge existingEdge = findEdge(edgeList, source, destination);
67+
if (existingEdge != null) {
68+
edgeList.remove(existingEdge); // Remove old edge since Edge properties are final
69+
}
70+
edgeList.add(new Edge(source, destination, weight)); // Add new edge with the updated weight
71+
}
72+
73+
/**
74+
* Finds an edge between a specified source and destination vertex.
75+
*/
76+
private Edge findEdge(List<Edge> edges, Vertex source, Vertex destination) {
77+
for (Edge e : edges) {
78+
if (e.getSource().equals(source) && e.getDestination().equals(destination)) {
79+
return e;
80+
}
81+
}
82+
return null;
83+
}
84+
85+
@Override
86+
public List<Edge> getEdgesForSource(Vertex source) {
87+
return adjacencyList.get(source);
88+
}
89+
90+
@Override
91+
public int getVertexCount() {
92+
return adjacencyList.size();
93+
}
94+
95+
@Override
96+
public boolean containsVertex(Vertex vertex) {
97+
return adjacencyList.containsKey(vertex);
98+
}
99+
}

‎src/graph/mst/prim/graph/PrimMatrixGraph.java‎

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
package graph.mst.prim.graph;
2+
3+
import graph.Edge;
4+
import graph.Vertex;
5+
import graph.VertexUtil;
6+
7+
import java.util.*;
8+
9+
/**
10+
* Implements the PrimGraph interface using an adjacency
11+
* matrix to represent the graph.
12+
*/
13+
public class PrimMatrixGraph implements PrimGraph {
14+
15+
private static final int NO_EDGE = Integer.MAX_VALUE;
16+
17+
// Maps each vertex to its corresponding index in the adjacency matrix.
18+
private final Map<Vertex, Integer> indicesMap;
19+
// Represents the edges between vertices.
20+
private final int[][] adjacencyMatrix;
21+
private final int maxVertices;
22+
private int currentVertexCount;
23+
24+
/**
25+
* Constructs a graph with a specified maximum number of vertices.
26+
*/
27+
public PrimMatrixGraph(int maxVertexCount) {
28+
indicesMap = new HashMap<>();
29+
adjacencyMatrix = new int[maxVertexCount][maxVertexCount];
30+
maxVertices = maxVertexCount;
31+
currentVertexCount = 0;
32+
for (int i = 0; i < maxVertexCount; i++) {
33+
Arrays.fill(adjacencyMatrix[i], NO_EDGE);
34+
}
35+
}
36+
37+
/**
38+
* Adds a vertex to the graph. Each vertex is indexed to
39+
* correspond with the adjacency matrix.
40+
*/
41+
@Override
42+
public void addVertex(Vertex vertex) {
43+
if (vertex == null) {
44+
throw new IllegalArgumentException("Vertex cannot be null.");
45+
}
46+
if (currentVertexCount >= maxVertices) {
47+
throw new IllegalStateException("Maximum vertices limit reached.");
48+
}
49+
indicesMap.putIfAbsent(vertex, currentVertexCount++);
50+
}
51+
52+
/**
53+
* Sets or updates the weight of the edge between the
54+
* given source and destination vertices.
55+
*/
56+
@Override
57+
public void setEdge(Vertex source, Vertex destination, int weight) {
58+
if (source == null || destination == null) {
59+
throw new IllegalArgumentException("Source or destination vertex cannot be null.");
60+
}
61+
if (source == destination) {
62+
throw new IllegalArgumentException("Cannot add an edge from a vertex to itself.");
63+
}
64+
if (!indicesMap.containsKey(source)) {
65+
throw new IllegalArgumentException("Source vertex does not exist in the graph.");
66+
}
67+
if (!indicesMap.containsKey(destination)) {
68+
throw new IllegalArgumentException("Destination vertex does not exist in the graph.");
69+
}
70+
71+
int sourceIndex = indicesMap.get(source);
72+
int destinationIndex = indicesMap.get(destination);
73+
74+
adjacencyMatrix[sourceIndex][destinationIndex] = weight;
75+
adjacencyMatrix[destinationIndex][sourceIndex] = weight;
76+
}
77+
78+
@Override
79+
public List<Edge> getEdgesForSource(Vertex source) {
80+
Integer index = indicesMap.get(source);
81+
if (index == null) {
82+
throw new IllegalArgumentException("Vertex does not exist in the graph");
83+
}
84+
List<Edge> edges = new ArrayList<>();
85+
86+
for (int i = 0; i < adjacencyMatrix[index].length; i++) {
87+
if (adjacencyMatrix[index][i] != NO_EDGE) { // Check if there's an edge
88+
Vertex neighbor = VertexUtil.getVertexByIndex(indicesMap, i);
89+
edges.add(new Edge(source, neighbor, adjacencyMatrix[index][i]));
90+
}
91+
}
92+
return edges;
93+
}
94+
95+
@Override
96+
public int getVertexCount() {
97+
return currentVertexCount;
98+
}
99+
100+
@Override
101+
public boolean containsVertex(Vertex vertex) {
102+
return indicesMap.get(vertex) != null;
103+
}
104+
}

0 commit comments

Comments
 (0)