[바미] 자료구조 - 그래프(Graph)

그래프(Graph)?

정점과 간선으로 이뤄진 자료구조 입니다.

 

❓ 정점 
정점은 그래프에서 데이터를 저장하는 기본 단위입니다. 노드(Node)라고 불리기도 하고, 다양한 데이터를 저장할 수 있습니다.

 

❓ 간선
정점을 연결하는 선으로 링크(link) 또는 브랜치(branch)라고도 합니다.

 

그리고 간선에는 방향이 존재하는 그래프와 방향이 없는 그래프가 존재합니다. 

아래 그림처럼 방향이 존재하는 그래프는 방향그래프(directed graph), 방향이 존재하지 않는 그래프를 무방향 그래프(undirected graph)라고 부릅니다.

---

추가적으로 그래프 탐색 방법 중 가장 기본적인 두 가지 중 깊이 우선 탐색(DFS, Depth-First Search)과 너비 우선 탐색(BFS, Breadth-First Search)이 있습니다. 이 두 가지 방법은 그래프의 모든 정점을 방문하거나 특정 조건을 만족하는 정점을 찾는 데 사용됩니다.

깊이 우선 탐색(DFS, Depth-First Search)

DFS는 그래프의 한 정점에서 시작하여 가능한 멀리까지 탐색한 다음, 다시 돌아와 다른 경로를 탐색하는 방식입니다. 

이 때 DFS는 스택(Stack) 자료 구조를 사용하거나 재귀(Recursion)를 통해 구현합니다.

출처: https://developer-mac.tistory.com/64

깊이 우선 탐색 동작 순서

1. 시작 정점을 방문하고, 이를 방문했다고 표시합니다.
2. 인접한 정점들 중 아직 방문하지 않은 정점으로 이동합니다.
3. 더 이상 방문할 인접 정점이 없으면, 이전 정점으로 되돌아갑니다.
4. 모든 정점을 방문할 때까지 1-3을 반복합니다.

---

너비 우선 탐색(BFS, Breadth-First Search)

BFS는 그래프의 한 정점에서 시작하여 인접한 정점들을 먼저 모두 탐색한 후, 다음 레벨의 정점들을 탐색하는 방식입니다. 

이 때 BFS는 주로 큐(Queue)를 사용하여 구현합니다.

너비 우선 탐색 동작 순서

 

1. 시작 정점을 큐에 넣고, 이를 방문했다고 표시합니다.
2. 큐에서 정점을 꺼내, 해당 정점에 인접한 정점들을 모두 큐에 넣고 방문했다고 표시합니다.
3. 큐가 빌 때까지 2를 반복합니다.

 

출처: https://developer-mac.tistory.com/64

코드(Java)

위 DFS, BFS탐색을 사용한 예제를 만들어 보았습니다.

import java.util.LinkedList;

class Graph {
    private int numVertices;
    private LinkedList<Integer>[] adjacencyList;

    // 그래프 생성자
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjacencyList = new LinkedList[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    // 간선 추가 (무방향 그래프)
    public void addEdge(int source, int destination) {
        adjacencyList[source].add(destination);
        adjacencyList[destination].add(source);
    }

    // 그래프 출력
    public void printGraph() {
        for (int i = 0; i < numVertices; i++) {
            System.out.print("Vertex " + i + ":");
            for (Integer neighbor : adjacencyList[i]) {
                System.out.print(" -> " + neighbor);
            }
            System.out.println();
        }
    }

    // DFS 탐색
    public void dfs(int startVertex) {
        boolean[] visited = new boolean[numVertices];
        dfsUtil(startVertex, visited);
    }

    // DFS 유틸리티 함수
    private void dfsUtil(int vertex, boolean[] visited) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        for (int neighbor : adjacencyList[vertex]) {
            if (!visited[neighbor]) {
                dfsUtil(neighbor, visited);
            }
        }
    }

    // BFS 탐색
    public void bfs(int startVertex) {
        boolean[] visited = new boolean[numVertices];
        LinkedList<Integer> queue = new LinkedList<>();

        visited[startVertex] = true;
        queue.add(startVertex);

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");

            for (int neighbor : adjacencyList[vertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(5);

        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);

        graph.printGraph();

        System.out.println("DFS traversal starting from vertex 0:");
        graph.dfs(0);

        System.out.println("\nBFS traversal starting from vertex 0:");
        graph.bfs(0);
    }
}

코드 설명

Graph클래스와 main 메소드로 나뉘어져 있는 구조입니다.

import java.util.LinkedList;

그래프의 인접 리스트를 구현하는 데 사용할 LinkedList 클래스를 임포트하는 부분입니다.

 

Graph클래스

private int numVertices;
private LinkedList<Integer>[] adjacencyList;

 

numVertices변수는 그래프의 정점(노드) 수를 저장하는 변수이고, adjacencyList변수는 각 정점의 인접 정점들을 저장하는 리스트 배열을 의미합니다.

생성자

    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjacencyList = new LinkedList[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

 

그래프의 생성자 부분입니다. 정점의 수를 받아 인접 리스트 배열을 초기화 해주는데 각 정점마다 LinkedList를 생성하여 초기화하는 형태입니다.

간선 추가

public void addEdge(int source, int destination) {
    adjacencyList[source].add(destination);
    adjacencyList[destination].add(source);
}

간선을 추가하는 메서드입니다. 현재 예제는 무방향 그래프이기 때문에 양쪽 정점의 인접 리스트에 서로를 추가하도록 했습니다.

 

그래프 출력

public void printGraph() {
    for (int i = 0; i < numVertices; i++) {
        System.out.print("Vertex " + i + ":");
        for (Integer neighbor : adjacencyList[i]) {
            System.out.print(" -> " + neighbor);
        }
        System.out.println();
    }
}

그래프를 출력하는 메서드입니다. 각 정점과 그 정점에 인접한 모든 정점들을 출력합니다.

DFS 탐색

public void dfs(int startVertex) {
    boolean[] visited = new boolean[numVertices];
    dfsUtil(startVertex, visited);
}

private void dfsUtil(int vertex, boolean[] visited) {
    visited[vertex] = true;
    System.out.print(vertex + " ");

    for (int neighbor : adjacencyList[vertex]) {
        if (!visited[neighbor]) {
            dfsUtil(neighbor, visited);
        }
    }
}

깊이 우선 탐색을 시작하는 메서드입니다. visited 배열을 사용하여 탐색한 정점을 추적하는 형태입니다.

dfsUtil 메서드를 통해 재귀적으로 깊이 우선 탐색을 수행하며 현재 정점을 탐색하고 출력한 후, 인접한 모든 정점을 탐색하죠.

BFS 탐색

public void bfs(int startVertex) {
    boolean[] visited = new boolean[numVertices];
    LinkedList<Integer> queue = new LinkedList<>();

    visited[startVertex] = true;
    queue.add(startVertex);

    while (!queue.isEmpty()) {
        int vertex = queue.poll();
        System.out.print(vertex + " ");

        for (int neighbor : adjacencyList[vertex]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.add(neighbor);
            }
        }
    }
}

너비 우선 탐색을 시작하는 메서드입니다. visited 배열을 사용하여 탐색한 정점을 추적하고, queue를 사용하여 탐색할 정점을 관리하는데 큐에서 정점을 꺼내 탐색하고, 그 정점에 인접한 모든 정점을 큐에 추가하는 형태입니다.

---

main 메서드

Graph graph = new Graph(5);

먼저 5개의 정점을 가지는 새로운 그래프를 생성합니다.

 

graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 3);
graph.addEdge(3, 4);

그 후 그래프에 간선을 추가하는 부분입니다.

여기에서 graph.addEdge(0, 1)라는 의미는 정점 0과 정점 1을 연결하는 간선을 추가한다는 의미죠.

 

graph.printGraph();

그래프를 출력해주는 부분입니다.

 

System.out.println("DFS traversal starting from vertex 0:");
graph.dfs(0);

정점 0에서 시작하여 DFS 탐색을 실행하고 결과를 출력해주는 부분입니다.

 

System.out.println("\nBFS traversal starting from vertex 0:");
graph.bfs(0);

정점 0에서 시작하여 BFS 탐색을 실행하고 결과를 출력해주는 부분입니다.

---

결과

Vertex 0: -> 1 -> 4
Vertex 1: -> 0 -> 2 -> 3 -> 4
Vertex 2: -> 1 -> 3
Vertex 3: -> 1 -> 2 -> 4
Vertex 4: -> 0 -> 1 -> 3
DFS traversal starting from vertex 0:
0 1 2 3 4 
BFS traversal starting from vertex 0:
0 1 4 2 3