그래프의 탐색 : DFS,BFS

그래프의 모든 노드를 탐색하는 방법으로 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)이 있다.

• DFS는 스택을, BFS는 큐를 사용하여 각각 구현한다.

⚽ 인접 행렬과 인접 리스트

그래프의 노드를 탐색하기 위해서는 노드간 간선에 의해 연결된 인접한 노드 정보가 필요하며 이 정보들을 행렬(2차원 리스트) 또는 리스트 형태로 저장하여 사용한다.

🎈 인접 행렬은 불필요한 정보까지 저장하게 되어 메모리를 낭비하게 되지만 원하는 관계정보를 빠르게 조회할 수 있다.

🎈 인접 리스트는 메모리의 낭비는 없지만 원하는 관계 정ㅈ보를 조회하기 위해 선형으로 조회해야 하기 때문에 속도가 비교적 떨어질 수도 있다.

어떨때 사용해야 하는가?

그렇기에 인접 행렬의 경우 문제에서 그래프 전체를 주어지고 구분해야할 경우에 무조건 인접행렬을 통해 풀어야 할 것이다.

• 알아서 문제에서 그래프 전체에 대한 설명 또는 그림을 주어주면 그때는 인접행렬로 푸는게 맞아.

반면에 인접리스트는 그래프 전체가 주어지지 않고 현재 노드로부터 인접 노드들만 주어지는 것을 확인할 수 있다면 인접리스트로 풀면 된다.