📌DFS 깊이 우선 탐색
그래프/트리 탐색 기법중 하나이다.
한 정점(Vertext)에서 연결되어있는 다른 정점으로 갈 때 한 분기의 가장 깊숙한 곳 까지 탐색하고 다시 돌아와 다른 분기를 탐색하는 기법이다.
특징
- 자기 자신을 호출하는 순환 알고리즘 형태를 가지고 있다.
- 어떤 노드를 탐색했는지 검사를 반드시 해야한다.
- 하지 않았을 때 무한 루프에 빠질 수 있다.
구현 코드
class Graph
{
private int _nodeCount;
private List<int>[] _adj;
public Graph(int nodeCount)
{
_nodeCount = nodeCount;
_adj = new List<int>[nodeCount];
for (int i = 0; i < nodeCount; i++)
_adj[i] = new List<int>();
}
public void AddEdge(int v, int edge)
{
_adj[v].Add(edge);
}
public void DFS(int startNode)
{
bool[] visited = new bool[_nodeCount];
DFSUtil(startNode, visited);
}
private void DFSUtil(int v, bool[] visited)
{
visited[v] = true;
List<int> nodes = _adj[v];
foreach (int i in nodes)
if (!visited[i])
DFSUtil(i, visited);
}
}
위 그림과 같은 구조를 가지는 그래프에서 DFS를 구현하면 다음과 같이 된다.
static void Main()
{
Graph graph = new Graph(6);
graph.AddEdge(0, 1);
graph.AddEdge(0, 3);
graph.AddEdge(1, 0);
graph.AddEdge(1, 2);
graph.AddEdge(1, 3);
graph.AddEdge(2, 1);
graph.AddEdge(2, 4);
graph.AddEdge(3, 0);
graph.AddEdge(3, 1);
graph.AddEdge(3, 5);
graph.AddEdge(4, 2);
graph.AddEdge(5, 3);
}
그리고 DFS 시작을 0번 정점부터 한다고 하면
graph.DFS(0);
다음과 같은 순서로 진행이 된다.
'자료구조 알고리즘' 카테고리의 다른 글
이진 탐색 (C#) (0) | 2024.05.27 |
---|---|
선형 탐색 (C#) (0) | 2024.05.19 |
선택정렬 (C#) (0) | 2024.05.19 |
버블정렬 (C#) (0) | 2024.05.19 |
(C#) BFS (0) | 2024.05.12 |