[Python] 기본적인 자료구조 - 그래프(Graph)

그래프(graph)

- 현상이나 사물을 정점 vertex(node)와 간선edge로 표현한것

Graph G = (V,E)

V : 정점집합

V : 간선집합

- 두 정점이 간선으로 연결되어 있으면 인접 adjacent하다고 한다.= 이웃관계에 있다고 표현하기도 한다. 

 

* 그래프의 종류

- 무방향성 그래프

: 간선에 방향이 없는 그래프

정점표현 = {A,B,C,D}

간선표현 = { (A,B) , (C,D) }

- 방향성 그래프

: 간선에 방향이 있는 그래프

정점표현 = {A,B,C,D}

간선표현 = { <A,B> , <C,D> }

<A,B> ≠ <B,A>

가중치 그래프

: 간선마다 가중치가 다르게 부여된 그래프

- 간선에 방향이 없는 그래프

- 간선에 방향이 있는 그래프

 

그래프 표현법

- 그래프는 정점의 집합과 간선의 집합의 결합

    -> 그래프를 표현하는 문제는 정점의 집합과 간선의 집합의 표현문제로 간선은 정점과 정점이 "인접"관계에 있음을 나타낸다. 

    -> 그래프의 표현문제는 "간선, 즉 정점과 정점의 인접관계를 어떻게 나타내는가?"의 문제로 귀결

※ 행렬을 이용하는 방식 : 인접행렬

: 정점끼리의 인접관계를 나타내는 행렬

그래프의 정점의 수가 N이라면 N X N 크기의 행렬

정점 사이 간선이 존재하면 1로 표시, 아니면 0으로 표시 

==> 모든간선이 양방향인 그래프 = 무방향그래프(대칭이다)

* 가중치그래프일 경우, 1대신에 가중치 값을 가진다.

장점 : 이해하기 쉽고, 간선 존재여부를 즉각 알 수 있다

단점 : N^2에 비례하는 공간빌표(N은 정점수), 행렬의 모든 우너소 채우는데에만 N^2에 비례하는 시간 필요

간선의 밀도가 높은 그래프에서는 유리! ==> 정점이 100만개인데 간선이 200만개 밖에 없다면?

(간선이 별로 없는데, 정점많은 그래프는 비효율이라는것)

 

※ 리스트를 이용하는 방식 : 인접리스트

: 그래프 내의 각 정점의 인접관계를 표현하는 리스트

- N개의 리스트(연결리스트 또는 배열)로 표현

- i번째 리스트는 정점 i에 인접한 정점들을 리스트로 연결

- 가중치 있는 그래프의 경우 : 리스트에 가중치도 보관

 

* 무향그래프에서는 총 간선 수의 두 배의 항목으로 필요

--> 간선 : 8개, 노드의 갯수 2*8 = 16 개가 필요

* 유향그래프에서는 간선 하나당 항목 하나씩 필요

--> 간선 : 8개, 노드의 갯수 8개가 필요

* 가중치 그래프

: <정점번호, 가중치>로 노드가 구성되어있다. 

 

장점 : 간선 총 수에 비례하는 양만큼만 필요(무향은 2배 유향은 1배)

         모든 가능한 정점 쌍에 비해 간선 수가 적을 때 유리

단점 : 거의 모든 정점에 간선이 있으면 구조적 접근 비효율성(Linked구현일 경우 메모리에서도 손해, 오버헤드)

          정점 i와 j간에 간선이 있는 지 알아볼 때 시간이 많이 걸림

LinkedLists는 끝을 알 수 있다, ArrayList는 끝을 모르기 때문에 크기 지정해야 한다. (간선갯수 저장변수 필요)

보통 인접리스트 많이쓴다(간선정보니까!, 간선중심알고리즘일때