728x90 Algorithm/알고리즘 기본27 [Algorithm] Kruskal Kruskal MST를 만드는 알고리즘 입니다. 적은 비용으로 노드를 연결하는 것이 핵심입니다. Kruskal 알고리즘을 구현하기전 MST 를 알아야 합니다. 맨아래 링크를 참조해주시면 됩니다. 알고리즘 순서 에지들을 오름 차순으로 정렬한다. 에지들을 그 순서대로 하나씩 택한다. 싸이클 검사를 한다. 선택된 에지의 수가 n-1 개의 에지가 선택되면 종료한다. 눈으로 한번 보면 편합니다. 싸이클을 검사하는 방법 위에서 싸이클이 생겼을때 우리는 선택된 엣지를 추가 하지 않고 그냥 넘어 갔습니다. 집합을 사용하여 어떻게 싸이클을 검사하는지 파악해 보겠습니다. 처음 모든 노드들을 집합으로 만듭니다. {A} {B} {C} {D} {E} {F} {G} {H} {I} 집합에 선택된 노드를 넣어 준다. 선택한 간선을 .. 2021. 8. 11. [Algorithm] MST(Minimum Spanning Tree) MST 란? Minimum Spanning Tree 최소 신장 트리이다. 간선의 가중치를 고려 하여 최소 Spanning Tree 를 만든다. 싸이클이 없는 연결된 무방향 그래프를 트리 라고 한다. 모든 정점들이 연결이 되어 있어야 된다. 가중치의 합이 최소가 되어야 한다. 해가 유일하진 않다. - 최소 비용을 찾는 트리이기 때문에 동일한 가중치의 간선이 있을경우 해가 여러개가 될수 있다. Kruskal 알고리즘, Prim 알고리즘 이 있다. MST를 들어가기전에 Spanning Tree 를 알고가야한다. Spanning Tree 신장트리라고 한다. 그래프의 모든 정점을 가지는 트리이다. 특징 트리의 특징은 모두 포함된다. 하나의 그래프는 여러 Spanning Tree 를 가질 수 있다. 그림설명 MST.. 2021. 8. 10. [Algorithm] DAG(Directed Acyclic Graph) DAG 란? Directed Acyclic Graph 방향을 가지지만 순환이 없는 방향 그래프이다. 왼쪽에서 오른쪽 방향으로 이동한다. 용어 그래프에서 사용하는 용어들이있다. Indgree: 타겟노드에 들어오는 엣지의수 Outdgree: 타겟노드에서 나가는 엣지의수 Incomming: 들어오는 엣지 Outcomming: 나가는 엣지 비 순환이란? A 노드에서 출발했다면 A 노드로 다시 돌아오는 일이 없어야 한다. 위상정렬 DAG 에서 노드들의 순서화 단 모든 Edge(Vi,Vj)에 대해서 i 2021. 8. 3. [Algorithm] Graph Traversal BFS, DFS Graph Traversal 그래프를 순회 해본다. 순회방식 BFS: 너비 우선 탐색 DFS: 깊이 우선 탐색 BFS 구현 BFS 는 queue 를 이용 하면된다. 1. 처음 방문할 노드를 택한다. 2. 방문한 노드를 큐에 넣는다. 3. 큐에서 꺼내고 방문 했다고 체크 한다. 4. 방문한 노드에 인접한 노드를 큐에 넣어준다. 5. 2~4 까지 queue 가 비워질때 까지 반복한다. 코드 public void graphTraversalBFS(ArrayList graph, int startNode) { ArrayList checkVisit = new ArrayList(); Queue queue = new LinkedList(); queue.add(startNode); while(!queue.isEmpty().. 2021. 7. 22. 이전 1 2 3 4 5 6 7 다음 728x90 반응형
