DNF LOVE

[Tree] 트리란? 사이클이 존재하지 않은 연결 그래프다. 정점의 수 N에 대해 간선의 수는 항상 N-1이다. 두 노드 사이의 경로는 하나밖에 존재하지 않는다. 1. Spanning Tree(신장 트리) : 어떤 연결 그래프 G(V, E)에서 최소한의 간선만을 선택해 연결그래프인 트리를 만든 것을 의미한다. 연결성은 유지한 채 그래프를 경량화 할 수 있다. 최소 연결 = 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에..

1. SCC(Strogly connected component) - 방향 그래프의 순환 단방향 그래프의 서로 다른 두 노드 U, V쌍에 대해 U -> V에 대한 경로가 존재하고, 동시에 V -> U에 대한 경로가 존재한다면 두 노드를 같은 SCC에 속한다고 정의한다. 2. BCC(Bi-connected component) - 무방향 그래프의 순환 무방향 그래프의 서로 다른 두 노드 U, V쌍에 대하여 단결점 없는 경로가 존재하는 경우 두 노드를 같은 BCC에 속한다고 정의한다.

이전 포스터에서 자료구조를 선형, 비선형 구조로 구분하여 각 자료구조 별 특징을 나눠봤다. B로만 갈 수 있는 간선은 로 표시한다. 무방향 그래프와 다르게 로 나타낼 수 없다. 즉, 는 다른 의미다. 6. 가중치 그래프 : 간선에 비용이나 가중치가 할당된 그래프이다. 7. 순환 그래프 : 단순 경로의 시작 정점과 종료 정점이 동일한 그래프이다. 8. 비순환 그래프 : 사이클이 없는 그래프이다. [Tree] 트리란? 사이클이 존재하지 않은 연결 그래프다. 정점의 수 N에 대해 간선의 수는 항상 N-1이다. 두 노드 사이의 경로는 하나밖에 존재하지 않는다.