[Section 4] 그래프 알고리즘 _ 인접 리스트(Adjacency List)

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

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

0. INTRO

이번에는 인접 리스트 알고리즘을 생성해보자. 여기에서는 이전에 생성했던 단일 연결 리스트 알고리즘을 이용할 것이다.

1.  인접 리스트 방식 _ 구현 그래프

먼저 다음의 그림을 참고하자. 왼쪽은 예시 그래프이고 오른쪽은 구현할 자료 구조를 리스트 형태로 나타낸 것이다.

 

예시 그래프와 리스트 형태의 자료구조

 

개인적으로 인접 행렬 방식보다 연결 리스트 방식이 그래프의 연결 상태를 확인하기에 깔끔해 보이긴 한다.

 

생성 예시:

2.  인접리스트 알고리즘 _ 구조 이해하기

위에서처럼 그냥 연결 리스트로 만들어주는 방법보다는 자동으로 연결하게 만드는 기능의 알고리즘을 배워보자. 추가로 연결 리스트의 마지막 노드는 헤드를 가리켜야 한다. 그렇게 하는 편이 추후의 탐색 알고리즘을 위해서도 좋다. 그렇다면, 가장 기초적인 벌텍스 알고리즘을 다음의 예시 코드로 보자.

 

* 노드 클래스는 생략하였다.

 

예시 코드:

class Vertex:
    def __init__(self,node):
        self.node=node
    def setv(self,node):
        self.node=node
    def getv(self):
        return self.node

 

class GraphL:
    def __init__(self):
        self.Dictionary={}
        self.numV=0

 

여기서 이해할 것은 우리가 생성할 노드를 어떻게 그래프로 구현하는지를 우선적으로 알아야 한다. 

다음의 코드 결과를 통해서 어떤 방식으로 연결 리스트가 형성되는지 이해하자.

 

코드 결과:

 

벌텍스 생성과 구조의 이해

 

딕셔너리로 구현화한 형태 이해하기

3.  인접 리스트 알고리즘 _ 딕셔너리 방식으로 ADT 구현하기

그래프를 딕셔너리로 나타내고 각각의 키값들을 통해서 어떤 벌텍스 원소로 접근하는지를 이해했다면, 이제 주 ADT를 구현화하자. 위의 예시에서는 인접 리스트를 말 그대로 단일 연결 리스트 형태로 구현했다면, 이번 예시에서는 연결 리스트조차 집합 형태로 나타내고자 한다.

 

다음의 예시코드를 확인하자.

 

 

예시 코드:

class Vertex:
    def __init__(self,node):
        self.node=node
        self.adjacent={}
    def setv(self,node):
        self.node=node
    def getv(self):
        return self.node
    def getkeys(self):
        return self.adjacent.keys()
    def __str__(self):
        return str(self.node)+ " adjacent = " + str([x.node for x in self.adjacent])

class GraphL:
    def __init__(self):
        self.Dictionary={}
        self.numV=0
    def addV(self,v):
        self.numV=self.numV+1
        newV=Vertex(v)
        self.Dictionary[v]=newV
        return str(newV)
    def getV(self,v):
        if v in self.Dictionary:
            return self.Dictionary[v]
        else:
            return print("Not included")
    def addE(self,fr,to,cost=0):
        if fr not in self.Dictionary:
            self.addV(fr)
        self.Dictionary[fr].add

    def __iter__(self):
        return iter(self.Dictionary.values())

 

조금 복잡할지도 모르나 그래프 클래스의 내부 함수 addV가 Dictionary 내부에 키 쌍을 설정하는 메서드라 할 수 있다. 이를 이해하고 넘어가자. 그리고 내부 함수 addE가 노드의 연결에 해당한다고 할 수 있다. 다음의 코드 결과를 확인하여 벌텍스 생성과 연결을 이해하자.

 

코드 결과

 

조금 어렵지만 어떻게 알고리즘이 작용하는지 이해해보자!