案例研究：连通圆问题

连接圆的问题是判断二维平面中的所有圆是否连接。这个问题可以通过深度优先遍历来解决。 dfs算法有很多应用。本节应用dfs算法解决连接圆问题。

在连接圆的问题上，您可以确定二维平面中的所有圆是否连接。如果所有圆都连接起来，将其绘制成实心圆，如下图所示（a）所示。否则，它们将不会被填充，如下图所示(b)所示。

我们将编写一个程序，让用户在当前未被圆圈覆盖的空白区域单击鼠标来创建一个圆圈。添加圆圈时，如果圆圈已连接，将重新绘制填充，否则将不填充。

我们将创建一个模拟问题的图表。每个圆都是图中的顶点。如果两个圆重叠，它们是连接的。我们在图中应用dfs，如果在深度优先搜索中找到所有顶点，图是连接的。

在下面的代码中给出程序。

import javafx.application.Application;
import javafx.geometry.Point2D;
import javafx.scene.Node;
import javafx.scene.Scene;
import javafx.scene.layout.Pane;
import javafx.scene.paint.Color;
import javafx.scene.shape.Circle;
import javafx.stage.Stage;

public class ConnectedCircles extends Application {
    @Override // Override the start method in the Application class
    public void start(Stage primaryStage) {
        // Create a scene and place it in the stage
        Scene scene = new Scene(new CirclePane(), 450, 350);
        primaryStage.setTitle("ConnectedCircles"); // Set the stage title
        primaryStage.setScene(scene); // Place the scene in the stage
        primaryStage.show(); // Display the stage
    }

    public static void main(String[] args) {
        Application.launch(args);
    }

    /** Pane for displaying circles */
    class CirclePane extends Pane {
        public CirclePane() {
            this.setOnMouseClicked(e -> {
                if (!isInsideACircle(new Point2D(e.getX(), e.getY()))) {
                    // Add a new circle
                    getChildren().add(new Circle(e.getX(), e.getY(), 20));
                    colorIfConnected();
                }
            });
        }

        /** Returns true if the point is inside an existing circle */
        private boolean isInsideACircle(Point2D p) {
            for (Node circle: this.getChildren())
                if (circle.contains(p))
                    return true;

            return false;
        }

        /** Color all circles if they are connected */
        private void colorIfConnected() {
            if (getChildren().size() == 0)
                return; // No circles in the pane

            // Build the edges
            java.util.List<abstractgraph.edge> edges = new java.util.ArrayList();
            for (int i = 0; i  graph = new UnweightedGraph((java.util.List<node>)getChildren(), edges);
            AbstractGraph<node>.Tree tree = graph.dfs(0); // a DFS tree
            boolean isAllCirclesConnected = getChildren().size() == tree.getNumberOfVerticesFound();

            for (Node circle: getChildren()) {
                if (isAllCirclesConnected) { // All circles are connected
                    ((Circle)circle).setFill(Color.RED);
                }
                else {
                    ((Circle)circle).setStroke(Color.BLACK);
                    ((Circle)circle).setFill(Color.WHITE);
                }
            }
        }
    }

    public static boolean overlaps(Circle circle1， Circle circle2) {
        return new Point2D(circle1.getCenterX(), circle1.getCenterY()).distance(circle2.getCenterX(), circle2.getCenterY()) 



<p>javafx <strong>circle</strong> 类别包含数据字段 <strong>x</strong>、<strong>y</strong> 和 <strong>radius</strong>，它们指定圆的中心位置和半径。它还定义了<strong>contains</strong>测试一个点是否在圆中。它还定义了<strong>contains</strong>测试一个点是否在圆中。 <strong>overlaps</strong> 方法（第 76-80 检查两个圆是否重叠。</p>

<p>用户在任何现有圆圈外单击鼠标时，都会创建一个以鼠标点为中心的新圆圈，并将其添加到窗格中(第) 26 行）。</p>

<p>程序构建了一个图，以检测圆是否连接。 46-59 行）。圆圈是图片的顶点。边缘在第 49-55 行中构建。如果两个圆顶重叠，它们是相连的(第一 51 行）。该图的 dfs 生成一棵树(第 60 行）。树的 <strong>getnumberofverticesfound()</strong> 回到搜索到的顶点数。如果等于圆的数量，所有的圆都是相连的(第一 61-62 行）。</p>


          

            
        </node></node></abstractgraph.edge>

以上是案例研究：连接圆问题的详细内容，请关注图灵教育的其他相关文章！