그래프(Graph) 란?

그래프란?

• 노드 간에 연결될 수 있다는 점을 제외하고는 트리와 비슷하며, 루프를 형성할 수도 있다.
• 트리에서는 노드를 탐색하는 경우 제한이 있지만, 그래프는 루프 형성이 가능하기 때문에 다른 범위의 개념으로 필요한 자료구조이다.
• 예를 들어, object간의 관계를 표현을 할 때 유용하다.(SNS, 도로 상의 차량 검색, 운송 시스템)

그래프는 기본적으로 위 그림처럼 vert(노드 또는 정점)와 edge(간선)으로 연결되어있다.

그래프와 트리의 특징

• 그래프는 노드간의 관계, 트리는 노드간의 계층을 표현한다.
• 그래프와 트리는 서로 다른 개념이라는 것을 알아야 한다.
  • 트리에는 그래프에는 없는 계층개념이 있기 때문이다.
  • 도식화해서 상세히 둘의 관계를 확인해 보자.

그래프의 유형

• 그래프의 특성은 directed(방향성) 또는 undirected(무방향성) 그래프가 있다.
• 그래프가 "한쪽 방향(one-way)"으로 설명될 수 있다면 directed 그래프가 가장 적합하다.

• 방향성그래프는 보는 것처럼 순서가 있으므로 마지막 노드(리프, leaf)가 있다. 위 그림에서는 'F'가 리프노드이다.

• 위처럼 Directed 그래프는 **bidirectional(양방향)**가 될 수도 있다.
  • 예를 들어 모든 도로가 일방 통행이기 때문에 도로 지도는 방향이 지정되지만, 대부분의 거리는 양방향 도로로 구성된다.
• 그래프에서 노드 연결 관계의 목적이 상호 교환이라면, undirected 그래프가 가장 적합하다.
• "교환"관계는 항상 상호이므로 undirected 그래프가 여기에서 가장 의미가 있다.
  • 여기서 상호 교환이란? : 화살표로 연결된 노드들이 서로 노드 정보를 공유하는 것

• 위처럼 무방향성은 방향(화살표)이 따로 지정되어있지 않다.
• 간선으로 연결된 노드들끼리는 서로 인접(adjacent)해있다고 하며, 이웃(neighbor)라고 칭한다.

Cyclic and Acyclic Graphs(순환 및 비순환 그래프)

• 순환(루프)을 형성할 수 있는 경우(예 : 방문한 노드에 다시 방문) 그래프는 순환 그래프이다.
  • 예를 들어 아래 이미지에서 B에서 시작한 다음 가장자리를 따라 C, E, D로 이동한 다음 B(이미 방문한 노드)로 돌아갈 수 있다.

• 참고 : undirected 그래프는 항상 동일한 노드에 재방문할 수 있으므로 순환 그래프이다.
• 순환을 형성할 수 없는 경우(예 : 모서리를 따라 이미 방문한 노드에 방문할 수 없음) 비순환 그래프라고 한다.

Weighted Graphs(가중 그래프) - 실 사례에서 가장 많이 사용

🔍 자세히 보기 : **가중 그래프에는 edge(간선)**와 관련된 값이 있다.

• 각 edge의 가중치에 할당된 특정 값을 호출한다.
• 가중치는 서로 다른 그래프에서 서로 다른 데이터를 나타낸다.
• 예를 들어, 도로 구간을 나타내는 그래프에서 가중치는 도로의 길이를 나타낼 수 있다.
• 그래프에서 **경로의 총 가중치가 높을수록 경로 이동 시간(비용)**이 길어진다.
  • 가중치는 모든 경로 비교 시, 어떤 경로를 선택할 지에 사용된다.

• 순회(Traversal)는 그래프에 연결된 노드를 탐색한다.
• 중요한 것은 아직 방문하지 않은 노드의 순회 순서이다.
• 순회 개념은 향후 배우게 되는 DFS, BFS와 같은 순회 알고리즘과 연관되어 있다.

Directed Acyclic Graphs (DAGs)

• 방향성 비순환 그래프(DAG)는 순환되지 않고 특정한 단방향 그래프이다.
• 즉, 아래 그림처럼 edge가 순서대로 향하도록 DAG의 노드를 선형(단방향)으로 정렬할 수 있다.

📚 Reference

• 그래프와 트리의 관계에 대한 고찰
• 그래프에 대한 문제해결