2022. 12. 6. 16:30ㆍ자료구조
*이웃: 노드가 가리키고 있는 노드
* 갔던 데 또 가는 반복을 피하기 위해 진행됨에 따라 방문한 정점은 표시할 필요가 있다.
1) depth-first search(깊이 우선 탐색)//이웃 하나를 정해서 탐색하고 다음 노드의 이웃 탐색
검색은 시작 정점에서 이웃 중 하나로, 다음으로 이웃의 이웃 중 하나로 진행된다.
검색을 더 진행할 수 없는 경우 백업해야 한다. (전 단계로 돌아가야함)
스택을 사용하거나 재귀적으로 구현할 수 있다.
-스택을 이용해서 구현 방법
1. 방문여부를 저장할 배열과 방문한 노드를 저장할 스택 생성
2. 배열을 모두 false로 초기화
3. 탐색 시작->지나온 노드에 해당하는 인덱스는 true로
4. 탐색 노드의 인접 노드들 중 방문하지 않은 노드가 있다면 탐색 노드를 스택에 삽입-> 인접 노드로 이동
5. 만약 탐색 노드의 인접 노드 중 방문하지 않은 노드가 없다면 이전 노드로 돌아가기 위해 스택에서 이전 노드 꺼내기
6. 스택이 비어 있으면 탐색 종료
-재귀적으로 구현 방법
1. 시작점이 그래프에서 유효한 넘버인지 체크
2. 방문여부 표시할 배열(maked[aGraph.MAX]) 전부 false로 세팅
3. 실제로 탐색을 실행할 별도의 함수(rec_dfs)를 재귀적으로 호출
template <class Process, class Item, class SizeType>
void rec_dfs(Process f, graph<Item>& g, SizeTypev,boolmarked[ ])
//g:그래프,f:어떤 행동을 취할 함수,v:노드의 인덱스 번호,marked[]:방문여부 표시할 배열
{ std::set<std::size_t> connections = g.neighbors(v);//이웃 탐색
std::set<std::size_t>::iterator it ;//반복자
marked[v] = true ;//방문 노드 표시
f(g[v]) ;//해당 노드에 어떤 행동을 취할 함수 호출
for (it=connections.begin() ; it != connections.end() ; ++it)//그래프 노드 시작부터 끝까지
{
if (!marked[*it])//방문하지 않은 노드있다면
rec_dfs(f, g, *it, marked) ;//재귀호출
}
}2) Breadth-first search(너비 우선 탐색)//이웃들을 다 탐색하고 다음 노드로 가서 그 이웃들 탐색
검색은 시작 정점에서 각 이웃까지 진행
모든 도달 가능한 정점이 처리되면 검색이 종료
모든 이웃을 처리한 후 이웃의 이웃에 대한 검색 진행됩니다.
큐를 사용하여 구현할 수 있음
-큐를 이용하여 구현방법:
1. 방문 여부를 저장할 배열 생성 후 모든 값 false로 초기화, 빈 큐 생성
2. 탐색 시작->지나온 노드에 해당하는 인덱스는 true로
3. 탐색 노드의 인접 정점 중 방문하지 않은 모든 노드를 큐에 삽입
4. 큐에 들어온 순서대로 해당 노드 탐색-> 탐색하면 해당 노드를 큐에서 꺼냄 (fisrt in fisrt out으로)
5. 탐색 노드의 인접 정점 중 방문하지 않은 노드가 없다면
큐에 저장된 다음 노드 꺼내고 그 노드의 인접 정점들의 방문 여부 확인.
만약 큐가 비어있다면 탐색 종료
-재귀적으로 구현방법:
1. 시작 정점이 그래프의 유효한 정점 번호인지 확인
2. marked[ ]의 모든 구성 요소를 false로 설정
3. 시작 정점을 처리하고 방문했다고 표시(makede[] true로 변경)한 후 큐에 넣기
4. 큐가 비워질 때까지 다음 단계를 반복
4.1. 큐에서 정점 v를 제거
4.2. 표시되지 않은 각 이웃v에 대해 do:
4.2.1. 를 처리하고 표시한 후 u를 대기열에 배치합니다.
template <class Process, class Item, class SizeType>
void breadth_first(Process f, graph<Item>& g, SizeTypestart)
{
bool marked[g.MAX];//방문 표시할 배열
std::set<std::size_t> connections;//해당 노드가 가리키는 노드 저장할 set
std::set<std::size_t>::iterator it ;
std::queue<std::size_t> vertex_queue;//방문한 노드 넣을 큐
assert( start < g.size( ));//정점이 그래프의 유효한 번호인지 확인
std::fill_n(marked, g.size( ), false);//방문 표시 배열 false로 초기화
/* MAIN PROCESS */
marked[start] = true;//방문 정점 true로
f(g[start]) ;//해당 노드에 어떤 행동을 취할 함수
vertex_queue.push(start) ;//방문 정점 큐에 넣기
do {
connections = g.neighbors(vertex_queue.front());//큐에 넣은 노드의 이웃을 set에 저장
vertex_queue.pop() ;//방문 정점 큐에서 제거
for (it=connections.begin() ; it!=connections.end() ; ++it){
//노드의 이웃들을 탐색할 반복자
if (!marked[*it]){
//해당 노드가 방문하지 않은 상태라면
marked[*it] = true;//방문하고 true로
f(g[*it]) ;//해당노드에 어떤 행동 취할 함수
vertex_queue.push(*it) ;//방문 노드 큐에 넣기
}
}
} while (!vertex_queue.empty() ) ;//큐가 비어있지 않을때까지 반복
}3) 다익스트라 알고리즘: 한 노드에서 다른 모든 노드까지의 최단 경로 구하는 알고리즘
-구현방법:
1. 시작정점 설정
2. 출발 정점 기준 다음 정점까지 가는 거리비용 계산하여 해당 인덱스에 저장,
지나온 정점을 allowedVertexSet에 저장
3.방문하지 않은 정점 중 가장 거리비용이 적은 정점 선택: v1
다음 정점까지 가는 거리 비용 계산하여 해당 인덱스에 저장
(이미 저장되어 있는 인덱스는 값을 비교하여 최소값을 저장),
지나온 정점 set에 저장
4. 2,3 반복
-수도코드:
*distance[]//해당 노드까지 가중치 계산한 값 저장할 배열
allowed_vertices//지나온 노드 저장할 set
1. 모든 노드 distance[i]=무한대//i는 노드 번호
distance[start]=0//출발 노드는 0으로 설정
2. allowed_vertices={};
3.for(allowed_size=1;allowde_size<n;++allowed_size) //n은 노드의 개수
3.a next=allowed_vertices에 들어가 있지 않은 인접 노드의 인덱스
distance[next]=거리의 최소값
3.b next를 allowed_vertices에 추가
3.c
for(v=0;v<n;++n)
{
if(v가 allowed_vertices에 들어있지 않고 next->v인 엣지가 존재한다면)
{
sum=distance[next]+weight(next,v);
if(sum<distance[v]){
distance[v]=sum;
prodecessor[v]=next//distance[v]가 업데이트될 때 어떤 정점이 next였는지 추적해야 한다.
}
}
}모든 노드를 방문하게 되면 탐색 종료, 배열에 저장된 값이 시작 노드부터 각 노드까지의 최단 거리