Java를 사용하여 그래프 순회 알고리즘을 구현하는 방법

Java를 사용하여 그래프 순회 알고리즘을 구현하는 방법

그래프는 이산 수학에서 중요한 데이터 구조이며 사물 간의 관계를 설명하는 데 자주 사용됩니다. 그래프 순회 알고리즘은 특정 노드부터 시작하여 특정 규칙에 따라 그래프의 모든 노드를 순차적으로 방문하는 프로세스를 말합니다. 일반적으로 사용되는 그래프 순회 알고리즘에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다. 이 기사에서는 Java 언어를 사용하여 두 그래프 순회 알고리즘을 구현하는 방법을 소개하고 특정 샘플 코드를 제공합니다.

1. 깊이 우선 검색(DFS)

깊이 우선 검색은 방문하지 않은 인접 노드가 없을 때까지 시작 노드에서 시작하여 인접 노드를 재귀적으로 방문한 다음 이전 노드로 역추적하는 선주문 탐색 알고리즘입니다. 전체 그래프를 탐색할 때까지 방문하지 않은 인접 노드를 계속 방문합니다.

다음은 깊이 우선 탐색을 통해 그래프를 순회하는 예제 코드입니다.

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);
    }
 
    void DFSUtil(int v, Boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");
 
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }
 
    void DFS(int v) {
        Boolean visited[] = new Boolean[V];
        Arrays.fill(visited, false);
 
        DFSUtil(v, visited);
    }
 
    public static void main(String args[]) {
        Graph g = new Graph(4);
 
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
 
        System.out.println("从顶点2开始的遍历结果：");
        g.DFS(2);
    }
}

출력 결과:

从顶点2开始的遍历结果：
2 0 1 3

2. 너비 우선 탐색(BFS)

폭 우선 탐색은 다음에서 시작하는 수평 순회 알고리즘입니다. 시작 노드는 전체 그래프를 탐색할 때까지 순서대로 노드를 하나씩 방문합니다. 대기열을 사용하여 한 번에 대기열에서 하나의 노드를 가져온 다음 방문하지 않은 인접 노드를 대기열에 추가하는 너비 우선 검색을 구현합니다.

다음은 너비 우선 탐색을 통해 그래프를 순회하는 샘플 코드입니다.

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);
    }
 
    void BFS(int v) {
        boolean visited[] = new boolean[V];
 
        LinkedList<Integer> queue = new LinkedList<Integer>();
 
        visited[v] = true;
        queue.add(v);
 
        while (queue.size() != 0) {
            v = queue.poll();
            System.out.print(v + " ");
 
            Iterator<Integer> i = adj[v].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
 
    public static void main(String args[]) {
        Graph g = new Graph(4);
 
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
 
        System.out.println("从顶点2开始的遍历结果：");
        g.BFS(2);
    }
}

출력 결과:

从顶点2开始的遍历结果：
2 0 3 1

위 샘플 코드에서는 인접 목록을 사용하여 그래프의 구조를 나타내고 다음을 추가하여 그래프를 구성합니다. 가장자리. 그런 다음 각각 DFS 및 BFS 메서드를 호출하여 그래프를 탐색합니다. 출력 결과는 순회 알고리즘으로 얻은 노드 시퀀스입니다.

요약:

이 기사의 소개와 샘플 코드를 통해 Java 언어를 사용하여 깊이 우선 검색 및 너비 우선 검색을 포함한 그래프 순회 알고리즘을 구현하는 방법을 배울 수 있습니다. 이 두 가지 탐색 알고리즘은 웹 크롤러, 미로 해결 및 기타 분야에서 실제로 널리 사용됩니다. 그래프 순회 알고리즘을 마스터하면 관련 문제를 빠르고 효과적으로 해결할 수 있습니다.

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