[Python 자료구조 #그래프1] 그래프 용어, 인접 행렬/ 인접 리스트로 표현한 그래프

* 그래프(graph)

• 그래프는 연결된 객체들 사이의 관계를 표현할 수 있는 자료구조이다.
• 선형 자료구조들이나 트리도 그래프로 표현할 수 있기 때문에 그래프의 한 종류로 볼 수 있다.(그래프는 가장 일반화된 자료구조이다.)

 

* 그래프 이론(graph theory)

• 그래프와 관련된 다양한 문제를 연구하는 학문 분야
• 그래프는 수학자 오일러(Euler)에 의해 처음 창안되었다.

 

* 그래프 용어

• 정점(vertex) 또는 노드(node): 객체(object)
• 간선(edge) 또는 링크(link) : 객체간의 관계. 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
• G = (V, E) : 그래프의 수학적 표기법
• V(G) : 그래프 G의 정점들의 집합
• E(G) : 그래프 G의 간선들의 집합
• 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
• 정점의 차수(degree) : 그 정점에 연결된 간선의 수

* 무방향 그래프의 정점의 차수 : 모든 정점의 차수의 합 = 간선 수 x 2

* 방향 그래프의 정점의 차수 : 진입 차수의 합 또는 진출 차수의 합 = 간선의 수
1. 진입 차수(in-degree) : 외부에서 오는 간선의 수
2. 진출 차수(out-degree) :  그 정점에서 외부로 향하는 간선의 수

• 경로(path) : 간선을 따라 갈 수 있는 길
• 경로의 길이  : 경로를 구성하는데 사용된 간선의 수
• 단순 경로(simple path) : 경로 중에서 반복되는 간선이 없는 경로를 단순 경로라 함.
• 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 같은 경로

 

* 그래프 종류

• 무방향 그래프(undirected graph) : 간선에 방향이 표시되지 않은 그래프

 

V(G1) = {A, B, C, D}

E(G1) = {(A, B), (A, C), (A, D), (B, C), (C, D)}

 

 

 

• 방향 그래프(directed graph) : 간선에 방향성이 존재하는 그래프를 말한다.

 

 

V(G3) = {A, B, C}

E(G3) = {<A, B>, <B, A>, <B, C>}

 

 

 

• 가중치 그래프(weighted graph) 또는 네트워크(network) : 간선에 비용이나 가중치가 할당된 그래프. 
• 부분 그래프(subgraph) : 그래프 G를 구성하는 정점의 집합 V(G)와 간선의 집합 E(G)의 부분 집합으로 이루어진 그래프를 G의 부분 그래프라 한다.
• 연결 그래프(connected graph) : 모든 정점들 사이에 경로가 존재. 따로 떨어진 정점이 없다.
• 트리(Tree) : 사이클을 가지지 않는 연결 그래프. 연결 그래프에서 사이클이 없으면 그래프의 임의의 두 정점을 연결하는 경로는 오직 하나 뿐이다.
• 완전 그래프(complete graph) : 모든 정점 간에 간선이 존재하는 그래프. 무방향 완전 그래프의 정점 수를 n이라 하면 간선의 수는 n*(n-1)/2가 된다.

 

* 그래프의 추상 자료형(graph ADT)

• isEmpty(): 그래프가 공백 상태인지 확인한다.
• countVertex(): 정점의 수를 반환한다.
• countEdge(): 간선의 수를 반환한다.
• getEdge(u, v): 정점 u에서 정점v로 연결된 간선을 반환한다.
• degree(v): 정점 v의 차수를 반환한다.
• adjacent(v): 정점 v에 인접한 모든 정점의 집합을 반환한다.
• insertVertex(v): 그래프에 정점 v를 삽입한다.
• insertEdge(v): 그래프에 간선 (u, v)를 삽입한다.
• deleteVertex(v): 그래프의 정점 v를 삭제한다.
• deleteEdge(v): 그래프의 간선 (u, v)를 삭제한다.

 

* 인접 행렬(adjacency matrix)을 이용한 그래프 표현

• 그래프에서 정점들의 연결 관계를 표현한 행렬(matrix)
• 두 정점 사이에 간선이 없으면 0 또는 None을 갖는다.
• 간선이 있으면 1을 갖는다.
• 가중치 그래프라면 간선이 있는 성분을 그 가중치 값으로 표시한다.
• 보통 자체 간선(자신에게 출발해서 자신으로 들어오는 간선)을 허용하지 않으므로 대각선 성분은 모두 0으로 표시한다.

 

* 인접 리스트(adjacency list)을 이용한 그래프 표현

• 그래프의 각 정점과 연결된 인접 정점들을 각각의 리스트로 표현한 것
• 연결 리스트 혹은 배열 구조의 파이썬의 리스트를 사용할 수 있다.
•  

인접 리스트를 이용한 무방향 그래프 표현

인접 리스트를 이용한 방향 그래프 표현

 

 

* 인접 행렬과 인접 리스트의 복잡도 비교

출처 : 파이썬으로 쉽게 풀어쓴 자료구조