[자료구조] JAVA로 그래프(Graph)구현하기, BFS, DFS

 

 

<그래프의 개념>

자료구조의 일종이다.

정점(Node, Vertex)와 간선(Edge)로 이루어져 있으며

간선은 정점간의 관계를 나타내는데 사용한다.

G = (V,E)로 나타낸다.

 

경로 : 한 정점에서 특정 정점으로 이동하는 방법.

사이클 : 경로중에서 시작과 도착이 같은것(되돌아오는것)

 

단순 경로와 단순 사이클 : 같은 정점을 두번이상 방문하지 않는다.

보통 특별한 말이 없으면 일반적으로 단순 경로와 단순 사이클을 구한다.

 

방향이 있는 그래프 (directed graph) = 특정 방향으로만 이동이 가능한 그래프

방향이 없는 그래프 (undirected graph) = 방향이 없는 그래프 (문제를 풀때는 둘다 저장)

 

간선이 여러개인 그래프도 있다.

 

루프 : 시작점과 끝점이 같은 간선.

 

가중치(Weight) : 이동하는 거리, 이동하는데 필요한 시간 등이 있는 그래프

(없으면 간선이동당 1이라고 생각하면 된다)

 

차수(degree) : 정점과 연결되어 있는 간선의 개수

방향이 있는 그래프의 차수 : 나가는 간선(outdegree) / 들어오는 간선(indegree)의 개수를 따로 세준다.

 

<그래프의 표현>

정점(V, N) : 보통 1~V로 차례대로 나타내기 때문에 정점의 수로 저장한다.

간선(E, M) : 어레이에 그냥 저장하는것도 좋지만, 간선을 효율적으로 저장한다

=> 어떤 한 노드와 연결되어 있는 간선을 효율적으로 찾을 수 있다.

1. 인접 행렬

정점의 개수를 V라고 했을 때,

V*V 크기의 이차원 배열을 이용.

A[i][j] = 1 (i->j의 간선이 있을 때), 0 (없을 때)

   1  2  3  4  5  6

1 0  1  0  0  1  0

2 1  0  1  1  1  0

3 0  1  0  1  0  0

4 0  1  1  0  1  1

5 1  1  0  1  0  0

6 0  0  0  1  0  0

장점 : 구현이 쉽다.

단점 : 없는 간선까지 저장해줘야되기 때문에 자주 사용하지는 않는다.

 

 * 가중치가 있는 그래프

간선의 가중치의 범위에 따라 간선이 없을때의 숫자를 결정하면 된다.

(여기서는 0으로 결정했다, 만약 간선가중치가 정수범위다? 하면 인접행렬을 2개를 만드는 방법도 있다.)

    1  2  3  4  5  6 

1  0  2  0  0  7  0

2  2  0  2  3  1  0

3  0  2  0  1  0  0

4  0  3  1  0  7  7

5  7  1  0  7  0  0

6  0  0  0  7  0  0

 

2. 인접 리스트

A[i] = i와 연결된 정점이 링크드 리스트(Linked List)의 형태로 들어가있다.

*주의 : 정점이 아닌 간선임*

A[1] = 2 5

A[2] = 1 3 4 5

A[3] = 2 4

A[4] = 3 5 2 6

A[5] = 1 2 4

A[6] = 4

 

인접행렬(필요 공간 : V^2) : 인접리스트(필요 공간 :  E)

장점 : 필요한 만큼만 공간을 사용할 수 있다.

단점 : 구현하는데 시간이 오래걸리고, 디버깅이 어렵다.

 

C++의 Vector나 Java의 ArrayList와 같이 유동적인 배열이 존재하기 때문에

요즘에는 이런 자료구조로 구현.

 

가중치가 있는 경우에는?

A[1] = (2,2) (5,7)

A[2] = (1,2) (3,2) (4,3) (5,1)의 형태로 저장한다.

 

<그래프의 탐색>

DFS : 깊이 우선 탐색 -> 최대한 깊숙히 많이 가는 것 => 스택사용

BFS : 너비 우선 탐색 -> 최대한 넓게 가는 것. => 큐사용

목적 : 모든 정점을 1번씩 방문

 

BFS 모든 가중치가 1일 경우, 최단거리 찾는 알고리즘이 됨.

 

DFS : 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고,

갈 수 없으면 이전 정점으로 돌아간다.

dfs(x) = x를 방문.

// 인접 행렬로 풀기
void dfs(int x) {

    check[x] = true;
	System.out.println(x);
	for (int i = 1; i <= n; i++) {
    // 간선이 아직 있고, 아직 방문하지 않았으면!
    	if (a[x][i] == 1 && check[i] == false) {
        	dfs(i);
        }
    }
}

// 인접 리스트
void dfs(int x){
	check[x] = true;
    System.out.println(x);
    for (int i=0; i <a[x].size(); i++) {
    	int y = a[x][i];
        if (check[y] == false){
        	dfs(y);
        }
    }
}

BFS : 큐를 이용해서 구현, 큐에 넣기 전에 체크.

// 인접 행렬
queue<int> q;
// 시작점
check[1] = true; q.push(1);
while (!q.empty()){
	int x = q.front(); q.pop();
    printf("%d ",x);
    for (int i = 1; i <= n; i++) {
    	if (a[x][i] == 1 && check[i] == false) {
        	check[i] = true;
            q.push(i);
        }
	}
}

//인접 리스트
queue<int> q;
check[1] = true; q.push(1);
while(!q.empty()) {
	int x = q.front(); q.pop();
    printf("%d ",x);
    for (int i = 0; i < a[x].size(); i++) {
    	int y = a[x][i];
        if (check[y] == false) {
        	check[y] = true; q.push(y);
        }	
    }	
}