2021. 3. 12. 15:36ㆍ카테고리 없음
<용어>
formula -> G=(V, E) : V는 node, E는 edge
adjacent vertex: 인접한 node
degree: 하나의 node를 기준으로 adjacen vertex의 갯수
path: 하나의 node에서 다른 node로 가는 경로
directed graph: edge의 방향이 있는 그래프
strongly connedted graph: edge의 방향이 양방향인 경우
weighted graph: edge에 가중치가 있는 경우
<graph의 표현>
- 첫번째 방법은 2차원 matrix로 표현하여, 하나의 node를 기준으로 인접node를 1로 나타내는 법이다. weight가 있다면 숫자로 나타낸다.
- 0으로 소모되는 메모리가 많아 자주 사용되진 않는다.
- 따라서 Linked List로 표현한다
<graph 클래스>
- node를 쭉 밀어넣을 array와, edge를 만들어 노드간의 연결을 밀어넣을 dictionary를 만든다
- addNode: 특정 node v를 node 배열에 넣고, adjList에는 'v' =[ ] 라는 원소를 만들어준다
- addEdge: 'v'라는 key를 가진 entry 를 찾아 value에 w를 넣어준다.
- 무방향 그래프라면 서로 순서를 바꾸어 edge를 한번 더 추가해준다
<graph 순회>
- 한번 순회한 노드는 순회했다는 표시를 해주는 것이 중요하다
- 정점당 방문횟수는 2회를 초과하면 안된다.
- 방문한 노드의 상태는 방문전/ 방문완료-탐색전/ 탐색완료로 나눠 관리한다.
1) BFS(너비우선탐색)
- 큐사용-> 가장 오래전에 방문하지 않은 노드를 방문
- 방문예정인 노드를 queue에 넣고 해당 노드를 방문하면 인접 노드들을 탐색한다.
- 방문만 했던 노드는 grey로, 방문하지 않은 노드는 white로, 방문하여 탐색이 끝난 노드는 black으로 설정
- 응용: 최단경로 찾기
2) DFS(깊이우선탐색)
- 스택사용-> 인접 정점을 방문
- 추후 이어 포스팅