-
노드와 노드 간 연결(edge)로 구성된 자료 구조이며, object 간의 관계를 표현할 때 유용하게 사용할 수 있다.
트리와는 다르게 계층 구조가 아니며, 루프를 형성할 수 있다.
유형
1. directed(방향성) / undirected(무방향성)
directed - 단방향 혹은 양방향 edge로 구성되어있으며, 순서가 있고, 마지막 노드(leaf)가 있다.
undirected - 모든 edge 가 상호교환이면 방향이 의미가 없으므로, 무방향성 그래프가 된다.
2. cyclic(순환) / acyclic(비순환)
cyclic(순환) - 방문한 노드에 다시 방문하는 것
*undirected 그래프는 항상 동일한 노드에 재방문이 가능하기 때문에 cyclic graph이다.
acyclic - edge의 방향성 때문에 순환을 형성할 수 없는 경우 acyclic graph라고 한다.
3. wighted graph
edge에 할당된 값이 존재하여 여러가지 의미를 내포하는 그래프
4. Directed Acyclic Graph (DAG)
순환되지 않고 특정한 단방향성을 가진 그래프 (선형 형태를 형성한다)
그래프를 표현하는 방법
1. 인접행렬 (adjacency matrices)
각 행에 해당하는 노드가 각 열에 해당하는 노드에 연결되었을 경우, edge의 weight (가중치가 없을 경우 1)을 값으로 갖는 행렬로 그래프를 표현할 수 있다.
adj_matrix = [ [0, 1, 0, 0], [1, 0, 1, 0], [0, 0, 0, 1], [0, 0, 0, 0] ]인접 행렬은 구현하기 쉽지만, matrix만 봐서는 어떤 행,열이 어떤 node와 매치되는지 알 수 없다는 단점이 있다.
2. 인접리스트 (adjacency list)
edge로 연결된 두 node의 관계를 서로 '인접(adjacent)'라고 한다.
인접리스트는 각 노드 별로 연결된 노드를 저장한다. 여기서는 각 노드를 key로, 해당 노드에 연결 된 노드를 value로 갖는 python dictionary로 표현했다.
adj_list = { 'A' : {'B':1}, #숫자는 weight를 뜻한다 'B' : {'C':3, 'A':2}, 'C' : {'D':1}, 'D' : {}, }