그래프
in Algorithms
그래프 기초
그래프 G : 그래프 G는 (V,E)의 쌍이다.
- v는 정점(vertext)의 집합, E는 간선(edge)의 집합.
- a directed graph
- 화살표가 있는 그래프
- 각 간선은 한 정점을 떠나 다른 한 정점으로 들어간다.(자기 자신 포함)
- 보통 각 정점은 숫자나 이름으로 구분 V={1,2,3,4,5}
- 각 간선은 간선이 떠나고 도착하는 정점의 쌍을 순서대로 적음. E={(1,2).(2,2),(2,4)}
- an undirected graph
- 화살표가 없는 그래프
- 간선 방향이 없으므로 직전표현.
- (2,4)=(4,2)다.
- 인접하다
- undirected graph에서는 연결만 되있으면 인접하다고 한다.
- directed graph는 화살표 방향이 중요한데, a–>b 라고 치면, a는b에 인접하지만 b는 a에 인접하지 않다.
- 차수
- out-degree : 어떤 정점을 기준으로 나가는 간선의 수
- in-degree : 어떤 정점을 기준으로 들어오는 간선의 수
- degree = 위 둘을 합친 것 (out-degree+in-degree)
- 경로
- 정점 u로부터 정점 v까지의 경로는 정점의 순서다
- 단순경로 : 경로에 있는 모든 정점들이 서로 다른 경우
- 비순환 그래프 : 순환이 없는 그래프
- 연결 그래프 : 정점의 모든 쌍이 경로를 가지는 무방향성 그래프
- 연결 요소 : 무방향성 그래프에서 정점들이 최대한 연결되어있는 하위 그래프-
- 강한 연결 : 방향성 그래프에서 정점의 각 쌍이 서로 도달 가능하면 강하게 연결돼있다라고 함
- 강한 연결 요소 : 방향성 그래프에서 최대한 많은 정점을 강하게 연결한 하위 그래프
완전 그래프 : 무방향성 그래프에서 모든 정점의 쌍이 서로 인접한 경우
- 포레스트 : 순환하지 않는 무방향성 그래프
- 트리 : 포레스트가 연결되어있는 경우 (무방향성, 연결, 사이클이 없다)
- 그래프 G에서 어떤 두 정점들도 단일 단순 경로로 연결
- G가 연결되어있을 때 어떤 간선을 제거하면, G는 더이상 연결되지 않음
G가 연결되어있고 비순환이면 E = V -1 - G가 비순환일 때, 간선 하나 추가하면 순환
- 그래프에서 간선의 개수
방향성 그래프 : E <= V **2 비방향성 그래프 : E <= V ( V -1)/2
그래프 표현
인접 리스트 표현
방향성 그래프를 인접 리스트로 표현하기
비방향성 그래프를 인접 리스트로 표현하기
간선을 찾는데 걸리는 시간 : O(v) , 모든 간선을 찾거나 방문하는 시간 : Θ(v+e)
인접 행렬 표현
- 두 정점 i와 j를 잇는 간선이 있다면 행렬의 (i,j)는 1, 아니면 0
- 비방향성 그래프를 저장할 때는, 어차피 하위 삼각행렬이 상ㅎ위 삼각행렬과 같기 때문에 하위 삼각행렬을 저장한다. 그래서 v^2/2의 공간만 사용.
- 간선을 찾는데 걸리는 시간 : Θ(1) , 모든 간선을 찾거나 방문하는 시간 : Θ(v**2)
가중 그래프
- 간선이 숫자로 표현되는 값을 가지는 그래프
- 인접 리스트에서는 정점 외 간선의 값 추가 저장
- 인접 매트릭스에서는 1과 0으로 하는게 아니라 간선값을 매트릭스에 넣어주면 된다.
