Comment implémenter l'algorithme de point de coupure graphique à l'aide de Java

Comment utiliser Java pour implémenter l'algorithme de point de coupure des graphiques nécessite des exemples de code spécifiques

Les graphiques sont l'un des concepts importants des mathématiques discrètes grâce à la représentation de graphiques, de relations et de connexions qui apparaissent dans diverses situations réelles. les problèmes peuvent être décrits. Dans les algorithmes liés aux graphes, trouver les points de coupure d’un graphique est un problème difficile. Le point de coupe d'un graphe est également appelé point commun ou sommet coupé. Cela signifie que dans un graphe connecté non orienté, si un sommet et toutes les arêtes associées au sommet sont supprimés, le graphe d'origine n'est plus connecté. est appelé un point de coupure.

Cet article expliquera comment utiliser le langage de programmation Java pour implémenter l'algorithme de point de coupure graphique et fournira des exemples de code spécifiques. Tout d'abord, nous devons définir la structure de données d'un graphique. Voici un exemple simple de classe de graphique :

import java.util.*;

class Graph {
    private int V; // 顶点的数量
    private LinkedList<Integer> adj[]; // 邻接表形式的图

    // 构造函数，初始化图
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    // 添加边到图中
    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    // 递归函数，实现割点算法
    void cutVertexUtil(int u, boolean visited[], int disc[], int low[], int parent[], boolean ap[]) {
        int children = 0;
        visited[u] = true;
        disc[u] = low[u] = ++time;

        Iterator<Integer> i = adj[u].iterator();
        while (i.hasNext()) {
            int v = i.next();
            if (!visited[v]) {
                children++;
                parent[v] = u;
                cutVertexUtil(v, visited, disc, low, parent, ap);
                low[u]  = Math.min(low[u], low[v]);

                if (parent[u] == -1 && children > 1)
                    ap[u] = true;

                if (parent[u] != -1 && low[v] >= disc[u])
                    ap[u] = true;
            }
            else if (v != parent[u])
                low[u]  = Math.min(low[u], disc[v]);
        }
    }

    // 割点算法的主函数
    void cutVertices() {
        boolean visited[] = new boolean[V];
        int disc[] = new int[V];
        int low[] = new int[V];
        int parent[] = new int[V];
        boolean ap[] = new boolean[V]; // 记录割点

        for (int i = 0; i < V; i++) {
            parent[i] = -1;
            visited[i] = false;
            ap[i] = false;
        }

        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                cutVertexUtil(i, visited, disc, low, parent, ap);

        System.out.println("割点：");
        for (int i = 0; i < V; i++)
            if (ap[i] == true)
                System.out.print(i+" ");
        System.out.println();
    }

    public static void main(String args[]) {
        Graph g1 = new Graph(5);
        g1.addEdge(1, 0);
        g1.addEdge(0, 2);
        g1.addEdge(2, 1);
        g1.addEdge(0, 3);
        g1.addEdge(3, 4);
        System.out.println("以下是图g1中的割点：");
        g1.cutVertices();

        Graph g2 = new Graph(4);
        g2.addEdge(0, 1);
        g2.addEdge(1, 2);
        g2.addEdge(2, 3);
        System.out.println("以下是图g2中的割点：");
        g2.cutVertices();

        Graph g3 = new Graph(7);
        g3.addEdge(0, 1);
        g3.addEdge(1, 2);
        g3.addEdge(2, 0);
        g3.addEdge(1, 3);
        g3.addEdge(1, 4);
        g3.addEdge(1, 6);
        g3.addEdge(3, 5);
        g3.addEdge(4, 5);
        System.out.println("以下是图g3中的割点：");
        g3.cutVertices();
    }
}

Dans cet exemple de code, nous créons une classe Graph pour représenter le graphique, en utilisant la forme d'une liste de contiguïté pour stocker les arêtes. du graphique. Dans la mise en œuvre de l'algorithme de point de coupure, nous utilisons la méthode de parcours de recherche en profondeur d'abord et utilisons certains tableaux auxiliaires pour enregistrer l'état d'accès, l'heure de découverte, le nœud ancêtre visité le plus tôt et marquer le point de coupure. En appelant la fonction cutVertices(), vous pouvez trouver les points de coupure dans le graphique et afficher l'index des points de coupure. cutVertices()函数，可以找到图中的割点，并输出割点的索引。

代码示例中的main

La fonction main dans l'exemple de code montre comment utiliser cet algorithme de point de coupure pour trouver des points de coupure dans un graphique donné. Vous pouvez modifier la taille du graphique et les relations de connexion des arêtes selon vos besoins, puis exécuter le code pour afficher la sortie.

Pour résumer, cet article présente comment utiliser Java pour implémenter l'algorithme de point de coupure des graphiques et fournit des exemples de code spécifiques. J'espère que cet article pourra aider les lecteurs à comprendre l'algorithme du point de coupure du graphique et à effectuer les ajustements et les utilisations correspondants dans des applications pratiques. 🎜

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!