[자료구조] 그래프(Graph) (Python)

1. 기본 구조와 용어

출처: 위키백과

• 그래프(Graph): 노드(Node)와 간선(Edge)로 실제 세계 현상이나 사물을 표현하는 자료구조

 

• 노드(Node): 위치
• 간선(Edge): 위치간의 관계를 표시한 선

 

2. 그래프(Graph) 종류

[무방향 그래프(Undirected Graph)]

• 방향 X
• 간선을 통해 양방향으로 움직일 수 있음

 

[방향 그래프(Directed Graph)]

• 방향 O
• 간선을 통해 정해진 방향으로 움직임

 

[가중치 그래프(Weighted Graph)]

• 간선에 가중치가 할당

 

[사이클(Cycle) & 비순환 그래프(Acyclic Graph)]

• 사이클(Cycle): 단순 경로의 시작 노드와 종료 노드가 동일
• 비순환 그래프(Acyclic Graph): 사이클이 없는 그래프

#'단순': 경로나 사이클에서 같은 정점을 두 번 이상 방문하지 않음

출처: ResearchGate

 

[완전 그래프(Complete Graph)]

• 그래프의 모든 노드가 서로 연결되어 있음