알고리즘 이론 깨부수기 그래프

Graph

Undirected Graph

방향성이 없는 그래프를 Undirected Graph

Directed Graph (Digraph)

간선에 방향성이 포함되어 있는 그래프를 Directed Graph

Degree

Undirected Graph 에서 각 정점(Vertex)에 연결된 Edge 의 개수를 Degree 라 한다.

Directed Graph 에서는 간선에 방향성이 존재하기 때문에 Degree 가 두 개로 나뉘게 된다.

각 정점으로부터 나가는 간선의 개수를 Outdegree 라 하고, 들어오는 간선의 개수를 Indegree 라 한다.

가중치 그래프(Weight Graph)와 부분 그래프(Sub Graph)

가중치 그래프란 간선에 가중치 정보를 두어서 구성한 그래프를 말한다.

비가중치 그래프 즉, 모든 간선의 가중치가 동일한 그래프

부분 그래프는 본래의 그래프의 일부 정점 및 간선으로 이루어진 그래프를 말한다.

그래프를 구현하는 두 방법

인접 행렬 (adjacent matrix) : 정방 행렬을 사용하는 방법

장점

• 2차원 배열에 모든 정점들의 간선 정보가 있기 때문에, 두 정점을 연결하는 간선을 조회할 때 O(1) 시간복잡도로 가능하다.
• 정점(i)의 차수를 구할 때는 다음과 같이 인접행렬(M)의 i번째 행의 값을 모두 더하면 되므로 O(n)의 시간복잡도를 가진다.
• 구현이 비교적 간단하다.

단점

• 간선의 수와 무관하게 항상 n² 크기의 2차원 배열이 필요하므로 메모리 공간이 낭비된다.
• 그래프의 모든 간선의 수를 알아내려면 인접행렬 전체를 확인해야 하므로 O(n²)의 시간이 소요된다.

인접 리스트 (adjacent list) : 연결 리스트를 사용하는 방법

장점

• 존재하는 간선만 관리하면 되므로 메모리 사용 측면에서 보다 효율적이다.
• 그래프의 모든 간선의 수를 알아내려면 각 정점의 헤더 노드부터 모든 인접리스트를 탐색해야 하므로 O(n+e)의 시간이 소요된다.

단점

• 두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 인접 리스트를 탐색해야 하므로 정점의 차수만큼의 시간이 필요하다.
• 구현이 비교적 어렵다.

그래프 탐색

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

깊이 우선 탐색은 가능한 가장 깊이 들어갔다가 더이상 파고들어갈 수 없을때 이전상태로 복귀하고 파고들어가고 나오고를 반복하는 형태입니다.

시간복잡도 : O(V+E) … vertex 개수 + edge 개수

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

너비우선 탐색방법은 어떤 방점에서 연결된 가장 빠른 정점들을 방문한 후에 다시 같은 방법들을 연결된 순서들을 다시 방문해 나가는 방법입니다.

Time Complexity : O(V+E) … vertex 개수 + edge 개수  ! BFS 로 구한 경로는 최단 경로이다.