[자료구조 & 알고리즘] 7. 그래프, 인접 행렬, 인접 리스트, 암시적 그래프

그래프, 인접 행렬, 인접 리스트, 암시적 그래프

1. 그래프 (Graph)

• 그래프는 어떤 자료나 개념을 표현하는  정점(Vertex)들의 집합 V와 이들을 연결하는 간선(Edge)들의 집합 E로 구성된 자료구조.
• 트리와 비슷하지만 트리가 그래프의 한 종류임.

     - 트리는 부모 자식 노드라는 계층이 존재하지만, 그래프는 어느 정점이라도 모두 연결 가능.

• 그래프는 그림에 따라 다르게 그려질 수 있지만, 정점들과 그들을 잇는 간선들이 같다면 같은 그래프임.

• 방향 그래프와 무향 그래프

     - 방향 그래프 : 간선에 방향이 정해져 있어 정점 간에 이동이 정해진 방향을 따라서만 이동할 수 있는 그래프.

     - 무향 그래프 : 간선에 방향이 정해지지 않아 간선만 연결되어 있으면 정점 간에 자유롭게 이동이 가능한 그래프.

• 다중 그래프와 단순 그래프

     - 다중 그래프 : 두 정점 간에 연결이 여러 간선으로 이뤄진 그래프.

     - 단순 그래프 : 두 정점 간에 연결이 하나의 간선으로만 이뤄진 그래프.

• 가중치 그래프

     - 간선에 가중치가 있는 그래프.

• 활용

     - 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현

          - 도시들을 연결하는 도로망 : 도시(Vertex), 도로망(Edge)

          - 지하철 연결 노선도 : 정거징(Vertex), 정거장을 연결한 선(Edge)

          - 컴퓨터 네트워크 : 각 컴퓨터와 라우터(Vertex), 라우터 간의 연결 관계(Edge)

          - 소셜 네트워크 분석 : 페이스북의 계정(Vertex), Follow 관계(Edge)

• 구현 방법

     - 인접 행렬, 인접 리스트, 암시적 그래프 등이 있음.

 

2. 인접 행렬 (Adjacency Matrix)

• 각 정점마다 모든 정점과의 연결 여부를 0과 1로 표현하여 행렬로 나타냄.

• 행렬을 나타내기 위해 이중 배열을 사용

int[][] adjMatrix = {
  {0, 0, 1, 0, 1},
  {0, 0, 0, 1, 1},
  {1, 0, 0, 0, 1},
  {0, 1, 0, 0, 1},
  {1, 1, 1, 1, 0}
};

• 무향 그래프의 경우 대각선 ↘ 방향을 기준으로 대칭

• 연결되지 않음을 나타내기 위한 0을 계속 표시하기 때문에 메모리를 비효율적으로 씀.

 

3. 인접 리스트 (Adjacency List)

• 각 정점에 연결된 정점을 리스트로 표현

List<List<Integer>> adjList = new ArrayList<>();
adjList.add(new ArrayList<>(Arrays.asList(3, 5)));
adjList.add(new ArrayList<>(Arrays.asList(4, 5)));
adjList.add(new ArrayList<>(Arrays.asList(1, 5)));
adjList.add(new ArrayList<>(Arrays.asList(2, 5)));
adjList.add(new ArrayList<>(Arrays.asList(1, 2, 3, 4)));

• 원소마다 리스트의 크기가 다르기 때문에 배열은 사용 불가.

• 정점이 숫자라면 인덱스로 표현 가능. 숫자가 아니라 다른 값이라면 key-value 형식의 map도 가능.

 

4. 암시적 그래프 (Implicit Graph)

• 직접 명시적으로 간선을 표현하지 않아도 암시적으로 알 수 있도록 표현.

• 예를 들어, 아래의 그림에서 검은 색은 벽, 흰 색은 길이라고 한다면

     - 한 칸 한 칸을 정점으로 보고, 그 중 흰 색 칸을 서로 엣지로 연결된 정점으로 본다면 그래프로 볼 수 있음.

• 이 경우, 25개의 정점에 대한 모든 간선을 인접 행렬이나 인접 리스트 등으로 일일이 표시하는 것이 아닌, 아래와 같은 이중 배열로 그래프의 모양을 나타내고 간선은 이 그래프의 모양으러 암시적으로 판단.

int[][] implictGraph = {
  {1, 1, 1, 1, 1},
  {0, 0, 0, 1, 1},
  {1, 1, 0, 1, 1},
  {1, 0, 0, 0, 0},
  {1, 1, 1, 1, 1}
};