- 정점의 개수를 V라고 했을 때, V x V 크기의 이차원 배열을 사용한다.
- A[i][j] = 1이면 간선이 있고, A[i][j] = 0이면 간선이 없다.
- 정점 V, 간선 E라고 할 때, 공간복잡도는 V x V이다. (이차원 배열을 사용하기 때문)
- 모든 간선을 알아보는데 걸리는 시간은 O(V)이다. 왜냐하면 하나의 정점에 연결된 간선을 확인하려면 하나의 행을 전부 확인해야 하기 때문이다.
-
리스트를 이용해서 구현한다.(Java = ArrayList)
-
인접리스트에서 정점 V, 간선 E라고 할 때, 공간복잡도 O(E)이다. 왜냐하면 간선이 있는 경우에만 저장하기 때문에 간선의 개수와 같다.
- 한 정점과 연결된 모든 간선을 찾는 시간은 O(차수)이다. 왜냐하면 하나의 정점에 연결되어 있는 간선들이 리스트 형태로 연결되어 있기 때문임
(i, j)가 있는지 없는지를 파악하는 것은 인접행렬의 경우 O(1), 인접리스트의 경우 O(V)만큼의 시간이 걸리지만, 그래프 알고리즘에서
많이 필요한 것은 하나의 정점에 연결된 간선들을 확인하는 것이 더 많이 쓰이기 때문에 인접리스트를 많이 사용한다.
목적 : 임의의 정점에서 시작해서 연결되어 있는 모든 정점을 반드시 한번씩 방문한다.
DFS, BFS의 차이는 어떤 순서로 정점을 방문할 것이냐의 차이
- 하나의 정점을 방문해서 갈 수 있는 만큼 갔다가 돌아와서 나머지를 방문하는 방식 -
Stackor재귀호출을 사용
-
하나의 정점에 연결된 정점을 한번에 방문 (복사되어 동시에 여러곳 방문한다고 생각하면 됨) -
Queue를 사용 -
모든 가중치가 1이라면
최단거리를 구할 때 사용한다. (참고)