그래프란? 그래프 탐색알고리즘(DFS,BFS)

728x90

도입

그래프는 정점과 간선으로 구성되는 중요한 자료구조입니다. 이번 시간에는 그래프에 대한 용어와 그래프를 표현하는 방법 그리고 그래프를 탐색하는 알고리즘을 알아보겠습니다.

그래프란?

그래프는 정점과 간선으로 구성되는 자료구조입니다. 정점은 하나의 객체를 의미하며 Vertex혹은 노드라고 표현합니다. 간선은 정점과 정점을 이어주는 선을 의미합니다. 따라서 그래프를 구현하여 서로 연결되어있는 객체들의 관계를 표현해줄 수 있습니다.

위는 그래프의 예시입니다. A,B,C,D,E를 정점이라하며 각각을 연결하고 있는 선을 간선이라고 합니다.

그래프 용어

그래프의 용어를 정리하도록 하겠습니다.

정점	Vertex라고 하며 하나의 점을 의미합니다. 하나의 객체라고 생각하면 됩니다.
간선	edge라고 부르며 정점과 정점 사이를 이어주는 선을 의미합니다. 간선은 방향이 존재합니다.
정점의 차수	정점에 연결되어있는 간선의 개수를 의미합니다. (한 정점에서 다른 정점으로 연결된 개수)
가중치	간선의 가중치를 의미합니다. 간선의 비용이라고 생각하시면 됩니다.
단순 경로	한 정점에서 다른 정점까지 동일한 정점을 거치지 않고 가는 길을 의미합니다.
사이클	한 정점에서 출발한 단순 경로 중 도착한 정점이 같은 경로를 의미합니다.
루프	출발한 정점과 도착한 정점이 동일한 간선을 의미합니다.

가중치 그래프

가중치 그래프는 간선에 가중치를 보유한 그래프를 의미합니다.

위처럼 각각의 간선에 가중치가 들어있는 그래프를 가중치 그래프라고 합니다.

만약 가중치가 거리라고 가정하고 A에서 B로 갈 때 가장 빠른 길을 고른다고 합시다. 가장 빠른 길은 A에서 B로 가는 단순경로만 비교해 주면 됩니다.(동일한 정점으로 두번 이동시 최단경로는 아님) A에서 B로 가는 단순 경로는 A -> B와 A -> C -> D -> B로 총 2가지 입니다.

계산을 해보면 A -> B는 30, A -> C -> D -> B는 19로 A -> C -> D -> B가 가장 빠른 길이 됩니다.

이렇게 가중치를 따져 계산을 하는 대표적인 예로 라우팅 프로토콜 중에 OSPF가 있습니다.

*OSPF -> 라우팅 프로토콜 중 대역폭(BandWidth)을 고려하여 최단경로를 구성해주는 프로토콜

방향 그래프

그래프의 간선이 방향을 가지고 있는 그래프를 방향 그래프라고 합니다. 무방향 그래프는 A와 B 간선을 연결하면 A -> B, B -> A 모두 이동이 가능하지만 방향 그래프는 단방향으로 갈 수 있습니다.

그래프를 구현하는 방법

그래프는 정점과 간선으로 이루어져 있습니다. 따라서 그래프를 코드로 구현하기 위해서는 각각의 정점(객체)와 그를 이어주는 간선을 구현하여주면 됩니다.

정점을 구현하는 방법

정점을 구현하는 방법은 객체지향언어에서는 Class로 구현할 수도 있고 혹은 인덱스로 생각해주어도 무방합니다.

예를 들어 정점이 5개가 주어진다면, 배열의 인덱스 0부터 4를 각각의 정점이라고 생각해주는 것 입니다.

간선을 구현하는 방법

간선을 구현하는 방법으로는 인접행렬과 인접리스트가 있습니다.

인접행렬은 정점의 개수 $N$에 대해 $N*N$ 사이즈의 1과 0으로 구성된 이차원 배열을 사용하여 구현해주는 방법입니다.

a라는 인접행렬을 만들었다면 a[i][j]의 값은 i번째 정점에서 j로 가는 정점이 연결이 되어있으면 1 아니면 0이 됩니다.

이 방법을 사용할 경우 정점에서 다른 정점이 연결되어있는지 확인하는 방법은 $O(1)$이라는 시간이 걸립니다. 한 정점에 연결되어 있는 모든정점을 찾는 방법은 항상 정점의 개수 $O(N)$이 됩니다. 그리고 매우 큰 단점으로 항상 $N*N$의 메모리를 사용해주어야 하므로 불필요하게 메모리를 사용하게 됩니다.

인접리스트는 Linked List로 간선을 구성해주는 방법입니다. Linked List는 노드를 구현하여 만들 수 있고 동적으로 계속 데이터를 넣어줄 수 있는 라이브러리를 사용하여 구현할 수도 있습니다.(Java는 ArrayList, C++은 vector가 있습니다.)

Linked List는 정점의 개수 $N$개 만큼만 만들어 주면 됩니다. 그리고 각각의 List 뒤에 해당 정점과 연결된 정점을 넣어주면 됩니다.

이 방법을 사용할 경우 정점에서 다른 정점이 연결되어 있는지 확인하는 방법은 각 정점의 연결 되어있는 정점의 수인 $O(정점의 차수)$가 됩니다. 한 정점에서 모든 정점을 찾는 방법은 항상 $O(정점의 차수)$가 됩니다. 인접행렬과 다르게 메모리를 낭비하는 일은 없습니다.

그래프 탐색 알고리즘

연결요소를 전체적으로 1회만 탐색하는 알고리즘으로 DFS와 BFS가 있습니다. DFS와 BFS는 그리디한 알고리즘 입니다.

연결요소를 잠깐 알아봅시다. 그래프에서 이어져 있는 요소들을 연결요소라고 합니다. 아래 그림을 보면 A,B,C,D와 E,F,G 각각 2개의 연결요소로 이루어져 있는 것을 알 수 있습니다.

이제 본론으로 돌아와 그래프를 탐색하는 알고리즘은 DFS와 BFS를 알아봅시다.

DFS

DFS는 깊이우선탐색법이라 불립니다. DFS를 구현할 때는 자료구조 Stack을 사용하게 됩니다.

DFS는 깊이를 우선적으로 탐색하기 때문에 시작점에서 시작하여 연결되어 있는 곳 중 확인을 안한 곳으로 바로 탐색을 하러 들어갑니다. 탐색을 하러 들어갈 때마다 항상 탐색한 정점을 스택에 넣어두게됩니다. 따라서 위 순서을 보면 A부터 탐색을 시작한다고 하면, A를 스택에 넣고 A와 연결되어 있는 B,C,D 중 한 곳(예시는 B)을 탐색합니다. B를 탐색했으므로 스택에 B를 넣어주고 B와 연결된 것 중 E를 탐색하러 갑니다.(A,E 중 A는 이미 확인했으므로 E) E를 스택에 넣고 E와 연결된 F로 계속 연결된 정점을 찾아가게 되어있습니다.

그리고 F까지 확인을 했을 때는 더 이상 F와 연결된 정점 중 검색을 안한 정점이 없으므로 다시 돌아가게 됩니다. 이 때 스택을 사용하게 됩니다. 스택은 후입선출의 자료구조이므로 가장 최근에 넣은 데이터가 나오게 되어있습니다. 따라서 F이전에 넣었던 곳으로 되돌아가기 위해 스택을 사용합니다. 따라서 F 이후 E를 확인하고 E에도 추가적인 조치가 필요없다면 B 그 다음에 A 그리고 A에 아직 확인안한 C와 D를 위의 설명드린 방법대로 확인하여 모두 탐색하게 됩니다. DFS는 이처럼 그리디하게 깊이를 우선적으로 탐색하는 알고리즘 입니다.

코드로 구현할 때는 스택을 꼭 만들필요는 없습니다. 메소드의 호출이 바로 스택과 동일하기 때문에 재귀로 구현해주면 스택의 역할을 자연스럽게 수행합니다. 아래의 재귀함수 처럼 연결된 정점에 대한 리스트를 활용하여 확인하지 않은 정점이라면 재귀적으로 들어가서 확인하면 됩니다.

    //재귀로 dfs 구현 예 
    public void dfs(int x, boolean[] checked, ArrayList<Integer>[] edgeList){
        checked[x] = true;
        ArrayList<Integer> vertexs = edgeList[x];
        for(int i = 0; i < vertexs.size(); i++){
            int ver =vertexs.get(i);
            if(!checked[ver])
                dfs(ver,checked,edgeList);
        }
    }

시간복잡도를 생각해보면 인접 행렬과 인접리스트로 구현할 때 다르다는 것을 알 수 있습니다.

우선 dfs는 모든 정점에 대하여 한번씩 수행되므로 정점의 개수(V)만큼 수행되는 것을 알 수 있습니다.

이 때 인접행렬일 경우 각 정점이 연결되어있는지 모두 확인해주기 때문에 1개의 정점당 모든 정점의 개수만큼 확인하게 됩니다. 따라서 시간복잡도는 $O(V^2)$가 됩니다.

하지만 인접리스트 구현한 경우는 간선의 수(E) 만큼만 수행이 됩니다. 따라서 시간 복잡도는 $O(V+E)$가 됩니다. 통상 간선의 수가 항상 정점보다 많기 때문에 $O(E)$라고 생각하여도 됩니다.

BFS

BFS는 너비 우선 탐색이라고 불립니다. DFS와 다르게 구현을 할 때는 큐를 사용합니다.

BFS는 DFS와 다르게 연결되어있는 간선들을 모두 탐색하며 진행합니다. 탐색과 동시에 Queue에 넣어주게 됩니다. 이 말이 구현을 할 때 굉장히 중요한 부분입니다. 우선 시작점 A를 Queue에 넣어주고 A를 체크했다고 표시하여줍니다. 그리고 A와 연결된 B,C,D를 순서대로 넣어주고 체크했다고 표시해줍니다. Queue의 상태는 현재 B,C,D의 순서로 들어와 있으며 선입선출 자료구조이기 때문에 다음에 나오는 값은 B일 것 입니다. 다음에 Queue에서 B를 빼주고 B와 연결된 정점 중 체크가 안된 정점을 찾아 Queue에 넣어주고 체크해줍니다. 이렇게 되면 현재 Queue는 C D E가 들어간 상태일 것입니다. 다음 C를 꺼내서 동일한 작업, D를 꺼내서 동일한 작업을 수행합니다. E를 꺼내고 F가 체크가 안되어있으므로 F를 Queue에 넣고 체크합니다. 마지막으로 Queue에서 F를 꺼내어주고 더 이상 Queue에 정점이 없으므로 종료됩니다. BFS는 이처럼 너비를 우선적으로 탐색하는 그리디 알고리즘 입니다. DFS와 결과는 다르지만 결론적으로 동일하게 연결요소의 모든 정점을 한번씩만 확인하게 됩니다.

BFS를 구현할 때 가장 중요한 것은 Queue에 넣는 순간 check를 해주어야 한다는 것 입니다. DFS의 경우 함수로 호출 되고 체크를 해주어도 무방하였지만, BFS는 그렇지 않습니다. Queue에 넣는 순간 check를 하지 않고 Queue에서 나올 때 check를 한다면 중복된 데이터를 체크하게 됩니다.(B,D가 연결되어 있다고 가정하면 A를 체크하고 B,C,D를 넣었는데 B를 체크할 때 D가 체크가 안되어 있으므로 D가 추가로 들어가게 됩니다.)

시간복잡도는 DFS와 동일하게 됩니다.

인접행렬로 구현 시 $O(V^2)$

인접리스트로 구현 시 $O(V+E)$

마무리

그래프는 정점과 간선으로 구성된 객체들의 연결상태를 보여주는 자료구조입니다.
BFS와 DFS는 시간복잡도는 동일하며 구현의 차이가 있습니다. DFS는 스택을 사용하며 BFS는 큐를 사용합니다. 실제로 구현할 때 DFS는 재귀함수를 사용하여주면 스택을 사용하지 않아도 됩니다. BFS를 구현할 때 유의할 점은 큐에 삽입할 때 해당 데이터를 체크하였다고 체크해주어야합니다.

잘못된 정보나 궁금한점은 편하게 댓글 달아주시면 감사하겠습니다 :)