[그래프 알고리즘] 인접행렬과 그래프 (초보자용)

초보자를 위해서 써봅니다. (사실 저도 알고리즘 책 1권밖에 공부 안한 초보자입니다만 ^^;;)

이해에 관련된 민감한 오타등은 댓글 달아주심 고치도록 하겠습니다. 글자가 많아서 지루할수도 있지만 열심히 쓸테니 차근차근 읽어 주시면 감사하겠습니다. 문단은 글이 좀 길어질 경우 내용이 계속 이어지더라도 보기편하시라고 중간중간 띄어놓도록 하겠습니다.

 

FOUNDATIONS of USING C++ PSEUDOCODE

저자 : Richard Neapolitan / Kumarss Naimipour

 

위의 책을 참고하였음을 밝힙니다. ^^

 

사실 어떻게 보면 알고리즘 공부 전에 자료구조에서 그래프를 미리 접하는 경우가 있기 때문에...

알고리즘에서 굳이 인접행렬에 대해 설명 할 필요는 없습니다만... 앞에서와 같이 초보자를 위한 글이므로...

또한 자료구조를 공부하셨다고 해도 기억이 가물가물 할 수 도 있으므로... 자료구조와 알고리즘의 영역에 대해 논하는 것은 민감한 사항이기도... 뭐 어떻게 딱 나눌수가 없다는 ㅎㅎ C와 C++간의 관계와 비슷하다고 할 수 있는건가... 글쎄...

아래에서 사용하는 용어는 다른책에선 좀 다르게 말할 수도 있습니다. 그래도 거의 비슷하기때문에 아래 용어를 기억하나면 별 문제는 없을 듯 싶습니다. 한글로는 용어가 다르더라도 영어로는 거의 같을겁니다. 내용을 자세히 들어가면 더 많은 내용과 용어들이 있으나 앞에서 밝히바와 같이 초보자용임을 잊지 말아 주시길... ^^

 

제목엔 인접행렬을 강조하기 위해서 앞에 뒀지만 사실은 그래프(Graph)를 먼저 알아야 인접행렬(Adjacent matrix)을 알 수 있습니다.

따라서 그래프를 먼저 보도록하겠습니다. 그래프는 경로에 관련되 문제에 많이 사용 됩니다.

용어들을 알기에 앞서서 일단 그래프란 녀석이 뭔지 그림으로 보도록 합시다.

 

 

보시면 아시겠지만 뭐 별거 없습니다. 동그라미 있구 화살표 찍찍 화살표에 숫자 써있고 제가 설명안해도 감으로 뭘 말하는지 때려 잡으시는 분들이 많을거 같군요. 대강 예상을 하셨다면 제가 설명할 내용과 큰 차이 없을 겁니다. 그럼 하나 하나 보도록 하죠. 우선 원을 '정점(vertex, node)'이라고 합니다. 정점이란 개념은 계속 설명을 듣다보면 이해가 가실테지만 지금 대충 둘러대자면 땅? 위치? 뭐 그정도로 가능하겠군요. 원에 써있는 글자는 그 정점의 이름이구요. 원과 원을 잇고있는 선은 '이음선(edge, arc)'이라고 합니다. 한 정점에서 다른 정점으로 연결이 되어 있다는것은 이동가능하다라는 것을 의미한다고 할 수도 있겠군요.(제가 앞에서 계속 무엇은 무엇이다라고 정확히 말하지않고 무엇은 무엇이라고 할 수 있다 정도로 설명하는 것은 그래프가 다양한 용도에 쓰이기때문에 꼭 뭐라고 말 할 수 없기 때문입니다.) 하지만 이해의 편의를 위해서 정점을 섬이라고 생각하도 이음선을 다리라고 생각해도 좋겠습니다. 아래에선 이걸 활용하여 설명하겠습니다.

 

이음선에 화살표가 있는것을 볼수 있는데요. 그건 그 '방향(direction)'으로만 이동가능하다는 것입니다. 그림을 보시면 정점v1과 v2는 양쪽으로 화살표가 있기때문에 왔다갔다가 가능합니다. 하지만 정점v1과 v4의 경우 v1에서는 v4로 갈 수 있지만 v4에서는 v1으로 갈 수가 없는거죠. v4에서 v1으로 가려면 v4에서 v5로 간다음 v1으로 가는 방법이 있겠죠. 이음선의 화살표를 설명하던중 '경로(path)'에 대한 내용이 나왔군요. 앞에서와 같이 이동가능한 정점을 순서대로 나열한 것을 경로라고 합니다. [v1, v4], [v4, v5, v1] 이것을 경로라고 말합니다. 하지만 [v4, v1]은 경로가 아닙니다. 그래프를 보시면 아시겠지만 v4에서 v1으로 가는 길은 없습니다 따라서 경로가 아닌거죠. 가고싶다면 앞에서 나온 [v4, v5, v1]이경로를 이용해야죠 당연히 다른 경로도 있을수 있습니다. [v4, v3, v4, v5, v1]이런 경우죠... 왜 쓸데없이 v3갔다가 다시 v4오냐고 그러신다면 쓸데없는거 맞다고 대답해 드리겠습니다 ^^ 쓸데없는것 맞고 경로도 맞습니다. 어쨋든 이동 가능한 정점 순서이니 경로는 맞는거죠. 최단경로를 구하거나 할때는 이런 경로는 제거해야겠죠.

 

이번엔 경로를 설명하던중 '순환(cycle)'이 등장했군요. 시작한 정점에서 다시 그정점으로 오는 경로는 순환이라고 합니다. [v4, v3, v4] 이건 딱 봐도 순환이군요... 위의 그래프에서 다른 순환도 찾아보면 [v1, v4, v5, v1]도 있군요. 심심하시면 다른 순환도 찾아보세요 ^^ 그래프에 순환이 존재하면 '순환적(cyclic)'하고, 그렇지 않으면 '비순환적(acyclic)'이라고 합니다. 당연히 위의 그래프는 순환이 있었으니 순환적이라고 해야겠죠? 다음으로 '단순경로(simple path)'에 대해 알아봅시다. 단순경로란 같은 정점을 두번거치지 않는 경로를 말합니다. [v4, v3, v4, v5, v1] 이경로는 v4 정점을 두번 거치니 단순경로가 아니군요. 즉, 순환을 포함하면 단순경로가 될 수 없는 겁니다. 지금 쯤이면 이걸 왜따지고 있냐고 생각하는 분들도 있을텐데... 조금 감이 있으신분들은 순환이 있는 경로는 비효율적이니 최단 경로 계산시 제거해야되겠구나 정도로 생각하실 수 있겠고... 감이 안오시더라도 상관 없습니다. 여기에선 그래프와 인접행렬을 알아보자는 거니까요. 그냥 그런것이 있구나 하고 지나가시면 되겠습니다. 앞으로 나오는 용어들은 모두 언젠간 필요한 것들 입니다.

 

이음선 위의 값은 '가중치(weight)'라고 하며 이동거리 또는 비용을 나타냅니다. (앞에서 말했지만 꼭 앞처럼 말 할수 없습니다. 그래프는 각종 문제 해결 도구로 쓰이기 때문입니다. 이해의 편의를 위해 알기 쉬운 예를 들 뿐입니다.) 거리가 더 이해하기 편하실듯...

[v1, v2] 경로의 경우 거리는 1이고, [v2, v1]의 경우는 거리가 9입니다. 적당한(?) 예를 둘러대자면 v1이 산 꼭대기이고, v2가 산 밑이라 v2에서 v1으로 가면 오래걸린다는 식의 그래도 거리 길이는 같지만 뭐 그렇다는 겁니다. 단지 어거지예일뿐... 각자 좀 생각해 보면 방향에 따라 그런 상황이 생길 경우가 있는것을 알 수 있을거라 생각됩니다. 거리말고 비용이라고 생가하면 좀 나을지도 그리고 앞에서 말했듯이 그래프는 각종 문제 해결에 쓰이므로 방향에 따라 가중치가 달라질 경우는 충분히 있습니다. '길이(length)'는 경로의 가중치를 모두 합한값을 말합니다. [v4, v5, v1]의 경우 3 + 3= 6 길이가 6이군요.

 

배운내용을 토대로 위의 그래프 이름을 다시 지으면 '가중치 포함 방향 그래프'라고 말 할 수 있습니다. 만약 가중치를 없애면 방향그래프일테고 방향을 없애면 가중치포함 비방향 그래프라고 말할수 있겠습니다. 이왕 말 나온 김에 이제는 비방향 그래프를 보도록 합시다.

 

 

말 그대로 비방향 그래프입니다. 방향이 없는거죠... 방향이 없다면 더 말이안될수... 정리해서 다시말하면 양방향이라는 겁니다. 양방향이니 굳이 방향을 표시할 필요없다는 겁니다.(이음선 하나 하나가 양쪽으로 화살표를 지닌다고 보면 됩니다.) 센스있으신 분이면 이그래프의 정확한 이름을 지으실수 있습니다. 가중치 포함 비방향 그래프 이 이름을 지었다면 정말 휼륭하십니다 ^^ 앞의내용을 차근차근 읽으신 분이겠죠? 아님 이미 알고계시거나... 좀더 정확히 표현 하자면 '연결된, 가중치가 있는, 비방향 그래프'라고 말 할 수 있습니다. 연결된 이란... 따로 고립되어있는 정점이 없는것을 말합니다. 만약 v1,v3사이의 이음선과 v1,v2사이의 이음선을 제거하면 이 그래프는 연결된것이 아닙니다. 다른 노드에서 v1으로 갈 방법이 없기 때문입니다. 만약 v1,v2사이의 이음선과 v2,v3사이의 이음선 그리고 v3,v4사이의 이음선 이렇게 3개를 모두 제거해도 서로 이동이 모두 가능하기때문에 연결되어있다고 봅니다. 트리라는 개념도 있는데... 여기에선 본격적인 알고리즘 설명을 하기보단 그래프를 알기위함이었으므로 생략하도록 합니다.

 

지금까지 그래프의 설명을 잘 읽어 오셨습니다. 그렇다면 이제 인접행렬을 알아보도록하죠!!

 

그래프를 이용해서 각종 문제를 해결 할 수 있습니다. 하지만 그 그래프를 컴퓨터로 표현하지 못한다면 물거품이겠죠?

그래프를 컴퓨터로 표현하기위해 사용하는 것이 바로 인접행렬 입니다. 행렬이라... 뭐가 떠오르시나요...??

그렇습니다. 2차원 배열입니다 ㅎㅎ 감동(?) 아닌가... 이내용을 처음 접하고 감도을 받으셨다면 당신은 프로그래머적 감수성(?)이 풍부하신 분일 겁니다 *^^*

 

저는 설명의 편의를 위해 그냥 행렬로 나타냅니다. 여러분들도 그냥 행렬로 이해하시고 써먹을땐 2차원배열에 적용하시면됩니다. 계속 말하지만 이건 초보자용이므로 그냥 설명만하고 적용까지는 하지 않습니다. 적용은 몇몇분이 지금 강좌를 쓰고계신듯 합니다. 전 그냥 한번 써보는 정도라... ㅎㅎ 또 언제 필 충만하면 작성할지는 모르겠으나... 헐... 인접행렬도 방향있는 그래프를 가지고 먼저 설명하겠습니다. 그래야 비방향은 쉽게 끝납니다. ㅎㅎ

 

 

위쪽이 정의이고 좌측아래가 그래프 우측 아래가 인접행렬이 되겠습니다. 간선은 이음선과 같은 말이구요. 보시면 어느정도 감이 잡히실겁니다. 위의 그림을 보고 다 이해하시는 분들도 계실 겁니다. 그래도 설명은 들어 갑니다 ^^ 위의 정의를 보면 i가 행이 되겠고, j가 열이 되겠습니다. 이음선이 있으면 행렬값으로 가중치를 넣어주고 없으면 무한대를 넣어주고 i=j인 경우 즉 한 정점에서 자기 자신의 정점으로 오는경우는 0으로 합니다. 당연히 자기자신이면 거리가 0이지 않습니까? ^^ 그럼 이젠 인접 행렬을 읽어 보도록하죠! 행이 출발 정점이고 열이 도착 정점이라고 하면 모든것이 해결 됩니다. 정점v1을 기준으로 제가 쫙 읽어 보겠습니다. 그다음은 여러분들이 충분히 읽으실수 있을거라 생각됩니다. 1행1열 v1->v1 자기 자신으로 가는 것이므로 정의 대로 0을 넣습니다. 1행2열 v1->v2 그래프를 보시면 1이군요 그래서 1행2열은 인접행렬에서 가중치인 1을 지닙니다. 1행3열 v1->v3 그래프를 보면 이음선이 없군요. 정의대로 무한대로 보냅니다. 1행4열 v1->v4 그래프를 보면 1입니다. 따라서 1을 가지고요. 1행5열 v1->v5 5군요... 이런식으로 하면 충분히 행렬로 나타낼수있습니다. ^^ 간단하죠? 말로 설명할래니까 복잡하지... 알고보면 별거 없습니다. 그래프만 보고 인접행렬을 그리신다면 충분히 이해했다고 볼 수 있습니다. 이제 비방향 그래프를 알아보죠... 이미 여러분은 비방향 또한 인접행렬로 나타내는 방법을 아시고 계시지만요.

 

 

앞의 내용을 이해 하셨다면 이또한 이해되실겁니다. 여기서 주목할 만한 점은 비방향그래프는 양방향이기때문에(앞에서 말했지만 비방향 그래프는 이음선 양끝에 화살표가 있는것이라고 했습니다 ^^) 행렬값이 0으로 이루어진 대각선을 기준으로 대칭이라는 것이죠.. 흥미롭지 않으신가요? 이를 적용하는것은 다른분들이 이미 강좌를 쓰고계신것 같네요. 최소비용신장트리를 구하는 알고리즘에 이 기본지식은 튼튼한 버팀목이 될겁니다. 플로이드, 프림, 다익스트라, 크루스칼 알고리즘등의 이해를 위해서 이 내용들은 반드시 숙지하셔야 합니다. 이 알고리즘이 사용될만한 우리생활에서 접할수있는 예를 들자면 지하철 두개 역의 최단경로를 구하는 프로그램을 들 수 있겠네요 ㅎㅎ 설명은 약간 길었지만 별 내용은 없습니다. 제대로 이해했는지 확인 하는 가장 좋은 방법은 그래프를 아무렇게나 그려놓고 인접행렬로 옮겨 보시는 겁니다. 지금까지 읽으시느라 수고 많으셨습니다. 다음에 또 기회가 되면 나름대로(매우 중요한 단어)쉽고 자세한 강좌를 쓰도록 하겠습니다. 감사합니다~!