[Java DataStructure] Graph

Graph란?

• 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다.
• Java의 Collections를 사용하여 프로그래밍 방식으로 그래프를 나타낼 수 있다.
• 그래프를 생성하는 가장 일반적인 방법은 인접 행렬 또는 인접 목록과 같은 그래프 표현 중 하나를 사용하는 것

 

구조 및 용어

• 정점(vertex) : 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
• 간선 (edge): 정점 간의 관계 (정점을 이어주는 선)
• 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
• 가중치 그래프 (weighted Graph): 연결의 강도가 얼마나 되는지 적혀져 있는 그래프
• 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프
• 무(방)향 그래프 (undirected graph): 방향이 없이 연결되어 있는 그래프
• 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입하고 진출하는 간선이 몇 개인지를 나타낸다.
• 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있는 정점들
• 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우. 다른 정점을 거치지 않는다.
• 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현

 

 

 

무방향 그래프

유방향 그래프

 

인접 행렬

• 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다.
• 만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시
• 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용

 

 

 

 

인접 리스트

• 인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현
• 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.

 

자바 코드로 그래프 구현

public class Solution { 
    private int[][] graph;
    // setGraph(size): 그래프에 size만큼의 버텍스를 추가해야 합니다.
    public void setGraph(int size) {
        graph = new int[size][size];

        for(int i = 0; i < size; i++) {
            for(int j = 0; j < size; j++) {
                graph[i][j] = 0;
            }
        }
    }
    // getGraph(): 인접 행렬 정보가 담긴 배열을 반환합니다.
    public int[][] getGraph() {
        return graph;
    }
    // addEdge(from, to): fromVertex와 toVertex 사이의 간선을 추가합니다.
    public void addEdge(int from, int to) {
        if(from >= graph.length || to >= graph.length) return;
        graph[from][to] = 1;
    }
    // hasEdge(from, to): fromVertex와 toVertex 사이의 간선이 존재하는지 여부를 Boolean으로 반환해야 합니다.
    public boolean hasEdge(int from, int to) {
        if(from >= graph.length || to >= graph.length) return false;
        else if(graph[from][to] == 1) return true;
        else return false;
    }
    // removeEdge(from, to): fromVertex와 toVertex 사이의 간선을 삭제해야 합니다.
    public void removeEdge(int from, int to) {
        if(from >= graph.length || to >= graph.length) return;
        graph[from][to] = 0;
    }
}

---

BFS / DFS

• 그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적이다.
• 그래프의 데이터는 배열처럼 정렬되어 있지 않으므로, 원하는 자료를 찾으려면 하나씩 모두 방문하여 찾아야 한다.
• 그래프의 모든 정점 탐색 방법에는 대표적인 두 가지 방법, DFS와 BFS가 있다.

 

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

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
• 어떤 노드를 방문했었는지 여부를 반드시 검사 해야하므로, 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용

 

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

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
• 모든 노드를 방문 하고자 하는 경우에 사용한다.
• 순환 호출이나 명시적인 스택을 사용한다.