Някъв мазаляк станА, казах му да маха линията, след като я видя, да не се претрупва. Не разбра кво искам и ме отсвири.
Можеш ли да изведеш анимация в реално време, как се случва текущото изчисление?
Да, можем да извеждаме анимация, която визуализира текущото изчисление на минималното покриващо дърво, като рисуваме графа в реално време по време на изчисленията в приложението.
За да постигнем това, можем да добавим допълнителен код, който да изтрива и рисува обекти на графа в замислен анимационен цикъл, докато алгоритъмът на Крускал изчислява МПД. Всяко изчисление на ребро в МПД може да бъде изобразено като оцветяване на текущото ребро в друг цвят, след което да се изчака няколко милисекунди, преди да продължим изчислението към следващото ребро.
Ето една възможна реализация на програмата, която да визуализира МПД в реално време по време на изчисленията по алгоритъма на Крускал в приложението:
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import javax.swing.JFrame;
import javax.swing.JPanel;
public class AnimatedMinSpanningTree extends JPanel {
private static final int POINT_COUNT = 100;
private static final int WIDTH = 800;
private static final int HEIGHT = 600;
private static final int ANIMATION_DELAY_MS = 20;
private static final Color POINT_COLOR = Color.RED;
private static final Color EDGE_COLOR = Color.BLACK;
private static final Color ANIMATED_EDGE_COLOR = Color.BLUE;
private static final Random RAND = new Random();
private List<Point> points = new ArrayList<>();
private List<Edge> edges = new ArrayList<>();
private boolean isAnimating = false;
private int animatedEdgeIndex = -1;
public AnimatedMinSpanningTree() {
generatePoints();
}
private void generatePoints() {
for (int i = 0; i < POINT_COUNT; i++) {
points.add(new Point(RAND.nextInt(WIDTH), RAND.nextInt(HEIGHT)));
}
}
private void buildMinSpanningTree() throws InterruptedException {
List<Edge> sortedEdges = new ArrayList<>();
for (int i = 0; i < points.size(); i++) {
for (int j = i + 1; j < points.size(); j++) {
sortedEdges.add(new Edge(points.get(i), points.get(j)));
}
}
Collections.shuffle(sortedEdges);
List<Integer> roots = new ArrayList<>();
for (int i = 0; i < points.size(); i++) {
roots.add(i);
}
for (int i = 0; i < sortedEdges.size(); i++) {
Edge edge = sortedEdges.get(i);
int root1 = findRoot(roots, points.indexOf(edge.src));
int root2 = findRoot(roots, points.indexOf(edge.dest));
if (root1 != root2) {
roots.set(root1, root2);
edges.add(edge);
animateEdge(i);
}
}
}
private int findRoot(List<Integer> roots, int i) {
if (roots.get(i) != i) {
roots.set(i, findRoot(roots, roots.get(i)));
}
return roots.get(i);
}
private void animateEdge(int index) throws InterruptedException {
isAnimating = true;
animatedEdgeIndex = index;
repaint();
Thread.sleep(ANIMATION_DELAY_MS);
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
g.setColor(POINT_COLOR);
for (Point p : points) {
g.fillOval(p.x - 3, p.y - 3, 6, 6);
}
g.setColor(EDGE_COLOR);
for (int i = 0; i < edges.size(); i++) {
Edge edge = edges.get(i);
if (isAnimating && i == animatedEdgeIndex) {
g.setColor(ANIMATED_EDGE_COLOR);
}
g.drawLine(edge.src.x, edge.src.y, edge.dest.x, edge.dest.y);
g.setColor(EDGE_COLOR);
}
if (isAnimating) {
isAnimating = false;
animatedEdgeIndex = -1;
}
}
public static void main(String[] args) throws InterruptedException {
JFrame frame = new JFrame("Animated Minimum Spanning Tree");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setSize(WIDTH, HEIGHT);
AnimatedMinSpanningTree panel = new AnimatedMinSpanningTree();
frame.add(panel);
frame.setVisible(true);
panel.buildMinSpanningTree();
}
private static class Edge {
private Point src, dest;
private Edge(Point src, Point dest) {
this.src = src;
this.dest = dest;
}
}
}
Кода добавя нови полета, за да позволи анимация на изчислението на алгоритъма на Крускал. Полетата са isAnimating, което показва дали програмата в момента извършва анимация, animatedEdgeIndex, което показва индекса на текущото ребро, което се анимира, и ANIMATION_DELAY_MS, което указва колко време да се изчака между кадрите на анимацията.Добавен е нов метод animateEdge, който се извиква вместо edges.add, когато се добавя ново ребро в МПД