ホームページ Java &#&チュートリアル Java を使用してグラフの強接続コンポーネント アルゴリズムを実装する方法

Java を使用してグラフの強接続コンポーネント アルゴリズムを実装する方法

Sep 21, 2023 am 11:09 AM
java 写真 強連結成分アルゴリズム

Java を使用してグラフの強接続コンポーネント アルゴリズムを実装する方法

Java を使用してグラフの強接続コンポーネント アルゴリズムを実装する方法

はじめに:
グラフは、コンピューター サイエンスで一般的に使用されるデータ構造です。私たちは多くの実際的な問題を解決します。グラフにおいて、接続コンポーネントとは、相互に到達可能なパスを持つグラフ内の頂点のセットを指します。強く接続されたコンポーネントとは、有向グラフ内の任意の 2 つの頂点間に双方向のパスが存在することを意味します。この記事では、読者がグラフの接続性をよりよく理解できるように、Java を使用してグラフの強接続コンポーネント アルゴリズムを実装する方法を紹介します。

1. グラフの表現方法
Java では、隣接行列または隣接リストを使用してグラフを表現できます。隣接行列は、行列要素が 2 つの頂点間にエッジが存在するかどうかを表す 2 次元配列です。隣接リストは配列を使用して、グラフ内の各頂点に対応するエッジ セットを格納します。この記事では、グラフを表すために隣接リストを使用することを選択します。

2. 強連結コンポーネント アルゴリズムの原理
強連結コンポーネント アルゴリズムは、深さ優先検索 (DFS) を使用してグラフを横断し、強連結プロパティを持つ一連の頂点を見つけます。アルゴリズムの基本原理は次のとおりです。

  1. まず、DFS を使用してグラフ内の各頂点をトラバースし、訪問した頂点をマークします。
  2. 次に、グラフの転置を計算して (つまり、有向エッジの方向を逆にして)、転置されたグラフを取得します。
  3. 次に、転置されたグラフで DFS トラバーサルを実行し、DFS 終了時間に従って頂点を並べ替えます。
  4. 最後に、元のグラフに対して DFS トラバーサルを実行し、ソートされた頂点の順序に従って、相互に到達可能な頂点を同じ連結成分に分割します。

3. Java コードの実装
次は、Java を使用して強接続コンポーネント アルゴリズムを実装するコード例です:

import java.util.*;

class Graph {
    private int V;
    private List<Integer>[] adj;

    public Graph(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int u, int v) {
        adj[u].add(v);
    }

    public void DFSUtil(int v, boolean[] visited, Stack<Integer> stack) {
        visited[v] = true;
        for (int i : adj[v]) {
            if (!visited[i]) {
                DFSUtil(i, visited, stack);
            }
        }
        stack.push(v);
    }

    public Graph getTranspose() {
        Graph g = new Graph(V);
        for (int v = 0; v < V; v++) {
            for (int i : adj[v]) {
                g.adj[i].add(v);
            }
        }
        return g;
    }

    public void printSCCs() {
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[V];
        for (int i = 0; i < V; i++) {
            visited[i] = false;
        }
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                DFSUtil(i, visited, stack);
            }
        }

        Graph gr = getTranspose();
        for (int i = 0; i < V; i++) {
            visited[i] = false;
        }

        while (!stack.isEmpty()) {
            int v = stack.pop();
            if (!visited[v]) {
                gr.DFSUtil(v, visited, new Stack<>());
                System.out.println();
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph(5);
        g.addEdge(1, 0);
        g.addEdge(0, 2);
        g.addEdge(2, 1);
        g.addEdge(0, 3);
        g.addEdge(3, 4);

        System.out.println("Strongly Connected Components:");
        g.printSCCs();
    }
}
ログイン後にコピー

上記のコードでは、最初に ## を定義します。 # Graph グラフを表すクラス。 addEdge メソッドはグラフにエッジを追加するために使用され、DFSUtil メソッドは再帰を使用して DFS トラバーサルを実行し、getTranspose メソッドは転置を計算するために使用されます。グラフ printSCCs メソッドを使用して、それぞれの強接続コンポーネントを出力します。

Main クラスで、5 つの頂点を持つグラフを作成し、グラフにエッジを追加します。次に、printSCCs メソッドを呼び出して、グラフの強接続コンポーネントを出力します。

結論:

この記事では、Java を使用してグラフの強接続コンポーネント アルゴリズムを実装する方法を紹介し、具体的なコード例を示します。このアルゴリズムを理解して習得することで、読者はグラフの接続性の問題をより適切に処理し、解決できるようになります。この記事が読者のお役に立てば幸いです!

以上がJava を使用してグラフの強接続コンポーネント アルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

Javaの平方根 Javaの平方根 Aug 30, 2024 pm 04:26 PM

Java の平方根のガイド。ここでは、Java で平方根がどのように機能するかを、例とそのコード実装をそれぞれ示して説明します。

Javaの完全数 Javaの完全数 Aug 30, 2024 pm 04:28 PM

Java における完全数のガイド。ここでは、定義、Java で完全数を確認する方法、コード実装の例について説明します。

Java の乱数ジェネレーター Java の乱数ジェネレーター Aug 30, 2024 pm 04:27 PM

Java の乱数ジェネレーターのガイド。ここでは、Java の関数について例を挙げて説明し、2 つの異なるジェネレーターについて例を挙げて説明します。

Javaのアームストロング数 Javaのアームストロング数 Aug 30, 2024 pm 04:26 PM

Java のアームストロング番号に関するガイド。ここでは、Java でのアームストロング数の概要とコードの一部について説明します。

ジャワのウェカ ジャワのウェカ Aug 30, 2024 pm 04:28 PM

Java の Weka へのガイド。ここでは、weka java の概要、使い方、プラットフォームの種類、利点について例を交えて説明します。

Javaのスミス番号 Javaのスミス番号 Aug 30, 2024 pm 04:28 PM

Java のスミス番号のガイド。ここでは定義、Java でスミス番号を確認する方法について説明します。コード実装の例。

Java Springのインタビューの質問 Java Springのインタビューの質問 Aug 30, 2024 pm 04:29 PM

この記事では、Java Spring の面接で最もよく聞かれる質問とその詳細な回答をまとめました。面接を突破できるように。

Java 8 Stream Foreachから休憩または戻ってきますか? Java 8 Stream Foreachから休憩または戻ってきますか? Feb 07, 2025 pm 12:09 PM

Java 8は、Stream APIを導入し、データ収集を処理する強力で表現力のある方法を提供します。ただし、ストリームを使用する際の一般的な質問は次のとおりです。 従来のループにより、早期の中断やリターンが可能になりますが、StreamのForeachメソッドはこの方法を直接サポートしていません。この記事では、理由を説明し、ストリーム処理システムに早期終了を実装するための代替方法を調査します。 さらに読み取り:JavaストリームAPIの改善 ストリームを理解してください Foreachメソッドは、ストリーム内の各要素で1つの操作を実行する端末操作です。その設計意図はです

See all articles