그래프에서의 인접행렬과 인접리스트

그래프의 탐색을 하기 위해서는 그래프 정보를 저장해야만 한다.

그래프의 저장 방법 2가지를 살펴보고, 실제 예제를 통해 어떻게 적용되는지 살펴보도록 하겠다.

위와 같은 그래프는  방향성과 가중치를 가지고 있다. 이 그래프를 2가지 방법으로 자료를 정리해 보자.

인접행렬

인접행렬의 경우 2차 배열을 생각하면 쉽다. 이 때 기본 규칙은 간단하다.

각 점을 기준으로 갈 수 있는 방향에 데이터를 저장하며, 갈 수 없다면, 특정한 값을 입력해 놓도록 한다.(기본적으로 0 혹은 -1을 사용한다.)

가중치가 없는 경우라면 0과 1로 표현이 가능하다. 또한, 고민해 보아야 할 것은 방향성을 갖지 않는 경우이다. 예를 들어 위의 예제 그래프의 경우 정점 1에서 2로 이동하는 경로는 1가지 이다.  하지만 방향성이 없는 경우라면 1에서 2로 이동할 수 있으며 그 반대인 2에서 1로의 이동이 가능하다는 것을 알아야 한다.

위의 그래프에서 정점 1에 대한 경로를 저장하면 다음과 같다.

	1	2	3	4	5	6	7	8
정점 1	0	5	4	0	0	0	0	0

배열로 저장하게 되면 다음과 같은 자료를 구성할 수 있다. 얼마나 간단한가!!

이러한 방법으로 2차 배열을 완성할 수 있을 것이다.

	정점1	정점2	정점3	정점4	정점5	정점6	정점7	정점8
정점 1	0	5	4	0	0	0	0	0
정점 2	0	0	0	0	2	1	0	0
정점 3	0	0	0	0	0	3	0	0
정점 4	6	0	0	0	0	0	0	0
정점 5	0	0	0	0	0	7	0	9
정점 6	0	0	0	0	0	0	2	3
정점 7	0	0	0	5	0	0	0	0
정점 8	0	0	0	0	0	0	4	0

위의 표와 같이 자료가 저장 될 수 있다. 이와 같이 입력 받기 위해서는 다음과 같은 코드를 사용할 수 있다.

scanf("%d", &n);                        //c 코드 for(i=0;i<n;i++){    scanf("%d %d %d",&s,&t,&v);    ar[s][t]=v; }

위와 같은 인접행렬로 작성하는 경우 매우 쉽게 그래프 데이터를 저장할 수 있다는 이점을 갖는다. 하지만 인접행렬의 문제점은 무엇을까?

인접행렬의 문제점

인접행렬의 문제점으로는 실제 수행으로 들어가면 나타나게 된다. 예를 들어 특정 정점과 연결된 정점을 찾기 위해서는 모든 정점을 살펴보아야 한다는 것이다.

	1	2	3	4	5	6	7	8
정점 1	0	5	4	0	0	0	0	0

예를 들어 1번과 연결된 정점은 2, 3밖에는 존재하지 않지만, 이를 알아내기 위해서는 1번 정점부터 8번 정점까지 모든 정점을 순회해야 한다는 것이다. 이건 정말 낭비가 아닐 수 없다. 특히 정점이 늘어나면 늘어날 수록 그 탐색의 범위가 넓어지게 되며 결국 성능의 저하가 나타날 수 밖에 없다.

상상해 보시라. 만약 100개의 정점이 있다면, 각 정점에 도착할 때마다 적어도 100번씩 순회해야 한다. 게다가 모든 정점이  한 가지의 경로만을 가지고 있으며 모든 정점을 거친다고 하면, 경로는 1개 밖에 없지만 이를 탐색하기 위해서는 100 * 100 = 10000 번을 탐색해야 한다.

물론 정보올림피아드 문제에서 사례수를 적절히 조절하기 때문에 이 같은 문제점으로 인해 낮은 점수를 받는 경우는 그렇게 많지는 않을 것이다. 하지만 후반부 문제로 넘어갈수록 수행 시간이 길어진다는 것은 상과도 멀어진다는 것을 알아야 한다. 따라서 좀 더 효율적인 방법은 없을지 살펴보자.

인접리스트

이름에서 감이 온다. 얜 리스트다. 리스트… 리스트… 리스트를 쓰면 구현의 시간이 필요하다라는 겁부터 먹지 말고 일단 들어보시라.

이 녀석으로 구현하면 인접행렬의 구현에서 문제점인 연결되지 않은 정점까지도 표현이 된다는 것이 사라진다.

즉, 시작 정점에서 연결된 정점만을 리스트로 구현한다는 아이디어이다. 예를 들어 이렇게 표현 하자는 것이다.

위와 같은 그래프가 있다. 가중치는 있고, 방향성을 아직 넣지 않은 경우이다.

이런 경우 a에서 도착할 수 정점을 살펴보면 B와 D입니다. 즉 a가 가진 리스트를 위와 같이 연결하는 것이다.

가중치까지 넣어야 한다!

그렇다면 다음과 같이 표현하면 된다.

으아.. 리스트의 요소들이 값까지 갖게 되었습니다. 그렇다면 리스트의 요소들은 정점 정보, 값 정보, 다음 요소의 주소 정보, 3가지까지 갖게 하는 구조체로 만들어서 구현해야 할까? 그렇다면 오히려 구조체 구현에 시간이 더 소요되지 않을까?

정점 정보

가중치 정보

다음 정점 주소

과연 이따위 구조체를 만들어야 하는가…

이렇게 만들기가 귀찮다면 다른 방법이 있다!. 바로 이때 벡터를 사용하는 것이다! 벡터를 사용하는 방법을 모르겠다면…

다음 링크를 참조하자.

http://talksis.ga/30   배열을 대신하는 벡터!

사실, 리스트를 만들지 않고 벡터 배열을 사용하면 된다.

몇 가지 규칙을 사용하면 되는데

1. 만약 가중치가 없다면

이때는 그냥 경로만 저장하면 된다. 경로가 존재 여부가 요소가 있느냐 없느냐가 되는 것이다.

  2.  만약 가중치가 있다면

이때는 경로 뒤에 가중치까지 하나의 요소로 넣어 버린다. 이렇게 된다면, 값을 읽을 때 요소 2개씩을 한꺼번에 읽어 버리는 방법이 되는 것이다.

일단 어떤 방식인지를 보자.

이렇게 표현하게 되는데..

가로는 벡터 자료고..

각 정점은 배열이 된다..

예를 들어 이렇게 되는것이다.

vector<int> ar[8];

이렇게 자료를 만들면

ar[1] 은 int를 저장하는 벡터가 된다. 이 벡터에 각 자료를 저장하는데.

정점 1의 자료만 보자

	정점	가중치	정점	가중치
정점 1	2	47	3	69

이렇게 구현되는 것이며 정점 1에서 정점 2로 가는데 47의 비용이 , 정점 1에서 정점 3으로 가는데 가중치 69가 소요된다는 정보를 저장하는 것이다.

말하는 것이 더 어려울지 소스코드로 살펴보자

이런 경우 다음과 같은 소스코드로 인접리스트를 만들 수 있다.

//c++ stl vector 사용    int n,s,t,v,k;    vector<int> ar[100];    scanf("%d", &n);    scanf("%d", &k);        for(int i=0;i<k;i++){//데이터 입력        scanf("%d %d %d",&s,&t,&v);        ar[s].push_back(t);        ar[s].push_back(v);    }    for(int i=0;i<n;i++)//모든 정점에서 갈 수 있는 길 순회    {        printf("시작 : %d ",i );        for(int j=0;j<ar[i].size();j+=2)            printf("-> 정점 %d 값 %d  ",ar[i][j],ar[i][j+1]);        printf("\n");    }

소스 코드는 어려운 부분은 없다. 입력에서 벡터임으로 push_back 메소드를 이용하여 입력을 받으며,

출력에서는 배열처럼 접근이 가능하다. 한 가지 중요한 점은 각 정점에서 갈 수 있는 정점이 가변적이기 때문에 벡터의 사이즈를 기준으로 조건을 작성해야 한다는 점이 다르다.

인접리스트 vs 인접행렬 .. 뭘쓰지?

이런 고민이 드는건 바로 정점의 갯수에서 차이가 나게 된다. 만약 정점의 갯수가 작다면 인접행렬을 사용해도 무방하다. 하지만 정점이 점점 많아질 수록 쓸때없는 방문이 늘어나게 된다.

계산량으로 표현해 보자면… 인접행렬의 모든 정점을 참색하는데는 O(nm)의 시간이 필요하다.

하지만 인접리스트의 경우에는 O(n+m)의 시간이 소요되는 것이다.

O(nm) vs O(n+m)이 된다..

일반적으로 m은 다시 탐색해야 하는 경로라면..

O(n2) vs O(2n)= O(n)  이 되어버린다!

설명은 끝났다. 당신은 뭘 쓰겠는가?