[11] Graph, 그래프

어쨌든 계획한 목록에서는 마지막 챕터이다. 그래프!!!!!!!!!!!!!! 오늘의 짤은 따로 없을 예정 하하 

그래프도 참 나를 괴롭게했지...하...(기싫다)....

 

그림 출처 :https://python.plainenglish.io/graph-data-structure-theory-and-python-implementation-ee8c9795eae7

---

✅ 그래프란 

Vertices : 정점 / Edge : 간선

그래프(Graph)란 정점과 간선으로 이루어진 자료구조이다.

이전에 배웠던 트리(노드와 간선)도 그래프의 일종인데 사실 트리가 별종이다. 

 

 

다만, 트리와 그래프의 차이점이라면 다음과 같다.

1. 트리에는 루트 노드가 명백히 존재하지만, 그래프는 그런 거 없다.
2. 트리는 루트에서 리프 노드로 뻗어가는 단방향 경로만 존재하지만, 그래프는 단방향 & 양방향 둘 다 가능하다.
3. 트리는 단방향 경로만 존재해 루프가 존재할 수 없지만, 그래프는 존재할 수 있다. (오른쪽 그림에서 D-E-F-G-H : 루프)

 

 

✅ 그래프 구성요소 

Vertices : 정점 / Edge : 간선

그래프(G)는 (V, E)로 나타낸다. 

V : 정점의 집합, E : 간선(정점을 연결하는 선)의 집합

 

 

✅ 그래프 종류 

 

1. 무방향 그래프 (Undirected Graph) : 간선들이 방향을 가지고 있지 않음 (양방향)
2. 방향 그래프 (Directed Graph) : 간선들이 방향을 가지고 있음 (A -> B, 한쪽 방향)
3. 가중치 그래프 (Weighted Graph) : 간선들이 가중치를 가지고 있음 ( 무방향, 방향 그래프 모두 가능)

 

 

✅ 그래프 구현 

그래프를 구현하는 방법에는 2가지가 있다.

 

1. 인접 행렬 (Adjacency Matrix)
2. 인접 리스트 (Adjacency List)

 

1. 인접 행렬

무방향 그래프의 인접 행렬

 

방향 그래프의 인접 행렬

 

인접 행렬은 이중 배열로 구현한다. 무방향 그래프와 방향 그래프의 차이점은 조금만 자세히 살펴보면 알 수 있다. 

바로 오른쪽 배열 그림에서의 1의 갯수이다.

A -> B 일때 무방향 그래프는 [A,B] = [B,A] = 1이지만, 방향 그래프에서는 [A,B] = 1, [B,A] = 0이 된다. 

 

# 무방향 그래프 인접 행렬 구현
class Adjacency_Matrix:
    def __init__(self, vertices):
        self.vertices = vertices
        self.graph = [[0 for j in range(self.vertices)] for i in range(self.vertices)]
    
    def addEdge(self, v1, v2):
        self.graph[v1][v2] = 1
        self.graph[v2][v1] = 1
    
    def printGraph(self):
        for row in range(self.vertices):
            for column in range(self.vertices):
                print(self.graph[row][column], end=' ')
            print('')


Und# 방향 그래프 인접 행렬 구현
class Adjacency_Matrix:
    def __init__(self, vertices):
        self.vertices = vertices
        self.graph = [[0 for j in range(self.vertices)] for i in range(self.vertices)]
    
    def addEdge(self, v1, v2):
        self.graph[v1][v2] = 1
    
    def printGraph(self):
        for row in range(self.vertices):
            for column in range(self.vertices):
                print(self.graph[row][column], end=' ')
            print('')

 

인접 행렬의 경우, 정점간의 간선 존재여부를 O(1) 복잡도만에 알 수 있다. 전체의 간선들을 탐색할 경우 O(N^2) 시간이 걸리지만, 간선이 없을 경우의 공간이 낭비되기 때문에 공간복잡도 면에서는 비효율적이다.

 

2. 인접리스트

 

인접 리스트는 정점의 집합, 간선의 집합, 정점 & 간선의 집합 -> 그래프 이렇게 세 파트로 나누어서 순차적으로 이해하는게 좋다.

 

위의 그림에서 정점의 집합, 간선의 집합은 아래와 같다.

정점의 집합 : vertices = [1, 2, 3, 4, 5]

간선의 집합 : edges = [[1,2], [1,3], [1,4], [2,3], [3,2], [4,4], [5,2]]

 

그래프는 다음과 같이 나타낼 수 있다.

graph = [ [2,3,4], [3], [2],[4], [2] ] 

이것은 아래와 같이 edges = [[1,2], [1,3], [1,4], [2,3], [3,2], [4,4], [5,2]] 의 시작 정점을 묶어서 나타낸 형태이다. 

 

 

vertices = ['1','2','3','4','5']
edges = [[1,2],[1,3],[1,4],[2,3],[3,2],[4,4],[5,2]]

graph = [[] for vertex in vertices]

for edge in edges:
    graph[edge[0]-1].append(edge[1])

 

인접리스트는 edge만큼의 배열을 사용한다는 점에서, 공간복잡도는 행렬보다 효율적이다.