[Section 4] 그래프 알고리즘 _ 인접 행렬(Adjacency matrix)

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

인접 행렬 방식으로 구현한 그래프는 빽빽한 그래프에서 더 유리하다는 장점을 가지고 있다. 그렇다면, 그래프를 인접 행렬 방식으로 구현하는 알고리즘에 대해 배워보자.

1.  리스트를 집합으로 활용하기 _ 벌텍스와 초기화 알고리즘

그래프를 구현하기 위해서 벌텍스 V의 집합을 구현하고, 각각의 원소는 v로 초기화하여 리스트에 담아보는 알고리즘에 대해 배워보자. 이 알고리즘에는 두 개의 클래스를 구현하고 이를 연계하여 집합 형태의 벌텍스를 구현하겠다.

 

예시 코드:

class Vertex:
    def __init__(self,data):
        self.v=data
        self.visited=False 
    def setv(self,v):
        self.v=v
    def getv(self):
        return self.v

class Mgraph:
    def __init__(self,numV,cost=0):
        self.AdjM=[[-1]*numV for _ in range(numV)]
        self.numV=numV
        self.V=[]
        for i in range(0,numV):
            newV=Vertex(i)
            self.V.append(newV)

 

* 위에서 사용된 변수 중 AdjM이 이중 리스트로 구현된 행렬이고, numV는 원소의 총개수를 의미한다. 마지막으로 V가 벌텍스의 집합을 의미하는 변수이고, v가 그 원소 변수를 의미한다고 할 수 있다.

 

이렇게 벌텍스 집합을 구현하면, numV x numV의 이중 행렬 AdjM을 생성 할 수 있다. 그리고 그 원소는 모두 -1이다. 이때 벌텍스 집합 V는 numV 개수의 원소를 가지게 된다. 모든 원소는 Vertex 객체를 갖게 되는데, 이는 우리가 원소를 추가하지 않았기 때문이다. 그렇다면, 이번에는 원소를 추가하는 알고리즘을 구현해보자.

2.  원소를 추가하는 알고리즘 구현

원소를 추가하는 알고리즘을 구현하기 위해 위에서 예시로 정의한 Mgraph 클래스에 다음의 함수를 추가하자.

 

예시 코드:

    def setV(self,vertice,v):
        if 0 <= vertice <self.numV:
            self.V[vertice].setv(v)
    def getV(self,n):
        for i in range(0,self.numV):
            if n == self.V[i].getv():
                return i
        else:
            return -1

 

vertice 변수는 V 리스트의 인덱스를 의미한다고 할 수 있다. 그리고 setv(v) 함수를 통해 원소를 할당하는 것이다. 마지막으로 -1 반환 값은 변수 n에 해당하는 원소는 행렬에 존재하지 않는다는 의미이다. 

 

구체적인 예를 위해서 다음과 같이 엣지는 구현하지 않은 예시 그래프를 생성해보자.

예시 그래프 생성하기

 

생성 결과: 

그래프 생성 예시

 이제 엣지를 구현하여 행렬로 나타내기만 하면 된다. 

3.  그래프의 엣지와 방향 구현 알고리즘 _ 행렬에 연결 상태 나타내기

먼저 행렬에 연결 기능을 추가하는 함수는 다음과 같은 예제 코드로 구현할 수 있다.

 

예제 코드:

    def addE(self,fr,to,cost=0):
        if self.getV(fr)!=-1 and self.getV(to)!=-1:
            self.AdjM[self.getV(fr)][self.getV(to)] =cost
            self.AdjM[self.getV(to)][self.getV(fr)] =cost
    def getE(self):
        E=[]
        for v in range(0,self.numV):
            for i in range(0,self.numV):
                if self.AdjM[i][v] != -1:
                    vdata = self.V[v].getv()
                    idata = self.V[i].getv()
                    E.append((vdata,idata,self.AdjM[i][v]))
        return E

 

addE 함수가 AdjM 행렬[fr][to]에 해당하는 값을 cost 변수로 바꾸어 준다. 여기에서는 cost = 0 가 연결된 상태를 의미한다.  위에서는 비 방향 그래프이기 때문에 파란색 코드를 추가해주었는데, 방향 그래프에서는 파란색 코드를 제거해야 한다. 

 

getE 함수는 연결된 벌텍스 원소 쌍과 연결 값(cost)을 반환해주는 함수이다. 

 

구체적인 예를 위해서 다음의 예시 그래프를 생성해보자.

예시 그래프 생성하기

 

코드 결과:

그래프 생성 예시

 

* 필요에 따라 상황에 맞는 결과를 출력하는 함수를 구현하여 사용하기로 하자.