# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. 최단경로 Shortest Path 그래프에서 정점 i와 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로 최단경로를 찾는 알고리즘 Dijkstra 알고리즘 하나의 시작정점에서 다른 정점까지의 최단 경로를 구함 Floyd 알고리즘 모든 정점에서 다른 모든 정점까지의 최단 경로를 구함 최단 경로 VS 최소비용트리 최소 비용 트리 최소의 비용으로 모든 점을 다 연결할 때 사용한다. 모든 점을 다 이은 경로가 최단 거리라고 말할 수 있지만, 임의의 두 점 간의 거리가 최단 거리라는 보장은 없다 최단 경로 임의의 두 점 간의 최단 거리 구할 때 사용한..

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. Prim의 MST 알고리즘 시작 정점에서 출발하여 신장 트리 집합을 단계적으로 확장해 나가는 방법으로, 이전 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택한다. 아래의 그래프를 이용해 이해하며 위의 정의를 곱씹어 본다. 시작 정점을 0으로 두자. ==> 신장트리 집합: { 0 } 0의 인접 정점 중 최소 간선을 선택하자. ==> 신장트리 집합: { 0, 5 } 이 상태에서 신장트리 집합에 인접(*)한 정점을 살펴보면, 1과 4가 있다. 간선 (0,1)과 (5,4)의 가중치를 비교해보면 (5,4)가 27로서 (0,1..

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. Kruskal의 MST 알고리즘 이 알고리즘은 탐욕적인 방법을 사용해 최소 비용 신장 트리를 알아낸다. 탐욕적인 방법이란, 선택할 때마다 그 순간에 가장 좋다고 판단되는 것을 선택하는 방법이다. *탐욕적인 방법 = 그리디 알고리즘 = greedy method 하지만, 항상 최적의 결론을 내리는가에 대한 검증이 필요한데, 크루스칼 알고리즘은 최적의 해답을 주는 것으로 증명이 되어 있어서 이 부분은 신경쓰지 않아도 된다. 크루스칼 알고리즘을 사용하는 이유는 최소 비용 신장 트리(MST)를 알아내기 위함이다. 최소비용신장트리가 되기 위해 필수적으로 만족해야 하는 ..

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

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. 너비우선탐색 Breath First Search : BFS 시작 정점으로부터 가장 가까운 정점을 먼저 방문하고 차차 멀리 떨어져있는 정점을 방문한다. 다시 말해서, 가까운 거리에 있는 정점들을 차례로 저장한 후 넣은 순서대로 꺼내서 방문하는 방식이다. 이를 위해서, 자료구조 Queue 큐를 사용한다. #알고리즘 breath_first_search(v): v를 방문했다고 표시 큐 Queue에 정점 v를 삽입 while (Queue가 공백이 아니면) do w front = q->rear = 0; } // 공백 상태 검출 함수 int is_empty(QueueTy..

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