[자료구조] Graph

개인적으로 나는 그래프가 어렵다. 자료구조를 배운 이래, 가장 진입하기 힘들었던 자료구조다. 

물론 아직도 잘 모른다.

더욱이 이를 활용한 문제 풀이는 아직 먼 산이다...

그러므로 그래프에 대해 공부해본다.

자바로 한다.

---

그래프는 정점을 간선으로 연결한 것 그 이상도 이하도 아니다.

가장 단순한 모델은 무방향 그래프.

그래프의 정의는 이렇다.

 

정의 | 그래프는 정점의 집합과 그 집합의 정점 쌍을 연결하는 간선의 모음이다.

 

 

그래서 어디서 이용할까?

지도, 컴퓨터 네트워크, 소셜 네트워크 등등...

어떤 항목들을 연결하는 것이 핵심이다. 

연결은 어떤 관계를 의미한다.

즉, 특정 항목들의 연결 상태, 경로 추적 등등에서 이용된다.

용어

정점, V | 쉽게 생각하면 꼭짓점이다.

간선, E | 쉽게 생각하면 선분이다.

(삼각형은 정점 세 개와 선분 세 개로 이루어진다.)

인접한다 | 두 정점이 간선으로 연결되어 있으면 인접한다고 한다.

차수 | 정점에 연결된 간선의 갯수를 그 정점의 차수 라고 한다.

경로 | 간선으로 연결된 정점의 나열.

단순 경로 | 반복되는 정점이 없는 경로.

순환 | 출발 정점과 도착 정점이 같은 간선이 하나라도 존재하는 경로.

단순 순환 | 반복되는 간선이나 정점이 없는 순환 경로.

연결 | 그래프의 임의의 정점에서 다른 정점으로 가는 경로가 항상 존재한다면 그 그래프는  연결되었다고 한다.

연결 컴포넌트 | 모든 정점이 서로 연결되어 있지 않다면, 서로 연결된 정점들이 모두 모인 서브그래프.

비순환 그래프 | 순환 경로가 없는 그래프.

트리 | 연결된 비순환 그래프.

신장 트리 | 어떤 연결된 그래프에 대해서 그에 속한 모든 정점들을 포함하는 트리.

무방향 그래프 데이터 타입

LinkedList나 Map 등 자바엔 많은 컬렉션들이 주어져 사용하기에 상당히 편할 때가 많다.

하지만 Graph는 없다. 슬프다. 그러므로 만들어본다.

여기선 가장 기초적인 무방향 그래프에 대해 만들어본다.

또한 ArrayList를 사용해볼 것이다.

int V | 정점의 갯수

int E | 간선의 갯수

ArrayList<ArrayList<Integer>> array | 인접 리스트 (그래프의 형태다)

Graph(int capacity) | 우선 초기화를 해야한다. 우린 초기화할 때, capacity를 두고 생성자를 만들 예정이다.

addEdge(int v, int w) | 또한 간선 추가를 해줘야 한다. 물론 간선이 눈으로 보이지 않지만 논리적으로 그렇게 만들 것이다.

connectedWith(int v) | 특정 정점이 무슨 정점들과 연결되어있는지 확인하는 메소드도 필요하다.

전체 코드

public class Graph {
    private final int V;
    private int E;
    private ArrayList<ArrayList<Integer>> arr;

    public Graph(int V){
        this.V = V;
        this.E = 0;
        arr = new ArrayList<>();
        for (int i=0;i<V;i++){
            arr.add(new ArrayList<>());
        }
    }

    public int V(){
        return V;
    }

    public int E(){
        return E;
    }

    public void addEdge(int v, int w){
        arr.get(v).add(w);
        arr.get(w).add(v);
        E++;
    }

    public Iterable<Integer> connectedWith(int v){
        return arr.get(v);
    }
}