그래프 탐색 알고리즘 [알고리즘]

DFS

DFS(Depth-First Search) : 깊이 우선 탐색. 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘.
스택 자료구조를 사용하여 가장 깊은 노드를 방문 후 다시 돌아가 다른 경로를 탐색.

1. 탐색 시작 노드를 스택에 삽입, 스택에 삽입되었음을 체크하는 방문 처리(노드가 다시 스택에 삽입되지 않도록).
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없다면 스택의 최상단 노드를 꺼냄(스택에서 제거).
3. 2번의 과정을 반복

-그래프 : 노드와 간선으로 이루어진 데이터의 형태. 인접 행렬과 인접 리스트로 표현할 수 있다.

인접 행렬

• 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현

  adj[i][j] : 노드 i에서 노드j 로 가는 간선이 있으면 1, 없으면 0
  adj[i][j] : 노드 i에서 노드 j로 가는 간선의 가중치의 값, 없으면 무한

모든 관계를 저장하기 때문에 노드 개수가 많을수록 메모리가 낭비됨.

인접 리스트

• 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현
  노드와 연결되 노드에 대한 정보를 연결하여 저장
  연결 리스트 자료구조를 사용

graph[i].append((연결된노드, 거리))
graph[i].append((연결된노드2, 거리))

인접 행렬 방식에 비해 특정 노드의 관계에 대한 정보를 얻는 속도가 느림.

BFS

BFS (Breadth First Search) : 너비 우선 탐색. 그래프의 가까운 노드부터 탐색하는 알고리즘.
큐(선입선출) 자료구조를 사용하여 가까운 노드부터 탐색.

1. 탐색 시작 노드를 큐에 삽입하고 방문처리.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리.
3. 2번 과정을 반복