[자료구조] 01. 그래프

DFS, BFS에 대한 이야기를 하려다 어쩌다보니 그래프를 작성하게 되었다.. 안좋을 점은 없으니까.. 블로그에 남겨두고 간다...

그래프 란?

 

그래프

💡그래프: 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조

 

그래프의 구조

두 점 사이에 이어지는 그림의 갈색 선은 두 점이 직접적인 관계라는 것을 표현해준다. 그렇다면, 몇 개의 점과 선에 걸쳐 이어진 두 점은 간접적인 관계에 있다고 표현할 수 있다. 하나의 점을 그래프에서는 정점(vertex)이라 표현하고, 그림의 갈색 선을 간선(edge)이라고 부른다. 두 정점이 간선으로 이어져 있다면 이 두 정점은 인접한다고 이야기한다.

그래프의 종류

그래프의 종류에는 그림처럼 3가지의 종류가 있다.

• 간선에 대한 값이 정해지지 않고 양방향인 "비가중치 무향 그래프"
• 간선에 대해 값이 있으며 양방향인 "가중치 무향 그래프"
• 간선에 대한 값이 있으며 방향을 정할 수 있는 "가중치 유향 그래프"

A에서 C로 갈 경우의 비용을 구하라는 문제가 나온다면 밑 그림을 참고하여 A와 C를 이어주는 간선을 확인하고 그에 대한 가중치를 확인하면 된다. 따라서 A에서 C로 이동할 경우 드는 비용은 2일 것이다.

그래프의 표현 방식

이 그래프를 표현하는 방식은 2가지가 있다. 인접 행렬, 인접리스트. 이 두가지로 그래프를 표현할 수 있는데, 대게 인접 행렬일 경우 2차원 배열로 표현하고 인접 리스트일 경우 ArratList로 표현하고 있다.

 

인접 행렬

인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열로 표현한다. A와 B 정점이 이어져 있다면 값을 1(true), 이어져 있지 않다면 0(false)로 표시한다. 만약 가중치가 표시되어 있다면, 가중치를 값에 넣어주면 된다. 위 그림을 예제로 인접행렬을 나타낸다면

int[][] graph = new int[3][3];
graph[0][1] = 1; // A -> C
graph[1][0] = 1; // B -> A
graph[1][2] = 1; // B -> C
graph[2][0] = 1; // C -> A

for(int[] row : graph){
  for(int value : row){
     System.out.print(value + " ");
   }
  System.out.println();
}
// 출력
0 1 0 
1 0 1 
1 0 0

이런 식으로 표현할 수 있다.

 

인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접하는 지를 리스트의 형태로 표현한다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.

 

// ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); // 이런식으로도 표현 가능
ArrayList<Integer>[] graph = new ArrayList[3];
for(int i = 0; i < graph.length; i++) graph[i] = new ArrayList<>();

graph[0].add(2); // A->C
graph[1].add(0); // B->A
graph[1].add(2); // B->C
graph[2].add(0); // C->A
int index = 0;
for(ArrayList<Integer> list : graph){
    System.out.print(index++  + " ");
    for(int value : list){
        System.out.print(value + " ");
    }
    System.out.println();
}

ArrayList 타입의 배열로 나타낼 수 있으며 ArrayList 안에 ArrayList를 담아서 표현할 수도 있다.

 

기타 그래프 용어

• 정점(vertax): 노드라고도 부르며 데이터가 저장되는 그래프의 기본원소
• 간선(edge): 정점 간의 관계를 나타낸다.
• 인접 정점(adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻한다.
• 가중치 그래프(weighted Graph): 연결의 강도(추가적인 정보)가 얼마나 되는지 적혀있는 그래프
• 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프
• 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지
• 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다.
• 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현한다. 다른 정점을 거치지 않는다는 것이 특징이다.
• 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다.