그래프(Graph)란?

그래프는 여러 노드(정점)들이 간선으로 연결된 자료 구조입니다.

그래프는 네트워크 구조를 모델링하는 데 매우 유용하며, 다양한 현실 세계 문제를 해결하는 데 사용됩니다.

예를 들어, 소셜 네트워크, 컴퓨터 네트워크, 도로망 등이 그래프로 표현될 수 있습니다.

1. 노드(Node) / 정점(Vertex):

   • 그래프의 기본 요소로, 위치를 나타냅니다.

   • 예: 도시, 지점, 컴퓨터 네트워크의 개별 컴퓨터 등.

2. 간선(Edge):

   • 두 노드를 연결하는 선입니다.

   • 간선은 '무방향'(양 노드 사이를 양방향으로 이동할 수 있음) 또는 '방향성'(한 방향으로만 이동 가능)이 있을 수 있습니다.

3. 가중치(Weight) / 비용(Cost):

   • 간선에 할당된 '가중치'는 두 노드 간의 이동 비용이나 거리 등을 나타냅니다.

   • 모든 간선에 가중치가 있어야 하는 것은 아닙니다.

4. 인접리스트(Adjacency List):

   • 각 노드에 연결된 다른 노드의 목록을 저장하는 방식입니다.

   • 메모리 효율적이며, 특정 노드에 직접 연결된 노드를 찾는 데 유용합니다.

5. 인접행렬(Adjacency Matrix):

   • 2차원 배열을 사용해 노드 간의 연결 관계를 나타냅니다.

   • 노드 간의 연결 여부를 빠르게 확인할 수 있지만, 메모리를 더 많이 사용합니다.

6. 방향 그래프(Directed Graph):

   • 간선에 방향성이 있는 그래프입니다.

   • 예: 웹 페이지 간의 링크, 일방통행 도로.

7. 무방향 그래프(Undirected Graph):

   • 간선에 방향성이 없는 그래프입니다.

   • 예: 페이스북의 친구 관계, 양방향 도로.

8. 사이클(Cycle):

   • 노드들이 순환하여 연결된 구조입니다.

   • 사이클이 없는 그래프를 '비순환 그래프'라고 합니다.

9. 연결(Connected):

   • 그래프 내의 모든 노드가 서로 직접적이거나 간접적으로 연결되어 있을 때, 그 그래프는 '연결 그래프'라고 합니다.

   • 만약 어떤 노드에서 시작해 다른 모든 노드에 도달할 수 있다면, 그 그래프는 완전히 연결되어 있다고 할 수 있습니다.

10. 트리(Tree):

    • 사이클이 없는 연결 그래프입니다.

    • 모든 트리는 그래프이지만, 모든 그래프가 트리는 아닙니다.

    • 트리는 계층적인 구조를 나타내는 데 자주 사용됩니다.