# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. 신장트리 Spanning Tree 그래프 내의 모든 정점을 포함하는 트리 단, 아래의 3가지 조건을 모두 만족해야 한다. 모든 정점들이 연결되어 있어야 한다. 사이클 cycle 을 포함하면 안된다. 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결한다. 신장트리는 깊이우선 탐색 또는 너비우선 탐색을 하면서 사용된 간선만 모으면 만들 수 있다. 즉, 신장트리는 그래프의 최소 연결 부분 그래프가 된다. 이러한 신장트리는 통신망 네트워크 구축 등에 사용된다. 통신망, 도로망, 유통망 등은 간선에 가중치가 부여된 네트워크이다. 이를 가장 적은 비용으로..

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. 깊이우선 탐색 Depth First Search: DFS 시작 정점에서 한 방향으로 직진하다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 것 0. 알고리즘 그래프의 시작 정점에서 출발 ==> 시작정점 = v 정점 v 방문했다고 표시 정점 v의 인접정점 집합에 대해서 ( u ∈ 인접정점 집합 ) 정점 u를 아직 방문안했으면 시작정점을 u로 설정해서 위의 과정 다시 수행 만약 인접정점 집합이 공집합이면 리턴 depth_first_search(v): v를 방문했다고 표시 for all u in (v의 인접정점..