Graph (그래프) 정리

 👨🏼‍💻 Graph (그래프) 정리 With Python

🥝 Graph 란?

실제 세계의 현상이나 사물을 Vertex(정점)와 Edge(간선)로 표현하기 위해 사용합니다.

 

 

Vertex  : 위치를 말합니다. Node라고 하기도 합니다.

Edge    : 위치 간의 관계를 표시한 선입니다.

Degree : 방향이 없는 그래프에서 하나의 정점에 인접한 정점의 수입니다.

Simple Path : 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로입니다. (A-B-C는 Simple Path)

Cycle :  Simple Path의 시작 정점과 종료 정점이 동일한 경우입니다.

 

🍋 그래프의 종류

 

Undirected Graph

방향이 없는 그래프입니다.

Edge를 통해 Vertex 양 방향으로 갈 수 있습니다.

 

 

Directed Graph

방향이 있는 그래프입니다.

 

 

Weighted Graph

Edge에 비용 또는 가중치가 할당된 그래프입니다.

 

 

Connected Graph 또는 Disconnected Graph

 

Connected Graph

Undirected Graph에 있는 모든 노드에 대해 항상 경로가 존재하는 경우입니다.

 

Disconnected Graph

Undirected Graph에 있는 모든 노드에 대해 경호가 존재하지 않는 경우입니다.

 

위 그래프는 Disconnected Graph입니다.

 

 

Complete Graph

그래프의 모든 노드가 서로 연결되어 있는 그래프입니다.

 

🍊 Graph 구현 With Python

파이썬에서 제공하는 딕셔너리와 리스트 자료구조를 활용해서 그래프를 쉽게 표현할 수 있습니다.

위 그래프를 코드로 구현해 봅시다.

 

graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

print (graph) 실행 결과

 

{ 'A': ['B', 'C'],

'B': ['A', 'D'],

'C': ['A', 'G', 'H', 'I'],

'D': ['B', 'E', 'F'],

'E': ['D'], 'F': ['D'],

'G': ['C'],

'H': ['C'],

'I': ['C', 'J'],

'J': ['I'] }