vertices(정점)
= node
여러 가지 특성을 가질 수 있는 객체
V(G): 그래프
G
의 정점들의 집합
edge(간선)
= link
정점들 간의 관계
E(G): 그래프
G
의 간선들의 집합
Graph | Tree | |
---|---|---|
방향성 | 방향, 무방향 | 방향 |
순환 | 가능 | 불가능 |
루트 노드 | 루트 노드의 개념이 없음 | 한 개의 루트 노드만 존재 |
부모-자식 | 부모-자식의 개념이 없음 | 부모-자식 관계 |
모델 | 네트워크 모델 | 계층 모델 |
순회 | DFS, BFS | DFS, BFS 안의 Pre-, In-, Post-order |
간선의 수 | 그래프의 따라 다름 | 노드가 N 인 트리는 항상 N-1 의 간선을 가짐 |
s
부터 e
까지의 경로= Network
n
개의 정점을 가진 무방향 완전그래프의 간선의 수: n * (n - 1) / 2
i
, j
)가 그래프에 존재하면 M[i][j] = 1
,M[i][j] = 0
으로 표현한다.0 | 1 | 1 | 1 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
1 | 0 | 1 | 0 |
0 → 1 → 2 → 3
1 → 1 → 2
2 → 0 → 1 → 3
3 → 0 → 2