Graph

Graph

    - 노드와 간선으로 구성된 자료구조

    - 객체 간의 관계를 표현하는 자료구조

    - root와 부모-자식 관계가 없음

    - 트리는 그래프의 부분집합

    - 네트워크 모델

 

 

 

용어 표현

    - 정점(vertex) : 객체. 노드

    - 간선(edge) : 객체를 연결하는 선. 노드를 연결하는 선

    - 인접 정점 : A 정점에서 간선으로 연결된 다른 정점

    - 진입 차수 : 방향 그래프에서 A 정점으로 들어오는 간선의 수

    - 진출 차수 : 방향 그래프에서 A 정점에서 나가는 간선의 수

    - 단순 경로 : 경로 중에 반복되는 정점이 없는 경로. 같은 간선을 포함하지 않는 경로

    - 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

 

 

 

그래프의 종류

1) 무방향 그래프

    - 간선을 통해서 양방향으로 이동

    - (A, B)와 (B, A)는 동일

 

2) 방향 그래프

    - 간선을 통해서 한방향으로 이동

    - <A, B>와 <B, A>는 다름

 

3) 가중치 그래프

    - 간선에 가중치가 할당된 그래프

 

4) 연결 그래프

    - 모든 정점 사이에 경로가 항상 존재하는 그래프

 

5) 비연결 그래프

    - 특정 정점 사이에 경로가 존재하지 않는 그래프

 

6) 사이클 그래프

    - 사이클을 포함하는 그래프

 

7) 완전 그래프

    - 모든 정점이 서로 간선으로 연결된 그래프

 

 

그래프 구현 방법

1) 인접 행렬

    - N*N 배열을 만들어서 구현

    - 장점

        * 두 정점에 대한 간선의 정보를 O(1)에 접근 가능. ex) matrix[i][j]

 

    - 단점

        * 모든 간선에 대한 정보를 저장하기 때문에 간선이 적은 희소 그래프의 경우에는 공간 낭비

        * N^2의 공간 필요

        * 한 정점의 인접 정점을 찾기 위해서는 모든 정점을 탐색. 시간복잡도 O(n)

        * 그래프 내의 모든 간선을 알기 위해서는 O(n^2)이 걸림

 

    - 사용

        * 간선이 많은 밀집 그래프에서 유용

 

 

2) 인접 리스트

    - 그래프 이론에서 그래프를 표현하기 위한 방법으로 한 정점에서 연결되어 있는 정점들을 연결 리스트로 구현

 

    - 장점

        * 필요한 공간 만큼 사용하기 때문에 공간 활용도 높음

        * 한 정점의 인접 정점에 대한 정보를 인접 행렬보다 빠르게 찾을 수 있음

        * 그래프 내의 모든 간선을 아는 데 O(n+e)이 걸림

 

    - 단점

        * 두 정점에 대한 간선의 정보를 O(n)에 접근 가능. 인접 행렬보다 오래 걸림

 

    - 사용

        * 간선이 적은 희소 그래프에서 유용

 

 

사용

    - GNN

    - 지도, 지하철 노선, 통신망, 도로 등

 

 

 

그래프 탐색

https://namu.wiki/w/%EB%84%93%EC%9D%B4%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89

 

1) DFS(깊이 우선 탐색)

    - Root 노드에서 시작하여 다음 분기(branch)로 넘어가기 전에 선택한 분기를 먼저 완벽하게 탐색하는 방법

    - 재귀함수 또는 스택으로 구현

 

    - 장점

        * 현 경로에 있는 노드들만 기억하므로 저장공간의 수요가 적음. 하지만 깊이 들어갈 경우, stack overflow에 유의

        * 목표 노드가 깊이 있을 경우, 빠르게 해를 구함

 

    - 단점

        * 무한한 길이를 가진 경로가 존재하고 탐색 목표가 다른 경로에 존재할 경우, DFS는 해를 찾을 수 없음. 이 경우에 특정 깊이를 설정하여 그 깊이에 도달하면 다른 경로를 탐색하게 함

 

 

2) BFS(넓이 우선 탐색)

    - Root 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법

    - 큐로 구현

 

    - 장점

        * 무한한 길이를 가진 경로가 존재하고 탐색 목표가 다른 경로에 존재할 경우, BFS는 모든 경로를 동시에 진행하기 때문에 탐색이 가능

        * 간선을 한 번씩 탐색하기 때문에 가중치가 없는 그래프에서 출발 노드에서 도착 노드까지 최단 경로를 알 수 있음

 

    - 단점

        * 경로가 매우 길 경우에는 탐색 가지가 급격하게 증가하여 많은 저장 공간 필요

 

 

 

참고

    - en.wikipedia.org/wiki/Graph_(abstract_data_type)

    - coding-factory.tistory.com/610

    - gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

    - namu.wiki/w/%EB%84%93%EC%9D%B4%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89

    - ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89