[바킹독의 실전 알고리즘] 0x18 그래프

정의

 

그래프 = 정점과 간선으로 이루어진 자료구조

 

간선 = Edge, 정점(Vertex/Node), 차수 (degree) = 3

차수는 각 정점에 대해서 간선으로 연견될 이웃한 정점의 갯수

 

원소사이의 관계를 나타낼 때 잘 쓰이는 자료구조

 

그래프의 간선에는 방향성 존재

방향이 없다면 무방향 그래프, 있따면 방향 그래프

나가면 outdegree 진출차수

들어오면 indegree 진입차수

 

 

사이클, 임의의 한 점에서 출발해 자기 자신으로 돌아올 수 있는

경로를 사이클이라 한다. 하나라도 있으면 순환 그래프

없으면 비순환 그래프.

 

모든 서로 다른 두 정점 쌍이 간선으로 연결된 그래프가 완전 그래프

임의의 두 저점 사이에 경로가 항상 존재하는 그래프는 연결 그래프

 

 

단순 그래프 : 두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프

한 저엄에서 출발해 그 정점으로 돌아오는걸 루프라고 한다. 연결되어 있다. 

두 정점 사이의 간선은 최대 1개 존재한다. 같은 간선은 한 번만 주어진다.

간선의 두 정점 서로다르다, 등등 엄밀하게 주어진다. 이런 조건 없으면 여러 그래프에서 성립되게 만들어야 해

 

 

표현법 - 인접 행렬

표현법 - 인접 리스트

공간을 절약하 ㄹ수 있으며 인접 행렬 못 쓸 때 유용할 수 있어

1에서 갈 수 있는거  

 

	인접 행렬	인접 리스트
공간 복잡도	O(V^2)	O(V+E)
정점 u, v가 연결되어 있는지 확인하는 시간 복잡도	O(1)	O(min(deq(u), deq(v))
정점 v와 견결된 모든 정점을 확인하는 시간 복잡도	O(V)	O(deq(v))
효율적인 상황	두 점의 연결여부를 자주 확인할 때  E가 V^2에 가까울 때	특정 정점에 연결된 모든 정점을 자주 확인 할 때 E가 V2보다 훨씬 작을 떄

 

 

BFS = 그래프에서 너비를 우선으로 방문하는 알고리즘