뻔뻔한블로그

인접 행렬법

단점 : 메모리낭비 그래프의 정점의 개수를 V라고 하면 V * V행렬을 이용하여 표현한다. Vi가 행렬 i행과 i열에 대응된다고 할 때 만일 Vi와 Vj간의 간선이 있을 경우 [i,j]와 [j,i]요소를 1로 하고, 아닌 경우는 0으로 한다.

인접 리스트법

단순 연결리스트를 이용하여 각 정점에 간선으로 연결된 정점들을 주렁주렁 달아놓는 방법을 말한다. 인접행렬법과 대조적으로 인접리스트법에서는 그래프를 반사적으로 구성하기 위해 명시적으로 정보를 저장하지 않는다. 모든 간선에 대한 정보를 저장하지는 않는다. 정점에서 가능한 필요한 간선만 기록하게 된다.

탐색

우선탐색(DFS)과 너비 우선 탐색(Breadth First Search,BFS)방법이 있다. 나무와 다르게 그래프는 방향성이 없기 때문에 순서가 매번 다르다.

인접행렬의 깊이 우선 탐색

시작 정점에서 시작하여 그 정점과 연결된 정점으로 다음에는 그 정점에서 다시 연결된 정점의 순으로 진행된다.(당연히 방문한 정점은 다시 방문하지 않는다)

=> 탐색의 위치가 간선을 따라 깊이 들어가면서 움직인다.

비재귀

스택을 사용, 유일한 순회 순서가 존재하지 않음

인접 리스트의 깊이 우선 탐색

정점의 연결 상태를 알아내는 방법이 인접행렬과 다르다. 인접리스트로 그래프를 구현할 경우에는 순회 순서가 간선의 입력 순서에 민감하다.

먼저 입력된 간선이 각 리스트에서 앞에 위치하게 된다.

방문하지 않은 모든 요소를 탐색 ver

인접 행렬의 너비 우선탐색

깊이 우선 탐색과 대조적으로 우선 시작하는 정점과 연결된 정점을 탐색하고 다시 시작 정점의 다른 연결된 정점을 찾는 순으로 탐색한다.  트리순회의 레벨순회와 비슷하다고 생각하면 된다.

그래프의 불규칙성과 여러 개의 연결 요소로 구성된 다는 점을 고려해야 하므로 방문한 정점에 대한 체크가 필요하다. 재귀 호출 부분은 하나의 연결 요소만을 탐색하게 되므로 탐색 부분의 바깥에서 각 연결 요소의 시작 정점을 찾아내어 탐색을 시켜주는 부분이 필요하다.

인접리스트의 너비 우선 탐색

학습참고 : c로배우는 알고리즘