[TIL] 103. [자료구조] 그래프

키워드

• 그래프
• 인접행렬/인접리스트

그래프

• 그래프는 기본적으로 vert(노드, 정점)와 edge(간선, 링크)로 구성되어있다.
• 그래프는 노드간의 관계, 트리는 노드간의 계층을 표현

1. 방향성(단방향, 양방향)

• 순서가 존재하기 때문에 마지막 노드가 Leaf node가 된다.

• 양방향 형태의 경우, 그 주목적이 노드간의 상호 교환(서로 노드 정보를 공유)

2. 무방향성
   

• 방향이 존재하지 않고 연결된 노드들(이웃 노드들)끼리 서로 인접

3. 순환성
   

• 그래프가 가질 수 있는 성질로, 위와 같이 순환을 형성할 수 있다.

[그래프] 인접리스트, 인접행렬

• 그래프 자료구조를 구현하는 두가지 방법

1. 인접리스트

• 그래프의 형태를 리스트로 표현
• 전체 노드의 목록을 저장하고 있다.

파이썬의 딕셔너리로 그래프를 구현한 예시)

class Graph:
    def __init__(self):
        self.vertices = {
                            1 : {2, 3, 4},  
                            2 : {3}, 
                            3 : {},    
                            4 : {3}
                        }

2. 인접행렬

• 행노드와 연결되는 열노드에 대해서 값이 1(즉, edge가 존재하는 경우)
• 노드 간 간선 가중치를 표현할 수 있다.(0이면 링크가 안되어있고, 그 외의 숫자면 가중치를 가지면서 연결)
• 행렬로 표현시 '노드값' 자체와 인덱스 사이에 연관성이 없다.

class Graph:
    def __init__(self):
        self.edges = [[0,1,1,1],
                      [0,0,1,0],
                      [0,0,0,0],
                      [0,0,1,0]]