When to use get MST of undirected & weighted Graph Idea maintain two sets of vertices (1: MST, 2: not visited) find cut vertex minimum weight in each loop until all vertices be included in MST 📝 cut vertex: connect vertex which connects two disjoint subsets Algorithm (1) Create key-value table (vertex - weight) , empty MST Set (2) initialize first value of key as '0' to visit first, remain key a..
graph
🔒 문제 💭 생각의 흐름 MST (Minimum Spanning Tree) + Undirected Graph => 2가지 방법! Kruskcal Prim✔️ mstSet: 방문된 MST 원소의 집합 not visited Set: 아직 방문하지 않은 노드 번호 - 비용 집합 find minimum cut vertex : mstSet과 not visited Set을 최소 비용으로 연결하는 노드 찾기 mstSet -> 어차피 weight의 총합을 구하는 것이므로 방문 순서를 저장할 필요가 없겠다 -> unorderd_set not visited Set -> 배열로 생성시 따로 visited Boolean 배열이 필요하므로 map 자료구조 사용 ⭐ find minimum cut vertex -> not vist..
개요 MST (Minimum Spanning Tree)를 구하는 알고리즘 what's MST? 모든 노드(Vertex)를 최소 비용으로 최소 간선(Edge)을 사용해 연결한 트리 (no cycle) * MST의 Edge수는 Number Of Vertex - 1 이다. Where to use MST? Network Design Approximation algorithms (ex. traveling salesperson problem) When to use Kruskal Get MST of undirected graph by Greedy algorithm Algorithm (1) Sort all edges in ordering by weight (ascending) => 최소 비용 간선 오름차순 (2) Pi..
🔒 문제 💭 생각의 흐름 문제를 푸는 입장에서 유형을 보지 않을 수가 없는데 조건: 'directed graph' + can connect itself ∴ Union-Find 알고리즘을 사용하기 어렵다. 총 2가지 방식으로 풀이할 수 있겠다. Topological Sort using BFS (Kahn's Algorithm) 풀이 DFS 변형 풀이 여기선 2번 방법을 선택해서 풀이해보겠다. DFS 변형 풀이법의 핵심은 다음과 같다. 전형적인 DFS 코드를 쓰되, 부모 노드 Set(지나온 부모 노드 방문여부)을 Keep 한다! DFS 를 재귀적으로 호출하면서 이전 스택으로 되돌아 가기 직전에 방문처리 되지 않은 상태로 되돌리기 위해 (부모 노드 Set 업데이트) 부모 노드 방문을 취소한다. bool dfsD..
이론 정리한지 1년이 넘어서 풀어보는 예제 🔒 문제 위상 정렬 순서에 맞는 answer vector를 리턴하라. 🔑 풀이 class Solution{ public: vector topoSort(int V, vector adj[]) { int * indegree = new int[V]{0}; std::vector answer; // initialize indegree array for (int i = 0; i < V; i++) { for (const auto& adjacentVertex : adj[i]) { indegree[adjacentVertex]++; } } std::queue queue; // indegree 0 찾고 넣기 for (int i = 0; i < V; i++) { if(indegree[..
🔒 문제 Detect cycle in an undirected graph | Practice | GeeksforGeeks practice.geeksforgeeks.org 💭 생각의 흐름 일단 문제 자체에서 DFS를 사용하여 사이클을 탐색하라고 했다. 정석적인 DFS recursive function을 작성하고 사이클 생기는 시점에 true만 리턴하면 된다고 생각했다. Q. 사이클이 생기는 시점이 언제인가? A. BackEdge (부모노드 이외의 노드에 연결되는 선이 발견되는 시점) 따라서 visited (방문 기록) 배열을 두고 visited 상에 방문된 상태로 기록되있으면서 parent 노드가 아닌 노드로 연결되있을 경우 바로 true (사이클이 존재)를 리턴하도록 한다. ⚠️ 실수 아래 그림 처럼 그..
