그래프(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는 끝을 모르기 때문에 크기 지정해야 한다. (간선갯수 저장변수 필요)
보통 인접리스트 많이쓴다(간선정보니까!, 간선중심알고리즘일때
'개발일기 > Python' 카테고리의 다른 글
[Python] - 축소정복 (0) | 2023.04.24 |
---|---|
[Python] 알고리즘 - 완전탐색 (0) | 2023.04.24 |
[Python] 알고리즘 효율성 분석 (0) | 2023.04.24 |
[Python] 알고리즘 - 최대 공약수 구하기(유클리드 알고리즘) (0) | 2023.03.14 |
[Python] 알고리즘 - 최대값찾기 (0) | 2023.03.14 |