그래프
객체의 일부 쌍들이 '연관되어' 있는 객체 집합 구조
- 정점 6개, 간선 8개
- 방향이 없는 그래프
- 정점 : {1, 2, 3, 4, 5, 6}
- 간선 : { (1, 2), (1, 5), (2, 5), (2, 3), (3, 4), (2, 4), (4, 5), (4, 6) }
그래프 표현 방식
그래프를 이용한 작업을 수행하기 편하도록 그래프를 효율적으로 저장하는 방식
- 인접 행렬
1 0 로 구성된 2차원 행렬로 나타냄
구현 : 2차원 배열
- 인접 리스트
각 정점의 인접하는 정점들을 나타냄
구현 : 연결 리스트 또는 동적 배열 (std::vector)
- 간선 리스트
DFS, BFS
E라는 배열에 간선을 모두 저장. 각 간선의 앞 정점을 기준으로 개수를 셈
그래프 탐색
그래프의 정점을 적당한 순서로 한 번씩 모두 보는 방법
DFS (깊이 우선 탐색)
재귀함수나 스택으로 구현
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄 - 2번의 과정을 수행할 수 없을 때까지 반복
- 노드 방문 시 방문(visited) 여부를 반드시 검사해야 함. 아니면 무한루프에 빠질 수 있음
- 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)를 사용
- 깊이 제한에 도달할 때까지 목표 노드가 발견되지 않으면 최근에 첨가된 노드의 부모 노드로 돌아와서(qoremfozld),
부모 노드에 이전과는 다른 동작자를 적용하여 새로운 자식 노드를 생성
[장점]
- 단지 현 경로 상의 노드만을 기억하면 되므로 저장공간의 수요가 비교적 적음
- 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있음
[단점]
- 해가 없는 경로에 깊이 빠질 가능성이 있음.
실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용함 - 얻어진 해가 최단 경로가 된다는 보장 X
DFS는 해에 다다르면 탐색이 끝나므로 목표에 이르는 경로가 다수임 -> 최적이 아닐 수도 있음
BFS (너비 우선 탐색)
큐를 이용하여 구현
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리
- 2번 반복
- 특정 조건의 최단 경로 알고리즘을 계산할 때 사용
[장점]
- 출발 노드에서 목표 노트까지의 최단 길이 경로 보장
[단점]
- 경로가 매우 길 경우 탐색 가지가 급격히 증가하여 보다 많은 기억 공간 필요
- 해가 존재하지 않는다면, 유한 그래프의 경우 모든 그래프를 탐색한 후에 실패로 끝남
- 무한 그래프의 경우, 결코 해를 찾지도 못하고 끝내지도 못함
Server Engineer