그래프 알고리즘

 - 그래프 알고리즘

무방향 그래프와 방향성 그래프 

출처 : www.slideshare.net

무방향 그래프에서는 꼭지점 1에서 2의 변과 2에서 1의 변은 같다 

방향그래프에서는 서로 다른 변이다. 

방향그래프는 진입차수와 진출 차수로 구분한다. 

꼭지점을 n이라하고 변의 개수가 n(n-1)/2개이면 완전그래프라 한다.

 - 그래프 표현법

리스트형태로 저장

 적은 메모리 공간, 느림

행렬 저장

 많은 메모리 공간, 빠른

 - 탐색 방식

최대 꼭지점의 개수

방문한 노드를 표시하는 변수 

 - DFS

깊이 우선 탐색 방식

맨 아래까지 이동하면서 탐색

 - BFS

너비 우선 탐색

인접한 꼭지점을 바로 방문하는 방식

Queue를 만들어서 넣는 순서대로 방문