[C#] 재귀방식, list를 활용한 DFS 기본 형태

using System;
using System.Collections.Generic;

public class DFSExample {
    static void DFS(List<int>[] graph, int node, bool[] visited) { //인접 리스트, node 번호, visited 여부
        if (visited[node]) return; // 이미 방문한 노드면 종료

        Console.WriteLine("Visiting node: " + node);
        visited[node] = true; // 방문 처리

        foreach (var neighbor in graph[node]) {
            DFS(graph, neighbor, visited); // 재귀 호출
        }
    }

    public static void Main() {
        int n = 6; // 노드 개수
        List<int>[] graph = new List<int>[n]; // 인접 리스트 초기화
        for (int i = 0; i < n; i++) graph[i] = new List<int>();

        // 그래프 연결 정보 설정
        graph[0].AddRange(new int[] {1, 2});
        graph[1].AddRange(new int[] {0, 3, 4});
        graph[2].AddRange(new int[] {0});
        graph[3].AddRange(new int[] {1});
        graph[4].AddRange(new int[] {1, 5});
        graph[5].AddRange(new int[] {4});

        bool[] visited = new bool[n]; // 방문 체크 배열
        Console.WriteLine("DFS 탐색 시작:");
        DFS(graph, 0, visited); // 0번 노드부터 탐색 시작
    }
}

 

자세히 설명한 버전

using System;
using System.Collections.Generic;

public class DFSExample {
    // DFS 함수 (재귀 방식)
    static void DFS(List<int>[] graph, int node, bool[] visited) {
        if (visited[node]) return; // 이미 방문한 노드라면 종료

        Console.WriteLine("Visiting node: " + node); // 현재 방문한 노드 출력
        visited[node] = true; // 방문 표시

        // 현재 노드와 연결된 모든 이웃(인접 노드) 탐색
        foreach (var neighbor in graph[node]) {
            DFS(graph, neighbor, visited); // 재귀적으로 DFS 호출
        }
    }

    public static void Main() {
        int n = 6; // 그래프의 노드 개수
        List<int>[] graph = new List<int>[n]; // 인접 리스트 선언 (노드 개수만큼 배열 할당)

        // 각 노드에 대해 List 초기화 (리스트를 생성해야 사용 가능)
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }

        // 그래프의 연결 정보 추가
        graph[0].AddRange(new int[] {1, 2}); // 0번 노드와 1, 2번 노드 연결
        graph[1].AddRange(new int[] {0, 3, 4}); // 1번 노드와 0, 3, 4번 노드 연결
        graph[2].AddRange(new int[] {0}); // 2번 노드와 0번 노드 연결
        graph[3].AddRange(new int[] {1}); // 3번 노드와 1번 노드 연결
        graph[4].AddRange(new int[] {1, 5}); // 4번 노드와 1, 5번 노드 연결
        graph[5].AddRange(new int[] {4}); // 5번 노드와 4번 노드 연결

        bool[] visited = new bool[n]; // 방문 여부를 저장할 배열 (기본값 false)
        
        Console.WriteLine("DFS 탐색 시작:");
        DFS(graph, 0, visited); // DFS 시작 (0번 노드부터 탐색)
    }
}