[2019.04.03] 자료구조- Graph의 개념

단순히 노드와 그 노드를 연결하는 선들을 하나로 모아 놓은 구조이다.

# 그래프 종류

• 무방향 그래프 : 방향이 없는 간선 사용, 양방향 이동가능
• 방향 그래프 : 방향 간선 사용, 한쪽으로만 이동가능
• 가중치 그래프 : 선에 가중치(우선순위? 순서?)가 할당된 그래프

부분 그래프 종류들

# 그래프 표현방법

인접행렬 : 노드의 인접여부를 2차원 배열로 구분 

노드의 개수만큼 행 열을 만든다. 각 행열에 맞게, 선이 존재하면 해당 행열 자리의 값은 1이 들어가고 없으면 0이 들어간다.

인접 리스트 : 각 정점에 인접한 정점을 연결 리스트로 표현

각 노드가 연결된 선을 링크드리스트로 연결한다. 연결된 노드들을 한번씩 접근하여 해당 노드의 가중치를 자신의 노드 리스트에 노드를 추가한다.

# 그래프 탐색

깊이 우선 탐색(DFS) : 자기 자신을 다시 호출하는 순환 알고리즘 형태. 

자신과 인접해 있는 노드 중 방문하지 않은 노드들만 방문하는 방식이다. 위 사진에서 보면, vo에서 시작하여 인접한 노드 v1을 방문한다. v1에서 인접한 v3을 방문하고, v3노드에서 인접한 노드인 v5 방문, 그다음 v4방문 그다음 v2를 방문한다. 만약 인접한 노드가 있으면 이미 한번 방문한 노드면 방문하지 않는다. 

너비우선 탐색(BFS) : 시작정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

너비우선 탐색에는, 방문한 정점들을 차례로 저장한 후 꺼낼 수 있는 큐가 필요. 큐가 소진될 때까지 계속한다.

위 그림을 보면, vo0부터 시작하여, 인접한 노드가 v1, v2이므로 한번씩 방문한다. v1부터 방문하였으므로 v1에 인접한 노드 v3과 v4를 방문한다. 이후에 아까 v1노드 다음으로 방문한 v2노드의 인접한 노드를 방문한다. v4와 v5노드 중 v4는 이미 방문하였으므로, v5 노드만 방문한다.

그래프 탐색 수도코드

# 깊이우선 탐색

 

# 너비 우선 탐색