[Data Structure] Graph

🎯 목표 : 그래프 자료구조와 활용의 이해

📒 Graph

📌 그래프의 특징과 구조

• 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
• 여러개의 정점(Vertex)와  간선(Edge)들의 집합으로 구성된다.
• 직접적인 관계라면 두 정점에 간선이 존재한다.
• 간접적인 관계라면 두 정점 사이에 여러개의 정점과 간선이 존재한다.

---

📌 그래프의 용어 정리

• 정점(Vertex)
  • 노드라고도 하며 데이터가 저장되는 그래프의 기본 원소
• 간선(Edge)
  • 정점을 이어주는 선
• 인접정점(Adjacent Vertex)
  • 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
• 가중치 그래프(Weighted Graph)
  • 연결의 강도(추가적인 정보 등)가 적혀있는 그래프, 비 가중치 그래프는 반댓말.
• 무방향 그래프(Undirected Graph)
  • 두 정점을 연결하는 간선에 방향이 없으며 양방향으로 이동 가능하다. 정점 A, B가 있다면 (A,B)로 표현한다.
• 방향 그래프(Directed Graph)
  • 두 정점을 연결하는 간선에 방향이 존재하며 간선의 방향으로만 이동 할수 있다. 정점 A,B가 있다면 <A,B>로 표현한다.
• 진입차수(In-degree) / 진출차수(Out-degree)
  • 한 정점에서 들어오는 간선하고 나가는 간선이 몇 개인지를 나타낸다.
• 인접(Adjacency)
  • 두 정점 간에 간선이 직접 이어져 있다면 두 정점은 인접한 정점이다.
• 자기 루프(Self Loop)
  • 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 표현한다. 다른 정점을 거치지 않는다.
• 사이클(Cycle)
  • 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다.

---

📌 그래프의 표현

• 인접 행렬 은 A정점과 B정점이 서로 이어져 있다면 1 이어져 있지 않다면 0으로 표현한 행렬표다.
• 가중치 그래프라면 1 대신 다른 데이터를 저장한다.
• 두 정점 사이에 관계가 있는지 없는지 확인하기에 용이하다. 예를 들어 진출 간선이 있는지 행렬표로 바로 확인이 가능하다.
• 가장 빠른 경로를 찾고자 할때 주로 사용된다.
• 하지만, 간선의 수와 무관하게 항상 2차원 배열이 필요하므로 메모리 공간이 낭비된다.
• 그리고, 그래프의 모든 간선의 수를 알아내려면 인접 행렬 전체를 확인해야 하므로 많은 시간이 소요된다.
• 인접 리스트 는 각 정점이 어떤 정점과 인접하는지를 리스트 형태로 표현한다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점의 데이터를 가지고있다.
• 존재하는 간선만 관리하면 되므로 메모리 사용 측면에서 보다 효율적이다.
• 모든 간선의 수를 알아내려면 각 정점의 헤더 노드부터 모든 인접 리스트를 탐색하면 되므로 인접 행렬보다 적은 시간이 소요된다.
• 하지만 두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 인접 리스트를 탐색해야 하므로 정점의 차수만큼 시간이 필요하며, 비교적 구현이 어렵다.

• 위 그림에서 방향 그래프를 인접 행렬과 리스트로 표현하게 되면 아래와 같다.

• 위 그림에서 무방향 그래프를 인접 행렬과 리스트로 표현하게 되면 아래와 같다.

---

📌 그래프의 구현

• 개념 정리는 블로깅으로 마무리하고,
• 다음 블로깅에서는 인접 행렬과 리스트를 구현해 보고 위 그림의 그래프의 행렬과 리스트를 출력해 보는 프로그램을 작성할 것이다.