[C언어] 자료구조 - 그래프 탐색 -4

 그래프의 탐색은 가장 기본이라고 할 수 있을거야. 그럼에도 조금 나중에 배우는 이유는

제일 중요해서 그래 기본이 가장 중요한거지

 

그래프에서 탐색은 특정한 것을 찾는다기보다는

"시작 정점부터 차례대로 모든 정점들을 한 번씩 방문" 을 의미해

 

 

또한 연결되었는지 안되어있는지가 중요한 회로같은 경우

탐색만으로도 문제를 발견할 수 있는거지

 

•도로망 예: 특정 도시에서 다른 도시로 갈 수 있는지 여부

•전자회로 예: 특정 단자와 다른 단자의 연결 여부

 

우선 탐색에는 2가지 정도가 있어.

1. 깊이우선탐색(Depth First Search) DFS

2. 너비우선탐색(Breadth First Search) BFS

 

이렇게 2가지가 있는데 비교는 이제부터 할거야

 

1. 깊이우선탐색

 

깊이부터 가자

갈수 있을 때까지 계속 가다가 막혀있으면 가장 가까운 갈림길로

돌아가 이전에 선택했던 길이 아닌 다른길로 들어가서

또 갈때까지 가고 다시 갈림길오고를 전체를 탐색할 떄 까지 반복한다.

 

중복방문하면 손해니까 방문했으면 방문했다는 표시를 남겨야겠지?

 

이런식으로 탐색하는거야 뭔느낌인지 알겠지? 근데 처음에 b와 c 둘다 있는데 뭘선택해야하냐고?

값이 작은거를 먼저 선택하는게 대다수야.

뭐 큰거선택할 수 있지만 그건 뭐 그래프 탐색마다 다를 수 있어

그러나 모든 정점을 탐색하는 것은 변함없어.

 

인접행렬로 깊이우선탐색을 구현한다면

 

 

reset을 시키고 즉 값을 넣기전 초기화 하고 진행하는 것처럼

탐색도 아무곳도 방문하지 않은것처럼 초기화 시키고 방문을 시작하는거야 알았지?

또 방문했으면 저렇게 visited 가 1로 바뀌지? 방문을 한거야 다시 방문하면 손해인거야.

 

연결리스트로도 깊이우선탐색을 할 수있어.

 

리셋함수는 같고

 

for문만 조금 다르게 쓰는거야

 

 

이제 그다음엔 너비우선탐색을 해보자

얘는 시작점과 가까운 정점을 순서대로 방문하는거야. 뭐 예를 들자면 1만큼 가까운애들이 끝나면 그 후 2만큼 가까운 애들, 3,4, 이런식으로 가까운애들부터 탐색하는거지

 

근데 얘는 좀 다르게 큐를 사용해서 구현해

 

 

 

코드는 이런식으로 짤 수 있지, 근데 큐야 큐 다른게아니라 큐큐큐큐

 

정점들,, 노드들에 방문될 때 마다 큐에 인접 정점을 삽입하고, 더 이상 방문할 인접 정점이 없으면 

지금 큐에 정점들 들어가있을거아냐?

맨앞부터 정점을 꺼내서 또 방문하는거지  이 때도 방문하면서 인접 정점을 삽입하는 것은 동일하고. 그리고 공백상태가 될 때까지 반복하는거야. 그러면 탐색이 끝나는거지

 

물론 얘도 연결리스트로 구현 가능한데,,, 그건 귀찮아서 하지 않기로 했어 ㅎㅎ 그리고 조금만 고치면 되는 거라 혼자서도 가능!! 물론 난 안 가능