Graph 그래프 이론

 

Graph
-> 링크드리스트, 트리 둘다 포함
-> vertex (노드) 와 edge (연결방향)으로 구성
-> E <= V^2

 

 

 

그래서,

Tree와 linked list 는 방향성 있는 그래프(directed Graph) 라고 할 수 있고

 

방향성 없는 그래프(Undirected Graph) 라는 의미는,

= 즉, 양방향 모두 갈수 있다는 의미

= 양방향 에지(간선)

=> matrix 행렬 또는 adjacency list 인접 리스트 를 사용해서 문제 품!!

 

1. 행렬(Matrix) 문제는?

# Matrix (2D Grid)
grid = [[0, 0, 0, 0],
        [1, 1, 0, 0],
        [0, 0, 0, 1],
        [0, 1, 0, 0]]

 

0: Free

1: Blocked

 

위에서 아래로 행 = row 로우, index 는 0부터 시작

왼쪽에서 오른쪽 열 = colum 컬럼 , index 는 0부터 시작

 

 

 

2. Adjancency Matrix 인접 행렬 문제는?

vertex (노드)의 개수 만큼 행렬 만듦

→ 노드 개수가 3개면, 행렬은 3x3

→ 노드 개수가 4개면, 행렬은 4x4

# Adjacency matrix
adjMatrix = [[0, 0, 0, 0],
             [1, 1, 0, 0],
             [0, 0, 0, 1],
             [0, 1, 0, 0]]

 

r 버텍스에서 c 버텍스로 가는 drection (에지, 간선)이 있으면 1

adjMatrix[1][0] = 1 : from vertex 1 to vertex 0

adjMatrix[2][3] = 1 : from vertex 2 to vertex 3

adjMatrix[3][0] = 0 : from vertex 3 to vertex 0

 

 

그러나, 인접 행렬을 사용하면, 0을 가지는 행렬이 많으므로, 메모리가 너무 낭비됨

=> 따라서, 인접 리스트를 사용하여, 문제를 품!

3. Adjancency List 인접리스트 문제는?

# GraphNode used for adjacency list
class GraphNode:
    def __init__(self, val):
        self.val = val
        self.neighbors = []

 

 

self.val = 현재 노드 번호

self.neighbors = [현재 노드가 가리키는 노드, ...]

 

예를 들면

노드 3이면 self.val = 3, self.neighbors = [GraphNode(1)]