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

탐색을 배웠는데, 이제 탐색도 응용해봐야 하는데 이게 좀 중요한 내용이다. 

연결 성분이라는 것인데 connected component 라고 한다. 최대로 연결된 부분 그래프를 말한다.

 

연결성분을 찾기 위해서는 앞에서 배웠던 깊이, 너비 우선 탐색을 모두 이용할 수 있는데 상관없다.

그렇지만 예를 들어서 깊이 우선 탐색을 해보자

 

먼저 임의의 정점을 선택, 깊이우선탐색을 통해 연결되어 있는 모든 정점을 출력한다. 더 이상 연결된 정점이 없으면 그래프에서 아직 방문되지 않은 다른 정점을 선택해 반복한다. 이 과정을 그래프의 모든 정점이 방문될 때 까지 방문하면 모든 연결 성분을 찾을 수 있다.

 

연결 성분 탐색을 위해서는 각 정점마다  저런식으로 111 22 이렇게 저장하려면

저러한 번호를 저장할 공간이 필요한데

 

이걸 label이라고 보통한다. 그리고 배열로 선언해가지고

저렇게 111로 넣어주고 22로 넣어주고 이름을 붙혀준다.

 

 

 

그렇다면 정점을 방문하면서 각 정점에다 저렇게 이름붙이는 함수를 구현해보자

 

코드보면서 익히자.

 

 

 

 

 

결과는 이렇게 나옵디다.

 

또한 이제 신장트리를 배워볼건데 (spanning tree) 라고 하는데

이런데 쓰이곤 한다네..?

 

–최소의 링크를 사용하는 네트워크 구축 시 사용

(통신망, 도로망, 유통망 등)

 

얘는 좀 특이한 애야 신장트리란게 그래프 내의 모든 정점을 포함하는 트리인데

신장 트리도 트리의 일종이긴 한데 조건이 있어

 

 

1. 모든 정점들이 연결되어야 함

2. 사이클이 없어야함. 그니까 방문했던 노드를 또 방문하게 될 일이 있어선 안됨

3. n개의 정점을 n-1개의 간선으로 연결해야함.

 

저 조건만 만족하면 신장트리가 되는데, 신장트리가 다양하게 만들어질 수 있겠다.

 

이렇게 방문할 때는 탐색을 쓰는데 깊이든 너비든 둘 다 쓸 수 있다.

 

깊이도 너비도 똑같은 애들 방문안하고

쓸데없는 그런 간선 없잖아 ㅎㅎ

 

그래서 신장트리를 탐색으로도 구현할 수 있다. 이 말이지

 

그건 알아서 코드 짜보도록하자 ㅎㅎ

 

 

 

그리고 이제 진짜 마지막 위상 정렬

topological sort라고도 하는데

 

 

왜 정렬을 배우냐고??

 

지금까지 사용된 그래프의 특성을 정말 잘 이용하기 때문이야.

 

어떻게 정렬하냐고??

방향 그래프에서 존재하는 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열시키는 거야

 

말로 설명할게

1. 우선 진입차수가 0인 정점을 선택해(0이면 아무거나 괜찮아)

2. 선택된 정점과 여기에 부착된 모든 간선을 삭제해(그림 b를 보면 알 수 있지?)

3. 삭제되는 간선과 연결된 남아있는 정점들의 진입차수를 변경해(또 0이 있는지 알아보는거지)

4. 반복

 

얘도 순서가 여러개가 될 수 있겠습니다ㅎㅎㅎ 

이렇게 2개 같은 것입니다.ㅎㅎㅎ

 

얘는 그림으로 알아보는게 훨씬 편하고 좋아

코드는 복잡해 ㅠㅠ

 

오늘은 여기까지...