[Python] 그래프(Graph)

그래프(Graph)

그래프(Graph)의 기본

그래프의 개념

• 그래프(Graph) : 여러 노드가 서로 연결된 자료구조
• 루트에서 하위 노드 방향으로만 이어지는 트리와 달리, 여러 노드가 연결되어 있을 수 있다.
• 트리도 그래프의 일종이지만, 트리와 그래프를 구현하는 코드 등이 확연히 다르기 때문에 이 둘은 별도로 생각하는 편이 낫다.

트리(왼쪽)와 그래프(오른쪽)

 

그래프의 종류

• 그래프는 정점을 연결하는 간선의 방향성 여부에 따라 방향 그래프와 무방향 그래프로 나눈다.
• 간선에 가중치(Weight)를 부여하여 가중치 그래프도 만들 수 있다.

 

무방향 그래프

• 트리의 노드(Node)에 해당하는 용어가 그래프에서는 정점(Vertex)이다.
• 정점을 연결하는 선은 간선(Edge)이므로 그래프는 정점과 간선의 집합으로 볼 수 있다.

무방향 그래프 형태

 

• 그래프에서 정점은 Vertex의 V로, 간선은 Edge의 E로, 그래프는 Graph의 G로 표기한다.
• 따라서 정점 집합을 V(G)로, 간선 집합을 E(G)로 표기한다.

V(G1) = { A, B, C, D }
V(G2) = { A, B, C, D }

 

• 무방향 그래프의 간선은 연결하는 두 정점을 ( ) 괄호로 표현한다.
  • 정점 A와 B의 간선을 (A, B)로 표현한다.

E(G1) = { (A, B), (A, C), (A, D), (B, C), (C, D) }
E(G2) = { (A, B), (B, D), (D, C) }

 

방향 그래프

• 방향성이 있는 그래프는 화살표로 간선 방향을 표기하고, 그래프의 정점 집합이 무방향 그래프와 같다.

방향 그래프의 형태

V(G1) = { A, B, C, D }
V(G2) = { A, B, C, D }

 

• 방향 그래프의 간선은 연결하는 두 정점을 < >로 묶어 표현한다.
  • 정점 A와 B의 간선을 <A, B>로 표현한다.
• 그리고 방향성이 있어 <A, B>와 <B, A>는 서로 다른 간선이다.

E(G1) = { <A, B>, <A, C>, <D, A>, <D, C> }
E(G2) = { <A, B>, <C, B>, <C, D> }

 

가중치 그래프

• 간선 마다 가중치가 다르게 부여된 그래프를 가중치 그래프(Weight Graph)라고 한다.

무방향 가중치 그래프와 방향 가중치 그래프

 

깊이 우선 탐색(Depth First Search, DFS)

• 그래프 순회(Graph Traversal) : 그래프의 모든 정점을 한 번씩 방문하는 것
• 그래프 순회 방식
  • 깊이 우선 탐색(Depth First Search, DFS)
  • 너비 우선 탐색(Breath First Search, BFS)

 

깊이 우선 탐색의 예

• 그래프는 트리와 달리 부모와 자식 개념이 없으므로, 어떤 정점에서 시작해도 결과는 같다.

 

• 모든 노드를 방문한 것처럼 보이지만, 그래프는 정점마다 연결된 선이 여러 개 있을 수 있기 때문에 반드시 시작 정점까지 돌아가야 한다.

 

그래프의 인접 행렬 표현

• 그래프를 코드로 구현할 때는 일반적으로 인접 행렬(Adjacent Matrix)을 사용한다.
• 인접 행렬은 정방향으로 구성된 행렬로, 정점이 4개인 그래프는 4×4 인접 행렬로 표현한다.
• 출발점과 도착점이 연결되었다면 1로, 연결되지 않았다면 0으로 표시한다.
• 출발점과 도착점이 같은 자기 자신은 모두 0으로 표시된다.

 

무방향 그래프의 인접 행렬

 

• 무방향 그래프의 인접 행렬은 대각선을 기준으로 서로 대칭된다.

 

방향 그래프의 인접 행렬

 

• 방향 그래프는 무방향 그래프와 달리 대각선을 기준으로 대칭되지 않는다.
  • 도착점과 출발점이 대칭되지 않아 <A, B>는 <B, A>와 다르다.

 

그래프의 구현

 

① 그래프의 정점 생성

class Graph :
    def __init__(self, size) :
        self.SIZE = size
        self.graph = [[0 for _ in range(size)] for _ in range(size)]

G1 = Graph(4)

 

② 그래프의 정점 연결

G1.graph[0][1] = 1     # (A, B) 간선
G1.graph[0][2] = 1     # (A, C) 간선
G1.graph[0][3] = 1     # (A, D) 간선

 

G1.graph[1][0] = 1    # (B, A) 간선
G1.graph[1][2] = 1    # (B, C) 간선

 

G1.graph[2][0] = 1    # (C, A) 간선
G1.graph[2][1] = 1    # (C, B) 간선
G1.graph[2][3] = 1    # (C, D) 간선


G1.graph[3][0] = 1    # (D, A) 간선
G1.graph[3][2] = 1    # (D, C) 간선

 

구현 : 무방향 그래프

class Graph() :
    def __init__ (self, size) :
        self.SIZE = size
        self.graph = [ [0 for _ in range(size)] for _ in range(size) ]

G1, G3 = None, None

G1 = Graph(4)
G1.graph[0][1] = 1; G1.graph[0][2] = 1; G1.graph[0][3] = 1
G1.graph[1][0] = 1; G1.graph[1][2] = 1
G1.graph[2][0] = 1; G1.graph[2][1] = 1; G1.graph[2][3] = 1
G1.graph[3][0] = 1; G1.graph[3][2] = 1

print('## G1 무방향 그래프 ##')
for row in range(4) :
    for col in range(4) :
        print(G1.graph[row][col], end=' ')
    print()

G3 = Graph(4)
G3.graph[0][1] = 1; G3.graph[0][2] = 1
G3.graph[3][0] = 1; G3.graph[3][2] = 1

print('## G3 방향 그래프 ##')
for row in range(4) :
    for col in range(4) :
        print(G3.graph[row][col], end=' ')
    print()

## G1 무방향 그래프 ##
0 1 1 1 
1 0 1 0
1 1 0 1
1 0 1 0
## G3 방향 그래프 ##
0 1 1 0
0 0 0 0
0 0 0 0
1 0 1 0

 

그래프 개선

• 무방향 그래프를 인접 행렬로 구성할 때 0, 1, 2, ... 숫자로 구성했다.
• 하지만, 실제 그래프는 사람 이름, 도시 이름 등으로 구성하기도 한다.

 

• 변수 이름을 정점 번호로 지정하면 더 직관적이다.
• 변수 이름은 한글도 지원된다.

문별, 솔라, 휘인, 쯔위 = 0, 1, 2, 3
G1.graph[문별][솔라] = 1; G1.graph[문별][쯔위] = 1
G1.graph[솔라][문별] = 1; G1.graph[솔라][쯔위] = 1

 

• 주석을 추가하여 그래프를 표현할 수 있다.

nameAry = ['문별', '솔라', '휘인', '쯔위', '선미', '화사']
print('\t', end = '')
for v in range(g.SIZE) :
    print(nameAry[v], end = '\t')
print()
for row in range(g.SIZE) :
    print(nameAry[row], end = '\t')
    for col in range(g.SIZE) :
        print(g.graph[row][col], end= '\t')
    print()
print()

 

구현 : 개선된 무방향 그래프

class Graph() :
    def __init__ (self, size) :
        self.SIZE = size
        self.graph = [[0 for _ in range(size)] for _ in range(size)]

def printGraph(g) :
    print('\t', end = '')
    for v in range(g.SIZE) :
        print(nameAry[v], end = '\t')
    print()
    for row in range(g.SIZE) :
        print(nameAry[row], end = '\t')
        for col in range(g.SIZE) :
            print(g.graph[row][col], end= '\t')
        print()
    print()


G1 = None
nameAry = ['문별', '솔라', '휘인', '쯔위', '선미', '화사']
문별, 솔라, 휘인, 쯔위, 선미, 화사 = 0, 1, 2, 3, 4, 5


gSize = 6
G1 = Graph(gSize)
G1.graph[문별][솔라] = 1; G1.graph[문별][휘인] = 1
G1.graph[솔라][문별] = 1; G1.graph[솔라][쯔위] = 1
G1.graph[휘인][문별] = 1; G1.graph[휘인][쯔위] = 1
G1.graph[쯔위][솔라] = 1; G1.graph[쯔위][휘인] = 1; G1.graph[쯔위][선미] = 1; G1.graph[쯔위][화사] = 1
G1.graph[선미][쯔위] = 1; G1.graph[선미][화사] = 1
G1.graph[화사][쯔위] = 1; G1.graph[화사][선미] = 1

print('## G1 무방향 그래프 ##')
printGraph(G1)

## G1 무방향 그래프 ##
        문별    솔라    휘인    쯔위    선미    화사
문별    0       1       1       0       0       0
솔라    1       0       0       1       0       0
휘인    1       0       0       1       0       0
쯔위    0       1       1       0       1       1
선미    0       0       0       1       0       1
화사    0       0       0       1       1       0