자료구조 - 비순환 방향 그래프 (DAG, Directed Acyclic Graph)
1. 비순환 방향 그래프란? 비순환 방향 그래프(DAG, Directed Acyclic Graph)란 순환을 가지지 않는 방향그래프를 말한다. 일반적으로 우선순위를 가진 일련의 작업들은 DAG구조를 가진다. 1) 선행자(predecessor), 후행자(successor) DAG에서 어떤 정점 vi, vj에 대해서 vi에서 vj로의 경로가 존재하면, vi, vj의 선행자(predecessor), vj는 vi의 후행자(successor)라고 한다. 2) 즉각 선행자(immediate predecessor), 즉각 후행자(immediate successor) DAG에서 어떤 정점 vi, vj에 대해서 vi에서 vj로의 간선이 존재하면, vi를 vj의 즉각 선행자(immediate predecessor), vj..
2021. 2. 2.
자료구조 - 그래프
1. 그래프란? 그래프(Graph)는 현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화 하여 표현한 것이다. 수학정 정의 : 정점 집합 V = {v1, v2, v2, ..., vn} 이고, 정점간의 연결 관계들을 나타내는 간선 집합 E = {(vi, vj)/vi ∈ V, vj ∈ V} ⊆ V x V 일 때, 그래프 G = (V, E) 이다. 2. 그래프 용어 1) 무향 간선 (Undirected Edge) - 정점을 연결하는 간선에 방향이 존재하지 않는다. - 임의의 간선 (vi, vj)에 대해서 (vi, vj) = (vj, vi)이다. 2) 유향 간선 (Directed Edge) - 정점을 연결하는 간선에 방향이 존재한다. - 임의의 간선 (vi, vj)에 대해서 (vi, vj) ≠ (v..
2021. 2. 2.
