Java java지도 시간 Java를 사용하여 그래프의 강력하게 연결된 구성 요소 알고리즘을 구현하는 방법

Java를 사용하여 그래프의 강력하게 연결된 구성 요소 알고리즘을 구현하는 방법

Sep 21, 2023 am 11:09 AM
java 그림 강하게 연결된 구성 요소 알고리즘

Java를 사용하여 그래프의 강력하게 연결된 구성 요소 알고리즘을 구현하는 방법

Java를 사용하여 그래프의 강력하게 연결된 구성 요소 알고리즘을 구현하는 방법

소개:
그래프는 컴퓨터 과학에서 일반적으로 사용되는 데이터 구조이며 많은 실제 문제를 해결하는 데 도움이 될 수 있습니다. 그래프에서 연결된 구성 요소는 상호 도달 가능한 경로가 있는 그래프의 정점 집합을 나타냅니다. 강하게 연결된 구성요소는 유향 그래프의 두 정점 사이에 양방향 경로가 있음을 의미합니다. 이 기사에서는 독자가 그래프의 연결성을 더 잘 이해할 수 있도록 Java를 사용하여 그래프의 강력하게 연결된 구성 요소 알고리즘을 구현하는 방법을 소개합니다.

1. 그래프 표현
Java에서는 인접 행렬이나 인접 목록을 사용하여 그래프를 표현할 수 있습니다. 인접 행렬(Adjacency Matrix)은 두 꼭지점 사이에 모서리가 존재하는지 여부를 행렬 요소로 나타내는 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 메서드를 사용하여 강하게 연결된 각 구성 요소를 인쇄합니다. Graph类来表示图。addEdge方法用于向图中添加边,DFSUtil方法使用递归的方式进行DFS遍历,getTranspose方法用于计算图的转置,printSCCs方法用于打印出各个强连通分量。

Main类中,我们创建一个具有5个顶点的图,并向图中添加边。然后,调用printSCCs

Main 클래스에서는 5개의 꼭짓점을 가진 그래프를 만들고 그래프에 간선을 추가합니다. 그런 다음 printSCCs 메서드를 호출하여 그래프의 강하게 연결된 구성 요소를 인쇄합니다.


결론:

이 기사에서는 Java를 사용하여 그래프의 강력 연결 구성 요소 알고리즘을 구현하는 방법을 소개하고 구체적인 코드 예제를 제공합니다. 이 알고리즘을 이해하고 익히면 독자는 그래프 연결 문제를 더 잘 처리하고 해결할 수 있습니다. 이 글이 독자들에게 도움이 되기를 바랍니다! 🎜

위 내용은 Java를 사용하여 그래프의 강력하게 연결된 구성 요소 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 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 Hentai를 무료로 생성하십시오.

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

자바의 제곱근 자바의 제곱근 Aug 30, 2024 pm 04:26 PM

자바의 제곱근 안내 여기서는 예제와 코드 구현을 통해 Java에서 Square Root가 어떻게 작동하는지 설명합니다.

자바의 완전수 자바의 완전수 Aug 30, 2024 pm 04:28 PM

Java의 완전수 가이드. 여기서는 정의, Java에서 완전 숫자를 확인하는 방법, 코드 구현 예제에 대해 논의합니다.

Java의 난수 생성기 Java의 난수 생성기 Aug 30, 2024 pm 04:27 PM

Java의 난수 생성기 안내. 여기서는 예제를 통해 Java의 함수와 예제를 통해 두 가지 다른 생성기에 대해 설명합니다.

자바의 웨카 자바의 웨카 Aug 30, 2024 pm 04:28 PM

Java의 Weka 가이드. 여기에서는 소개, weka java 사용 방법, 플랫폼 유형 및 장점을 예제와 함께 설명합니다.

자바의 암스트롱 번호 자바의 암스트롱 번호 Aug 30, 2024 pm 04:26 PM

자바의 암스트롱 번호 안내 여기에서는 일부 코드와 함께 Java의 Armstrong 번호에 대한 소개를 논의합니다.

Java의 스미스 번호 Java의 스미스 번호 Aug 30, 2024 pm 04:28 PM

Java의 Smith Number 가이드. 여기서는 정의, 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은 스트림 API를 소개하여 데이터 컬렉션을 처리하는 강력하고 표현적인 방법을 제공합니다. 그러나 스트림을 사용할 때 일반적인 질문은 다음과 같은 것입니다. 기존 루프는 조기 중단 또는 반환을 허용하지만 스트림의 Foreach 메소드는이 방법을 직접 지원하지 않습니다. 이 기사는 이유를 설명하고 스트림 처리 시스템에서 조기 종료를 구현하기위한 대체 방법을 탐색합니다. 추가 읽기 : Java Stream API 개선 스트림 foreach를 이해하십시오 Foreach 메소드는 스트림의 각 요소에서 하나의 작업을 수행하는 터미널 작동입니다. 디자인 의도입니다

See all articles