[BK] 알고리즘 기초 - 그래프

그래프

(Graph)

- 자료구조 일종

- 정점(Node, Vertex)

- 간선(Edge): 정점간의 관계

- G = (V,E)로 나타냄

경로

(Path)

- 정점 A -> B로 가는 경로

사이클

(Cycle)

- 정점 A에서 다시 B로 돌아오는 경로

단순 경로와 단순 사이클

- 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클

- 일반적으로 지칭하는 경로/사이클

유향 그래프

(Directed Graph)

- 간선에 방향이 있음

무향/양방향 그래프

(Undirected / Bidirection Graph)

- 간선에 방향이 없음

루프

(Loop)

- 간선의 양 끝점이 같은 것

가중치

(Weight)

- 간선에 가중치가 있는 경우: A->B로 이동하는 거리, 시간, 비용 등

- 가중치가 없으면 1이라고 생각하면 됨

차수

(Degree)

- 정점과 연결되어 있는 간선의 개수

그래프의 표현

인접 행렬

(Adjacenct-matrix)

- VxV 크기의 이차원 배열 이용

- A[i][j] = w / 0 (i->j 간선이 있을 때 그 가중치 / 없을 때)

- 공간 복잡도: O(V^2)

인접 리스트

(Adjacenct-list)

- 주로 vector 이용해 구현

- A[i]: i와 연결된 정점을 포함

- A[i]: i와 연결된 정점과 그 간선의 가중치를 포함(pair로 구현)

- 공간 복잡도: O(E)

간선 리스트

(Edge-list)

- STL 사용 어려울 때 사용

- 배열 이용해 구현

- E라는 배열에 모든 간선 저장

그래프의 탐색

- DFS: 깊이 우선 탐색

- BFS: 너비 우선 탐색

깊이 우선 탐색

(Depth First Search, DFS)

- 스택 이용

- 갈 수 있는 만큼 최대한 많이 가고, 갈 수 없으면 이전 정점으로 돌아감

너비 우선 탐색

(Breadth First Search)

- 큐 이용

- 큐를 사용해 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식

- 큐에 넣을 때 방문했다고 체크해야 함

연결 요소

(Connected Component)

- 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 함

- 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안됨

- DFS / BFS 이용

이분 그래프

(Bipartitie Graph)

- A와 B로 나눌 수 있는 그래프

- A/B에  포함되어 있는 정점끼리 연결된 간선 없음

- 모든 간선 한 끝 점은 A에, 다른 끝 점은 B에

- DFS / BFS 이용