[n532] Graph

그래프 기본 개념

• 노드들이 서로 연결되어 루프 구조를 띌 수 있다. 
• 그래프와 트리의 쓰임은 다소 다르다. 예를 들어, 그래프는 object간의 관계성을 표현할 때 쓰인다. 
• 트리는 계층을 표현할 때 유용하다. 하지만, 그래프는 계층 개념이 존재하지 않는다. 

 

Directed Graph

• 그래프가 한 쪽 방향으로 흐르는 그래프를 의미한다. 
• 방향에 따라 흐르기 때문에 순서가 있고, 마지막 노르 (Leaf Node)가 존재한다. 
• 아래 그림은 Directed graph이고, 이 화살표가 양방향일 경우는 Bidirectional Graph(양방향 그래프)이다. 

 

Undirected Graph

• 무방향성이지만 인접한 노드끼리 서로 상호 교환 관계이다. 

Cyclic and Acyclic Graphs

• Cyclic graph : 순환하는 루프를 형성하는 그래프이다.
  • Undirected graph는 Cyclic graph 이다.
• Acyclic graph : 순환하지 않는 구조의 그래프이다.

 

Weighted Graphs (가중 그래프)

• 각 edge마다 할당된 가중치 값이 있다. 
• 가중치가 높을 수록 비용(시간)이 길어진다.

 

Directed Acyclic Graphs (DAGs)

• 방향성 비순환 그래프라고 한다. 
• 순환 구조 없이 특정 방향으로 흐른다. 

인접 행렬 (Adjacency Matrices)와 인접 리스트 (Adjacency Lists)

그래프 내에서 각 노드 사이의 연결 관계를 표현할 때 사용한다.

 

 

순회 (Traversal)

• 트리 또는 그래프에서 한번씩 모든 노드를 탐색하는 것을 순회(Traversal)이라 한다.
• 그래프의 순회 : DFS(깊이 우선 탐색), BFS(너비 우선 탐색)
• 트리의 순회 : 전위 (Preorder), 중위(Inorder), 후위(Postorder) 순회이다.