Undirected Graph 와 Directed Graph (Digraph)
Undirected Graph: 정점과 간선의 연결관계에 있어서 방향성이 없는 그래프
Directed Graph: 간선에 방향성이 포함되어 있는 그래프
- Directed Graph (Digraph),
- Undirected Graph
V = {1, 2, 3, 4, 5, 6}
E = {(1, 4), (2,1), (3, 4), (3, 4), (5, 6)}
(u, v) = vertex u에서 vertex v로 가는 edge
Degree
Undirected Graph 에서 각 정점(Vertex)에 연결된 간선(Edge) 의 개수를 Degree 라 한다. Directed Graph 에서는 간선에 방향성이 존재하기 때문에 Degree 가 두 개로 나뉘게 된다. 각 정점으로부터 나가는 간선의 개수를 Outdegree 라 하고, 들어오는 간선의 개수를 Indegree 라 한다.
가중치 그래프(Weight Graph)와 부분 그래프(Sub Graph)
그래프를 구현하는 두 방법
인접 행렬 : 정방 행렬을 사용하는 방법
해당하는 위치의 value 값을 통해서 vertex 간의 연결 관계를 O(1) 으로 파악할 수 있다. Edge 개수와는 무관하게 V^2 의 Space Complexity 를 갖는다. Dense graph 를 표현할 때 적절할 방법이다.
- A의 진출차수는 1개 입니다: A —> C
- [0][2] === 1
- B의 진출차수는 2개 입니다: B —> A, B —> C
- [1][0] === 1
- [1][2] === 1
- C의 진출차수는 1개입니다: C —> A
- [2][0] === 1
인접 행렬은 언제 사용할까?
- 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이합니다.
- 예를 들어, A에서 B로 진출하는 간선이 있는지 파악하기 위해선 0 번째 줄의 1 번째 열에 어떤 값이 저장되어있는지 바로 확인할 수 있습니다.
- 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용됩니다.
// directed graph (방향 그래프)
// unweighted (비가중치)
// adjacency matrix (인접 행렬)
// 이해를 돕기 위해 기존 배열의 인덱스를 정점으로 사용합니다 (0, 1, 2, ... --> 정점)
class GraphWithAdjacencyMatrix {
//graph의 constructor를 구현합니다.
constructor() {
this.matrix = [];
}
//vertex를 추가합니다.
addVertex() {
const currentLength = this.matrix.length;
for (let i = 0; i < currentLength; i++) {
this.matrix[i].push(0);
}
this.matrix.push(new Array(currentLength + 1).fill(0));
}
//vertex를 탐색합니다.
//this.matrix에 vertex가 존재한다면 true를 리턴하고, 반대의 경우라면 false를 리턴합니다.
contains(vertex) {
return !!this.matrix[vertex];
}
//vertex와 vertex를 이어주는 edge를 추가합니다.
addEdge(from, to) {
const currentLength = this.matrix.length - 1;
// 두 가지 인자 중, 어느 하나라도 undefined라면, 리턴합니다.
if (from === undefined || to === undefined) {
console.log("2개의 인자가 있어야 합니다.");
return;
}
// from vertex와 to vertex가 전체 그래프의 범위를 벗어난다면, 리턴합니다.
if (
from > currentLength ||
to > currentLength ||
from < 0 ||
to < 0
) {
console.log("범위가 매트릭스 밖에 있습니다.");
return;
}
// this.matrix[from][to]의 값을 1로 바꿔줘서 edge로 연결이 되어 있음을 표시합니다.
this.matrix[from][to] = 1;
}
// from vertex와 to vertex 사이에 edge를 가지고 있는지 여부를 판단합니다.
hasEdge(from, to) {
return !!this.matrix[from][to];
}
// from vertex와 to vertex 사이에 관련이 없다면, edge를 제거 합니다.
removeEdge(from, to) {
const currentLength = this.matrix.length - 1;
// 두 가지 인자 중, 어느 하나라도 undefined라면, 리턴합니다.
if (from === undefined || to === undefined) {
console.log("2개의 인자가 있어야 합니다.");
return;
}
// from vertex와 to vertex가 전체 그래프의 범위를 벗어난다면, 리턴합니다.
if (
from > currentLength ||
to > currentLength ||
from < 0 ||
to < 0
) {
console.log("범위가 매트릭스 밖에 있습니다.");
return;
}
// this.matrix[from][to]의 값을 0으로 바꿔줘서 관련이 없음을 표시합니다.
this.matrix[from][to] = 0;
}
}
인접 리스트 (adjacent list) : 연결 리스트를 사용하는 방법
vertex 의 adjacent list 를 확인해봐야 하므로 vertex 간 연결되어있는지 확인하는데 오래 걸린다. Space Complexity 는 O(E + V)이다. Sparse graph 를 표현하는데 적당한 방법이다.
https://kingpodo.tistory.com/46
6-2. 그래프의 표현(인접 행렬, 인접 리스트, 인접 다중 리스트)
1. 그래프의 표현 그래프를 표현하는 방법은 여러가지가 있지만 그 중 대표적인 방법이 인접행렬(adjacency matrix), 인접 리스트(adjacency list), 인접 다중 리스트(adjacency multi list)이다. 이때 어떤 표현
kingpodo.tistory.com
인접 리스트는 언제 사용할까?
- 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용합니다.
- 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지합니다.
그래프 탐색
그래프는 정점의 구성 뿐만 아니라 간선의 연결에도 규칙이 존재하지 않기 때문에 탐색이 복잡하다. 따라서 그래프의 모든 정점을 탐색하기 위한 방법은 다음의 두 가지 알고리즘을 기반으로 한다.
깊이 우선 탐색 (Depth First Search: DFS)
그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다라는 방법을 우선으로 탐색한다. 일단 연결된 정점으로 탐색하는 것이다.
깊이 우선 탐색의 구현에서 중요한 것은 스택이다.
시간복잡도 : O(V+E) … vertex 개수 + edge 개수
너비 우선 탐색 (Breadth First Search: BFS)
그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. Tree 에서의 Level Order Traversal 형식으로 진행되는 것이다. BFS 에서는 자료구조로 Queue 를 사용한다
우선, 탐색을 시작하는 정점을 Queue 에 넣는다.(enqueue) 그리고 dequeue 를 하면서 dequeue 하는 정점과 간선으로 연결되어 있는 정점들을 enqueue 한다. 즉 vertex 들을 방문한 순서대로 queue 에 저장하는 방법을 사용하는 것이다.
시간복잡도 : O(V+E) … vertex 개수 + edge 개수
Minimum Spanning Tree
그래프 G 의 spanning tree 중 edge weight 의 합이 최소인 spanning tree를 말한다. 여기서 말하는 spanning tree란 그래프 G 의 모든 vertex 가 cycle 이 없이 연결된 형태를 말한다.
Kruskal Algorithm
그래프 G 의 spanning tree 중 edge weight 의 합이 최소인 spanning tree를 말한다. 여기서 말하는 spanning tree란 그래프 G 의 모든 vertex 가 cycle 이 없이 연결된 형태를 말한다.
크러스컬 알고리즘 - 위키백과, 우리 모두의 백과사전
컴퓨터 과학에서, 크러스컬 알고리즘(영어: Kruskal’s algorithm)은 최소 비용 신장 부분 트리를 찾는 알고리즘이다. 변의 개수를 E {\displaystyle E} , 꼭짓점의 개수를 V {\displaystyle V} 라고 하면 이 알고
ko.wikipedia.org
어떻게 cycle 생성 여부를 판단하는가?
Graph 의 각 vertex 에 set-id라는 것을 추가적으로 부여한다. 그리고 초기화 과정에서 모두 1~n 까지의 값으로 각각의 vertex 들을 초기화 한다. 여기서 0 은 어떠한 edge 와도 연결되지 않았음을 의미하게 된다. 그리고 연결할 때마다 set-id를 하나로 통일시키는데, 값이 동일한 set-id 개수가 많은 set-id 값으로 통일시킨다.
Time Complexity
- Edge 의 weight 를 기준으로 sorting - O(E log E)
cycle 생성 여부를 검사하고 set-id 를 통일 - O(E + V log V) => 전체 시간 복잡도 : O(E log E)
Prime Algorithm
초기화 과정에서 한 개의 vertex 로 이루어진 초기 그래프 A 를 구성한다. 그리고나서 그래프 A 내부에 있는 vertex 로부터 외부에 있는 vertex 사이의 edge 를 연결하는데 그 중 가장 작은 weight 의 edge 를 통해 연결되는 vertex 를 추가한다. 어떤 vertex 건 간에 상관없이 edge 의 weight 를 기준으로 연결하는 것이다. 이렇게 연결된 vertex 는 그래프 A 에 포함된다. 위 과정을 반복하고 모든 vertex 들이 연결되면 종료한다.
Time Complexity
=> 전체 시간 복잡도 : O(E log V)
'자료구조' 카테고리의 다른 글
| 리스트 (0) | 2021.10.17 |
|---|---|
| 덱 (0) | 2021.10.17 |
| 재귀함수 (0) | 2021.10.07 |
| 자료구조(큐, 트리, 해시 테이블) (0) | 2021.09.06 |
| 자료구조(스택, 트리) (0) | 2021.09.05 |