개념 및 용어
그래프란?
정점(vertex)과 간선(edge)으로 이루어진 자료구조
용어
차수(degree)
어떤 정점과 연결된 간선의 개수
방향그래프의 경우, outdegree와 indegree가 존재한다
- outdegree : 해당 정점에서 나아가는 방향의 간선
- indegree : 해당 정점으로 들어오는 방향의 간선
사이클(cycle)
출발한 노드로 다시 돌아오는 경로를 의미한다
방향그래프의 경우에는 그래프의 방향에 주의해야 한다. 연결되어 있기만 하다고 사이클이 존재하는 것이 아니다.
그래프의 종류
순환그래프
사이클이 존재하는 그래프
비순환그래프
사이클이 존재하지 않는 그래프
완전그래프
모든 정점이 서로 연결되어 있는 그래프
연결그래프
임의의 두 정점 사이에 경로가 항상 존재하는 그래프
단순그래프
두 정점 사이의 간선이 1개 이하이고, 루프가 존재하지 않는 그래프
- 루프 : 자기자신에서 출발해서 자기 자신으로 돌아오는 간선
그래프 표현법
인접행렬
공간복잡도 : O(V^2)
시간복잡도
어떤 두 정점의 연결 여부를 확인하는 경우 : O(1)
어떤 정점에 연결되어 있는 모든 정점의 목록을 확인하는 경우 : O(V)
유리한 상황
- 간선 개수(E)가 많아 V^2에 가까운 경우
- 두 정점의 연결여부를 자주 확인하는 경우
인접리스트
공간복잡도 : O(V+E)
시간복잡도
정점u와 v의 연결 여부를 확인하는 경우 : O(min(deg(u), deg(v))
정점v에 연결되어 있는 모든 정점의 목록을 확인하는 경우 : O(deg(v))
유리한 상황
- 연결된 정점의 모든 정점을 자주 확인해야 하는 경우
- 간선의 개수(E)가 V^2보다 훨씩 적은 경우
