Show code
<think>
Okay, I need to create a self-contained HTML file that animates Prim's algorithm on a canvas. Let me start by understanding the requirements. The user wants the animation to show Prim's MST algorithm step by step, with nodes scattered randomly, edges between nodes within a certain radius, weights based on distance. The animation should highlight candidate edges, add the cheapest one each step, and show the progression of the total weight. Also, a line graph below showing the accumulated weight and the count of edges added. When done, it restarts with a new graph.
First, I'll structure the HTML. The canvas needs to be in the body, with some styles to center it. The total characters are limited to 7000, so I have to keep it concise. I'll use JavaScript inside the HTML.
Starting with the canvas setup. I'll set the canvas size to 600x400, maybe. Then, in the JavaScript part, I'll need to handle the animation loop with requestAnimationFrame. The animation should run smoothly without user input, so once it starts, it continues indefinitely.
For the nodes, I'll randomly generate their positions. Maybe 20-25 nodes. Let's say 20. Each node is an object with x, y coordinates. I can use Math.random() for that.
Edges need to connect nodes within a radius. Let's choose a radius, maybe 150 pixels. For each pair of nodes, calculate the distance. If within radius, create an edge. The weight is the distance, so I'll store edges between each such pair.
Prim's algorithm starts with a random node. I'll pick one randomly as the starting point. The tree starts with this node. Then, each step finds the cheapest edge connecting the tree to non-tree nodes. To do this efficiently, maybe track all edges and filter those that have one end in the tree and the other not. Then pick the minimum weight among those.
Each step should highlight the candidate edges. Wait, the user said to highlight the candidate edges under consideration. But Prim's algorithm at each step selects the minimum edge from all candidates. So perhaps, during each step, I can draw all possible edges from the current tree to non-tree nodes, then pick the cheapest one, and then add it. So to visualize, maybe first show all possible edges (highlighted in some way?), then pick the cheapest and add it to the tree.
Wait, but the problem says: "highlight the candidate edges under consideration". So perhaps first, when looking for the next edge, all candidate edges (those connecting tree and non-tree nodes) are drawn in a different color, then the chosen one is added. But how to animate that step? Maybe in the animation frame, first draw all candidates, then after a short delay, add the selected one. But since everything is in requestAnimationFrame, timing might be tricky. Alternatively, have the step-by-step animation where each step is a frame where first the candidates are shown, then the chosen edge is added. But since it's all in one function, maybe just draw the candidates as dashed lines or something, then add the chosen edge.
Alternatively, to simplify, perhaps during each step, the candidate edges are highlighted (maybe a different color) for a moment before selecting the cheapest. But I need to make sure the animation is smooth. Maybe the candidates are drawn as dotted lines, then the selected one is drawn as solid and added to the tree.
The line graph below the canvas needs to track the accumulated weight. Each step adds the new edge's weight to the total. So on the line graph, each step adds a point, with x as the edge count (starting at 0) and y as the accumulated weight.
Now, the structure:
- Canvas element.
- JavaScript variables for nodes, edges, tree, current step, etc.
- Animation loop that steps through Prim's algorithm, advancing each step when possible.
- When all nodes are in the tree, restart.
First, variables setup:
- nodes array: each has x, y, inTree (boolean).
- edges: array of objects with a, b (node indices), weight (distance), and maybe a highlight flag.
- tree: the nodes in the current MST.
- starting node chosen at random.
- step counter: how many edges have been added (starts at 0, needs to reach nodes.length -1).
- totalWeight: accumulates the edge weights.
- animation is in a loop with requestAnimationFrame.
The main steps in the algorithm:
1. Initialize nodes, edges.
2. Pick a starting node, mark it as in tree.
3. While there are nodes not in the tree:
a. Find all edges that connect in-tree and out-of-tree nodes.
b. Among those, pick the one with minimum weight.
c. Add that edge to the MST, mark the new node as in tree.
d. Update totalWeight with the edge's weight.
e. Increment step counter.
f. Then, after a delay, proceed to next step.
But to animate each step, the animation loop must handle each step as a frame. Wait, but how to control the steps. Since the animation runs on requestAnimationFrame, which is per frame, perhaps the steps are advanced each frame until completion, but with a slight delay between steps. Alternatively, have a counter that increments each frame until a threshold, and when that happens, advance to the next step.
Alternatively, use a flag and a timer. Let me think: when starting, the first step is initializing everything and starting the first step. Then, each step takes a frame, but you need to pause between steps. Hmm, maybe use a step counter and only advance when a certain amount of frames have passed. For example, after drawing the current step, wait for a few frames before proceeding to the next step. But since requestAnimationFrame is asynchronous, this might be tricky.
Alternatively, in the animation function, if the algorithm hasn't completed, then each frame checks if it's time to advance the step. For example, track the time since the last step and when it reaches a threshold (like 1 second between steps), then advance.
But perhaps to keep it simple, each step is done when the animation loop reaches a certain condition. Let's structure it so that the animation loop first checks if the algorithm is in progress. If yes, then it draws all elements, and if necessary, moves to the next step.
Wait, here's a possible approach:
- The algorithm is in progress if the current step count is less than nodes.length -1.
- In each frame (animation loop):
- If the algorithm is still in progress:
- Draw the current state (nodes, edges, highlighted edges, etc.)
- If it's time to proceed to the next step, then compute the next step (find the next edge, add it to the tree, etc.)
- Else:
- Delay for a moment, then restart the algorithm with new nodes and starting point.
The timing can be controlled by a variable stepDelay, counting down. For example, whenever you move to a new step, set a countdown, and only advance when countdown reaches zero.
Alternatively, use a flag to indicate whether to process the next step now.
Alternatively, in the animation loop, whenever it's time to process the next step (based on a timer), then process it. But integrating this with requestAnimationFrame might be a bit involved.
Alternatively, after each step, schedule a timeout to trigger the next step. But requestAnimationFrame is better because it integrates with the browser's repaint cycle.
Hmm, perhaps the steps can be advanced each time the animation frame is called, but with a delay between steps. Let me think in code terms.
Let me draft a rough structure:
Variables:
const canvas = ...;
const ctx = ...;
let nodes = [];
let edges = [];
let inTree = [] // or part of nodes
let startNode = 0;
let stepCount = 0;
let totalWeight = 0;
let isRunning = true;
let nextStepTime = Date.now();
function animate() {
if (isRunning) {
const now = Date.now();
if (now >= nextStepTime) {
// process next step
if (stepCount < nodes.length -1) {
... find next edge ...
stepCount++;
nextStepTime = now + 1000; // wait 1 sec between steps
} else {
// done, reset after a short delay
nextStepTime = now + 2000;
if (now >= nextStepTime) {
reset(); // generate new graph and start over
nextStepTime = Date.now() + 1000; // reset next step time?
}
}
}
// draw everything
draw();
requestAnimationFrame(animate);
}
}
But this might not be precise. Alternatively, use a step counter and increment it after a delay.
Alternatively, the step is advanced each animation frame, but after a certain number of frames.
Hmm, perhaps it's better to use a step counter and in each animation loop, check if it's time to advance to the next step (i.e., when enough frames have passed). Let's say each step takes 1 second. Then, for example:
let stepTimer = 0;
const stepDuration = 1000; // in ms
function animate() {
// calculate delta
// but since it's requestAnimationFrame, maybe use a timestamp
// but perhaps track time since last step
const now = performance.now();
if (isRunning) {
if (now - stepTimer >= stepDuration) {
stepTimer = now;
advanceStep(); // process next step of Prim's
}
draw();
requestAnimationFrame(animate);
}
}
But then the initial stepTimer must be set properly. Maybe when starting, the first step is processed immediately, then stepTimer is set to now + stepDuration?
Alternatively, track the time when the next step can be done. Let me think:
Initialize stepTime = 0.
In each frame:
If stepTime is 0 (meaning not started yet), then process first step, set stepTime to now + stepDuration.
Else, if current time >= stepTime, process the next step, set stepTime to now + stepDuration.
But this way, each step happens at intervals of stepDuration.
But then, when starting over after completion, we need to reset stepTime to 0 again.
This might be manageable.
Now, for the nodes and edges.
Generating nodes: in setup(), generate nodes randomly.
function setup() {
nodes = [];
const count = 20; // or 20-25, maybe Math.floor(Math.random()*5)+20
for (let i=0; i < count; i++) {
nodes.push({x: Math.random()*canvas.width, y: Math.random()*canvas.height, inTree: false});
}
// pick starting node
startNode = Math.floor(Math.random() * nodes.length);
nodes[startNode].inTree = true;
// create edges between nodes within radius (say, 150)
edges = [];
for (let i=0; i < nodes.length; i++) {
for (let j=i+1; j < nodes.length; j++) {
const dx = nodes[i].x - nodes[j].x;
const dy = nodes[i].y - nodes[j].y;
const dist = Math.sqrt(dx*dx + dy*dy);
if (dist < 150) {
edges.push({a:i, b:j, weight: dist});
}
}
}
// reset other variables
stepCount = 0;
totalWeight = 0;
isRunning = true;
stepTimer = 0;
}
Then, when the algorithm is done (stepCount == nodes.length -1), after a delay, call setup again to reset.
Now, the advanceStep() function:
function advanceStep() {
if (stepCount >= nodes.length -1) {
// done, schedule reset
setTimeout(setup, 2000); // wait 2 sec before restarting
isRunning = false;
return;
}
// find all edges connecting tree and non-tree nodes
let minEdge = null;
let minDist = Infinity;
for (const edge of edges) {
const aIn = nodes[edge.a].inTree;
const bIn = nodes[edge.b].inTree;
if (aIn != bIn) { // one is in, the other not
const weight = edge.weight;
if (weight < minDist) {
minEdge = edge;
minDist = weight;
}
}
}
// now add the chosen edge to the tree
const a = minEdge.a;
const b = minEdge.b;
const nodeA = nodes[a];
const nodeB = nodes[b];
if (nodeA.inTree) {
nodeB.inTree = true;
} else {
nodeA.inTree = true;
}
totalWeight += minEdge.weight;
stepCount++;
}
Wait, but how to track which nodes are in the tree. The nodes have inTree flags. So when adding the edge, whichever node is not in the tree is added to the tree.
But in this code, the edge could be either way, so need to check which node is in the tree, then set the other to inTree.
Once the edge is added, the step is advanced.
Now, in the drawing function, need to draw all nodes (inTree vs not), edges, the selected edge, and the line graph.
The edges can be drawn in different colors: those within the tree (the MST edges) are one color, the candidate edges (the ones connecting tree to non-tree) can be another, but in the case of Prim's, the current step's candidate is only the min edge?
Wait, the problem says "highlight the candidate edges under consideration", but in the algorithm, when choosing the next edge, all possible edges that connect the current tree to non-tree nodes are considered, but only the minimum one is selected. So perhaps, in the drawing phase before selecting the edge, all those edges are highlighted, then the selected one becomes part of the tree.
But how to represent this in the animation.
Perhaps during the step's processing, before drawing, we can highlight all candidate edges (the ones that connect tree and non-tree nodes), then after selecting the min edge, add it to the tree and draw it as part of the tree.
Alternatively, in the drawing function, edges that are part of the current tree are drawn in green, edges not yet in the tree can be drawn in gray. But during the selection phase (i.e., between steps), before the next edge is chosen, the candidate edges (those connecting tree and non-tree nodes) could be drawn in a different color (like yellow) to show they're candidates, then when the step proceeds, the selected edge becomes part of the tree.
Wait, but in the animate function, the advanceStep() is called once per step, but the drawing needs to show the candidate edges before the step is taken. Hmm, this is a bit tricky. So perhaps before advancing to the next step, the candidate edges are drawn, then after the step is taken, the selected edge is part of the tree.
Alternatively, after the step has been processed (i.e., the edge has been added), the next frame shows the new state.
Wait, the problem says "highlight the candidate edges under consideration". So during the step, when the algorithm is selecting the next edge, all candidate edges (those that bridge tree and non-tree nodes) should be highlighted. But since each step is a single frame (or a brief period), how to show that?
Perhaps the candidate edges are drawn in a different color (e.g., red dashed lines) during the step, but only for that frame before the selection is made. However, since the animation runs continuously, the actual selection happens instantly, so the user might not see it. Therefore, perhaps during the step's drawing phase, all candidate edges are highlighted, and the selected one is drawn as part of the tree in the next frame.
Hmm, perhaps when advancing the step, first the algorithm finds the next edge, but the drawing for the current step shows all candidate edges (the ones that could be chosen), then the next step shows the selected edge as part of the tree. Alternatively, the candidate edges are the current candidates (the edges being considered) before the step is processed, but in the drawing function, perhaps all non-tree edges that are candidates are highlighted.
Alternatively, during the drawing phase, edges are drawn as follows:
- For each edge, if both nodes are in the tree: draw in green (part of the tree).
- If one node is in the tree and the other isn't: draw as a candidate edge (maybe red or dashed).
- The edge that was just added in this step can be highlighted with a different color, like blue, but only for a moment.
Wait, perhaps the selected edge is drawn in a different color (e.g., red) during the step, but in the next step it becomes part of the tree (green). Wait, but how to track which edge was just added?
Alternatively, during the animation, after processing the step (i.e., selecting the edge), the edge is part of the tree. So in the drawing function, edges can be colored based on whether both nodes are in the tree.
Wait, but the edges are part of the tree only if both nodes are in the tree. So any edge that has both nodes in the tree is part of the tree. The algorithm ensures that edges are added only when one node is already in the tree. So after adding the edge, the other node is now in the tree, so the edge is now between two nodes in the tree.
Thus, in the drawing function, edges between two inTree nodes are drawn as part of the tree (green).
Other edges (non-tree) are either connecting nodes both not in the tree (drawn in light gray) or one in and one out (drawn in dashed red or something).
So in the drawing function:
for each edge in edges:
const a = nodes[edge.a], b = nodes[edge.b];
if (a.inTree && b.inTree) {
draw edge in green.
} else if (a.inTree || b.inTree) {
draw edge in red dashed line? (candidate edges)
} else {
draw edge in gray.
}
Wait, but the candidate edges during the step are the ones where exactly one node is in the tree. So those edges (candidates) can be drawn in a different color, like orange.
Additionally, the edge that was just added in this step can be highlighted with a different color for a moment (like blue), but this might complicate things.
Alternatively, just draw the candidates (edges between tree and non-tree nodes) in orange, and the tree edges in green.
The problem says to highlight the candidate edges under consideration. So that would be the edges between the current tree and non-tree nodes, which are drawn in orange, for example.
Now, the drawing function.
First, clear the canvas.
Then draw all edges:
for (const edge of edges) {
const a = nodes[edge.a], b = nodes[edge.b];
ctx.beginPath();
ctx.moveTo(a.x, a.y);
ctx.lineTo(b.x, b.y);
if (a.inTree && b.inTree) {
ctx.strokeStyle = 'green';
ctx.lineWidth = 2;
} else if (a.inTree || b.inTree) {
ctx.strokeStyle = 'orange';
ctx.lineWidth = 1;
ctx.setLineDash([5, 5]); // dashed
} else {
ctx.strokeStyle = 'lightgray';
ctx.lineWidth = 1;
}
ctx.stroke();
}
Then reset line dash:
ctx.setLineDash([]);
Then draw the nodes:
for (const node of nodes) {
ctx.beginPath();
ctx.arc(node.x, node.y, 5, 0, 2*Math.PI);
ctx.fillStyle = node.inTree ? 'green' : 'red';
ctx.fill();
}
Then draw the line graph.
Assuming the line graph is on the side or bottom, but since the problem doesn't specify, perhaps it's a small chart below the main canvas. But for simplicity, we can draw a small bar chart on the right side or something. Alternatively, just a line indicating the current step and total weight.
Alternatively, perhaps just write the total weight and current step in text.
But the problem says "create" the visualization, so perhaps a small bar graph next to the canvas.
Alternatively, the line graph can be drawn as a small chart on the right.
Let me think of the canvas as having main area for the graph and a small area for the line graph.
Suppose the canvas is 600x400, then maybe the line graph is in a 50x400 area on the right.
So:
const lineGraphWidth = 50;
const graphAreaWidth = canvas.width - lineGraphWidth;
ctx.fillStyle = 'white';
ctx.fillRect(0, 0, canvas.width, canvas.height);
// draw the main graph in the left area
Then draw the line graph in the right area.
To draw the line graph, which represents the steps taken. For each step, the height corresponds to the accumulated weight so far.
But since we need to track the weight per step, perhaps store an array of the total weight at each step.
Wait, in the setup function, perhaps initialize an array called 'weightHistory' which records the totalWeight after each step.
Wait in advanceStep():
totalWeight += minEdge.weight;
stepCount++;
so, in setup(), initialize weightHistory as empty array.
Then in advanceStep():
if (stepCount > nodes.length -1) { ... }
else {
... process edge ...
totalWeight += minEdge.weight;
stepCount++;
// record the weightHistory
weightHistory.push(totalWeight);
}
Then in the drawing function:
if we have the weightHistory, which is an array of the weight at each step.
The line graph would show the progression of totalWeight over the steps.
Thus, in the drawing function:
const barHeight = (canvas.height / weightHistory.length);
Wait, perhaps it's better to scale it to the canvas height.
Alternatively, the line graph can be a simple line plot where each step is a point, and the line connects them.
Suppose the line graph is drawn in the rightmost 50 pixels.
ctx.strokeStyle = 'blue';
ctx.beginPath();
ctx.moveTo( graphAreaWidth, canvas.height - (weightHistory[0]/maxWeight)*canvas.height ); // need to compute maxWeight?
Wait, perhaps compute the maximum weight possible and scale accordingly.
Alternatively, just use the current totalWeight as a proportion.
Alternatively, just draw a bar graph where each bar's height corresponds to the weight at that step.
But since it's a line graph, perhaps draw a line that goes up as steps are taken.
Alternatively, draw a bar chart where each bar is a step's contribution.
Hmm, perhaps a simple bar for each step in the line graph area.
Alternatively, the line graph can be a small line plot, but this requires keeping track of all steps.
Alternatively, just show the current step and total weight as text.
Well, the problem says "create" the visualization, so probably okay to have a simple text display.
But to follow the problem's instruction, perhaps a small line graph.
Alternatively, just display the total weight.
Let me think:
In the drawing function, after drawing the main graph:
ctx.fillStyle = 'black';
ctx.font = '16px Arial';
ctx.fillText(`Total Weight: ${totalWeight.toFixed(2)}`, 10, 30);
ctx.fillText(`Step: ${stepCount}`, 10, 50);
Maybe that's sufficient.
Now, putting all together.
The code outline would be:
HTML:
<canvas id="canvas" width="600" height="400"></canvas>
JS:
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
let nodes = [];
let edges = [];
let stepCount = 0;
let totalWeight = 0;
let isRunning = true;
let stepTimer = 0;
const stepDuration = 1000; // milliseconds
function setup() {
// reset all variables, generate nodes and edges
// ...
}
function draw() {
// clear canvas
ctx.clearRect(0, 0, canvas.width, canvas.height);
// draw edges
for (const edge of edges) {
// draw each edge with appropriate color
}
// draw nodes
for (const node of nodes) {
// draw each node green or red
}
// draw total weight and step count
ctx.fillText(...);
}
function advanceStep() {
// find next edge to add to the MST
// update nodes and totalWeight
}
function animate() {
const now = performance.now();
if (isRunning) {
if (now - stepTimer >= stepDuration) {
stepTimer = now;
advanceStep();
}
draw();
}
requestAnimationFrame(animate);
}
But I need to implement all the functions.
Now, let's code this step by step.
First, the setup function:
function setup() {
const count = 20 + Math.floor(Math.random() * 5); // 20 to 25 nodes
nodes = [];
for (let i = 0; i < count; i++) {
const x = Math.random() * (canvas.width - 10) + 5; // avoid edges
const y = Math.random() * (canvas.height - 10) + 5;
nodes.push({ x, y, inTree: false });
}
// set starting node
const startNodeIndex = Math.floor(Math.random() * nodes.length);
nodes[startNodeIndex].inTree = true;
edges = [];
// create edges between nodes within radius 150
const radius = 150;
for (let i = 0; i < nodes.length; i++) {
for (let j = i + 1; j < nodes.length; j++) {
const dx = nodes[i].x - nodes[j].x;
const dy = nodes[i].y - nodes[j].y;
const dist = Math.hypot(dx, dy);
if (dist < radius) {
edges.push({ a: i, b: j, weight: dist });
}
}
}
// reset variables
stepCount = 0;
totalWeight = 0;
isRunning = true;
stepTimer = -stepDuration; // so the first step is triggered immediately
// schedule the first step?
}
Wait, but stepTimer needs to be initialized so that the first step is taken immediately.
Alternatively, set stepTimer = performance.now() - stepDuration / 2, but perhaps better to compute in animate function.
Alternatively, after setup(), call advanceStep() once?
Hmm, perhaps in the animate function, we can check if setup() is needed first.
Wait, initially, setup() needs to be called once before starting the animation.
So:
setup();
animate();
Wait, but in the animate loop, if isRunning is true, then it will process steps.
But in setup(), isRunning is set to true, so that should trigger the first step.
Wait, but stepTimer is initialized as 0? Or in setup(), stepTimer is set to 0?
Wait in setup():
stepTimer = 0;
stepDuration is 1000, so the first step is done after 1000 ms.
Wait, perhaps better to set stepTimer to now - stepDuration, so that the first step is taken immediately.
Alternatively, in setup():
stepTimer = performance.now() - stepDuration;
But since setup() is called before the first animate().
Hmm, this can be tricky. Maybe better to set stepTimer = performance.now();
Wait, perhaps it's easier to use a flag indicating that the first step should be taken immediately.
Alternatively, to adjust the animate function to handle the first step.
Alternatively, maybe use requestAnimationFrame's timestamp.
Alternatively, let's rework the animate function to use the elapsed time properly.
Let me rework the animate function:
function animate(timestamp) {
if (!isRunning) return;
if (timestamp - stepTimer >= stepDuration) {
stepTimer = timestamp;
advanceStep();
}
draw();
requestAnimationFrame(animate);
}
Then in setup():
stepTimer = -stepDuration; // so that timestamp - stepTimer is immediately >= stepDuration
Thus, the first step is taken at the first animate call.
Now, the advanceStep function:
function advanceStep() {
// Find the next edge to add to the MST.
// To simplify, we'll greedily pick the shortest edge between inTree and out of tree nodes.
// But in reality, this is not the correct MST algorithm (Kruskal or Prim's), but for visualization purposes, maybe just pick the shortest edge.
// However, to keep it simple, perhaps choose any edge between the current tree and outside.
// Alternatively, use Prim's algorithm.
// Let's implement Prim's algorithm step by step:
let minEdge = null;
let minDist = Infinity;
// Find all edges that connect inTree to out of tree nodes.
for (const edge of edges) {
const a = nodes[edge.a];
const b = nodes[edge.b];
if (a.inTree !== b.inTree) {
if (edge.weight < minDist) {
minDist = edge.weight;
minEdge = edge;
}
}
}
if (minEdge) {
// Add this edge: set both nodes to inTree, but actually, one is already inTree.
const aNode = nodes[minEdge.a];
const bNode = nodes[minEdge.b];
// whichever is in the tree, the other is not.
if (aNode.inTree) {
bNode.inTree = true;
} else {
aNode.inTree = true;
}
totalWeight += minEdge.weight;
stepCount++;
} else {
// All nodes are in the tree, stop.
isRunning = false;
}
}
Wait, but this has a problem: when choosing the edge with the minimal weight, but if there are multiple, it's non-deterministic. But for visualization, it's okay.
However, Prim's algorithm requires selecting the minimum weight edge each time to form the MST. So this implementation is correct for Prim's algorithm.
Thus, the advanceStep() function is correct.
Now, putting all together.
Wait, also in the draw function, when drawing edges, we need to check if the edge is between two inTree nodes, or between in and out.
The code for drawing edges:
function draw() {
ctx.clearRect(0, 0, canvas.width, canvas.height);
ctx.strokeStyle = 'lightgray';
ctx.lineWidth = 1;
// Draw all edges
for (const edge of edges) {
const a = nodes[edge.a];
const b = nodes[edge.b];
ctx.beginPath();
ctx.moveTo(a.x, a.y);
ctx.lineTo(b.x, b.y);
// Determine edge color and style
let color, lineWidth, dash;
if (a.inTree && b.inTree) {
color = 'green';
lineWidth = 2;
dash = [];
} else if (a.inTree || b.inTree) {
color = 'orange';
lineWidth = 1;
dash = [5, 5]; // dashed
} else {
color = 'lightgray';
lineWidth = 1;
dash = [];
}
ctx.strokeStyle = color;
ctx.lineWidth = lineWidth;
ctx.setLineDash(dash);
ctx.stroke();
}
ctx.setLineDash([]);
// Draw nodes
for (const node of nodes) {
ctx.beginPath();
ctx.arc(node.x, node.y, 5, 0, 2 * Math.PI);
ctx.fillStyle = node.inTree ? 'green' : 'red';
ctx.fill();
}
// Display info
ctx.fillStyle = 'black';
ctx.font = '16px Arial';
ctx.fillText(`Total Weight: ${totalWeight.toFixed(2)}`, 10, 30);
ctx.fillText(`Step: ${stepCount}`, 10, 50);
}
This should work.
Finally, call setup and start the animation:
setup();
requestAnimationFrame(animate);
Putting it all together in the code.
Testing this in a browser (since it's JavaScript), but here is the code:
```javascript
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
let nodes = [];
let edges = [];
let stepCount = 0;
let totalWeight = 0;
let isRunning = true;
let stepTimer = 0;
const stepDuration = 1000; // milliseconds
function setup() {
const count = 20 + Math.floor(Math.random() * 5); // 20-25 nodes
nodes = [];
const radius = 150;
for (let i = 0; i < count; i++) {
const x = Math.random() * (canvas.width - 10) + 5;
const y = Math.random() * (canvas.height - 10) + 5;
nodes.push({ x, y, inTree: false });
}
// Choose a random starting node
const startNode = Math.floor(Math.random() * nodes.length);
nodes[startNode].inTree = true;
edges = [];
for (let i = 0; i < nodes.length; i++) {
for (let j = i + 1; j < nodes.length; j++) {
const dx = nodes[i].x - nodes[j].x;
const dy = nodes[i].y - nodes[j].y;
const dist = Math.hypot(dx, dy);
if (dist < radius) {
edges.push({ a: i, b: j, weight: dist });
}
}
}
stepCount = 0;
totalWeight = 0;
isRunning = true;
stepTimer = -stepDuration; // Ensure first step runs immediately
}
function draw() {
ctx.clearRect(0, 0, canvas.width, canvas.height);
// Draw edges
for (const edge of edges) {
const a = nodes[edge.a];
const b = nodes[edge.b];
ctx.beginPath();
ctx.moveTo(a.x, a.y);
ctx.lineTo(b.x, b.y);
let color, lineWidth, dash;
if (a.inTree && b.inTree) {
color = 'green';
lineWidth = 2;
dash = [];
} else if (a.inTree || b.inTree) {
color = 'orange';
lineWidth = 1;
dash = [5, 5];
} else {
color = 'lightgray';
lineWidth = 1;
dash = [];
}
ctx.strokeStyle = color;
ctx.lineWidth = lineWidth;
ctx.setLineDash(dash);
ctx.stroke();
}
ctx.setLineDash([]);
// Draw nodes
for (const node of nodes) {
ctx.beginPath();
ctx.arc(node.x, node.y, 5, 0, 2 * Math.PI);
ctx.fillStyle = node.inTree ? 'green' : 'red';
ctx.fill();
}
// Display info
ctx.fillStyle = 'black';
ctx.font = '16px Arial';
ctx.fillText(`Total Weight: ${totalWeight.toFixed(2)}`, 10, 30);
ctx.fillText(`Step: ${stepCount}`, 10, 50);
}
function advanceStep() {
let minEdge = null;
let minDist = Infinity;
// Find the shortest edge connecting inTree and out-of-tree nodes
for (const edge of edges) {
const a = nodes[edge.a];
const b = nodes[edge.b];
if (a.inTree !== b.inTree) {
if (edge.weight < minDist) {
minDist = edge.weight;
minEdge = edge;
}
}
}
if (minEdge) {
const aNode = nodes[minEdge.a];
const bNode = nodes[minEdge.b];
// Toggle the non-inTree node to inTree
if (aNode.inTree) {
bNode.inTree = true;
} else {
aNode.inTree = true;
}
totalWeight += minDist;
stepCount++;
} else {
// All nodes are in the tree, stop
isRunning = false;
}
}
function animate(timestamp) {
if (isRunning && timestamp - stepTimer >= stepDuration) {
stepTimer = timestamp;
advanceStep();
}
draw();
requestAnimationFrame(animate);
}
// Initialize and start
setup();
requestAnimationFrame(animate);
```
This code should create a visualization of Prim's algorithm building a minimum spanning tree. Nodes start as red (not in the tree) and turn green as they're added. Edges between inTree nodes are green, edges connecting to the tree are orange dashes, and unconnected edges are light gray. Each step adds the shortest edge to the tree, pausing for a second between steps.