그래프
연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조
Tree는 사이클이 허용되지 않는 그래프이다.
✔ 개념
정점(vertex) / 노드(node) : 위치
간선(edge) / 링크(link) : 위치간의 관계
인접 정점 : 간선에 의해 직접 연결된 노드
차수 : 하나의 노드에 인접한 노드의 수
경로 길이 : 경로를 구성하는 데 사용된 간선의 수
단순 경로 : 경로 중에서 반복되는 간선이 없을 경우
사이클 : 단순경로의 시작 정점과 종료 정점이 동일한 경로
오일러 경로 : 모든 간선을 한 번만 통과하면서 처음 정점으로 돌아오는 경로
오일러 정리 : 간선이 짝수일 때만 오일러 경로가 존재
부분 그래프 : 원래의 그래프의 일부 정점 및 간선으로 이루어진 그래프
✔ 그래프 종류
영 그래프 (null graph) : 비어있는 그래프
완전 그래프 (complete graph) : 모든 노드가 서로 연결되어 있는 그래프
연결 그래프 (connected graph ) : 무방향 그래프에 있는 모든 노드쌍에 대해 항상 경로가 존재한 경우
정규 그래프 (regular graph) : 모든 정점이 동일한 개수의 정점을 갖는 것 ( 모든 정점의 차수가 같은 그래프)
이분 그래프 (bipartite graph) : 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로 칠할 수 있는 그래프 ( 모든 정점이 두 그룹으로 나눠지고 같은 그룹끼리는 인접하지 않은 그래프 )
완전 이분 그래프 (complete bipartite graph) : 이분 그래프 중에서도 서로 다른 그룹이라면 서로 다른 그룹끼리 모두 연결되어 있는 그래프
가중치 그래프 : 간선에 가중치가 주어진 그래프 ( 가중치는 양,음 모두 가질 수 있다. )
밀집 그래프 : 간선이 많이 존재하는 그래프
희소 그래프 : 간선이 적은 그래프
✔ 표현 방법
인접 행렬 (Adjacency Matrix) ( 2차원 배열 )
인접 리스트 (Adjacency List) ( 연결 리스트 )
근접 행렬 (= 발생 행렬,부속 행렬) (Incidence Matrix) (2차원 배열)
✔ 시간 복잡도 ( Big-O)
저장 (storage)
간선 추가 (Add Vertex)
엣지 추가 (Add Edge)
간선 삭제 (Remove Vertex)
엣지 삭제 (Remove Edge)
Query
인접 리스트 (Adjacency list)
O(|V|+|E|)
O(1)
O(1)
O(|V|+|E|)
O(|E|)
O(|V|)
인접 행렬 (Adjacency matrix)
O(|V|^2)
O(|V|^2)
O(1)
O(|V|^2)
O(1)
O(1)
근접 리스트 (Incidence list)
O(|V|+|E|)
O(1)
O(1)
O(|E|)
O(|E|)
O(|E|)
근접 행렬 (Incidence matrix))
O(|V|+|E|)
O(|V|+|E|)
O(|V|+|E|)
O(|V|+|E|)
O(|V|+|E|)
O(|E|)
✔ 탐색
깊이 우선 탐색( DFS )
시작 노드에서 출발하여 먼저 다음 노드로 향하면서 탐색한 곳은 표시를 해두고 더이상 갈 수 있는 노드가 없다면 이전 노드에서 다른 노드로 향하여 모든 노드를 탐색하는 방식. Stack 을 사용하여 구현.
노드의 수가 n, 간선의 수가 e 인 그래프의 DFS 탐색 시간은 인접 리스트 O(n+e) / 인접 행렬 O(n^2) --> 희소 그래프인 경우 dfs에서는 인접 리스트 사용이 시간적으로 더 유리하다.
너비 우선 탐색( BFS )
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 큐를 이용하여 노드를 삽입하고 방문한 노드는 큐에서 빼내는 방식으로 구현
노드의 수 n, 간선의 수 e인 그래프 BFS탐색 시간은 인접 리스트 O(n+e) / 인접 행열 O(n^2) --> 희소그래프의 경우 인접 리스트를 사용하는 것이 유리하다.
✔ 신장 트리
구현
✔ 최소 비용 신장 트리 (MST)
한마디로 무방향의 가중치가 있는 연결 그래프
알고리즘 종류
Krustkal MST
edge 정렬이 속도를 결정짓기 때문에 egde 수가 적은 희소 그래프 유리
Prim MST
✔ 그래프 알고리즘 복잡도
평균 (Average)
최악 (Worst)
Kruskal 알고리즘
Θ( |E| log|E| )
O( |V|^2)
프림 알고리즘 (Prim's algorithm))
Θ( |E| log|V| )
O( |V|^2 )
다익스트라 알고리즘 (Dijkstra's algorithm)
Θ( |E| log|V| )
O( |V|^2 )
벨먼-포드 알고리즘 (Bellman-Ford algorithm)
Θ( |E| * |V| )
Θ( |V|^3 )
플로이드-워셜 알고리즘 (Floyd-Warshall algorithm)
Θ( |V|^3 )
O( |V|^3 )
A* 알고리즘 (A* search algorithm)
Θ( |E| )
O( b^d )
위상 정렬 (Topological sort)
Θ( |V| + |E| )
O( |V| + |E| )
Last updated