[c#] 깊이 우선 탐색, 너비 우선 탐색

그래프 노드 클래스 예시

    public class Graph
    {
        public class Node
        {
            public int data;
            public List<Node> adjacent;
            public bool marked;

            public Node(int data)
            {
                this.data = data;
                this.marked = false;
                this.adjacent = new List<Node>();
            }
        }

        Node[] nodes;
        public Graph(int size)
        {
            nodes = new Node[size];
            for(int i = 0; i < size; i++)
            {
                nodes[i] = new Node(i);
            }
        }

        public void addEdge(int index1, int index2)
        {
            var node1 = nodes[index1];
            var node2 = nodes[index2];
            if (false == node1.adjacent.Contains(node2))
            {
                node1.adjacent.Add(node2);
            }
            if (false == node2.adjacent.Contains(node1))
            {
                node2.adjacent.Add(node2);
            }
        }
	}

 

DFS (깊이 우선 탐색)

자식의 자식 마지막 자식까지 가면서 검색하는 방법

스택을 이용, 재귀 함수를 이용

단순 검색 속도는 BFS 보다 느림.

조합류 최단거리로 최단 거리로 갈 수 있는 경로의 수, 목적지 도달 여부 구하는곳에 쓰임

 

		// 스택을 이용한 dfx
        public void dfs(int index)
        {
            Node root = nodes[index];
            Stack<Node> stack = new Stack<Node>();
            stack.Push(root);
            root.marked = true;

            while(stack.Count > 0)
            {
                var node = stack.Pop();
                for(int i = 0; i < node.adjacent.Count; i++)
                {
                    var adjacentNode = node.adjacent[i];
                    if (adjacentNode.marked == false)
                    {
                        adjacentNode.marked = true;
                        stack.Push(adjacentNode);
                    }
                }
                Console.Write(node.data + ",");
            }
        }

        // 재귀함수를 이용한 dfx
        public void dfs_recursive(int index)
        {
            dfs_recursive(nodes[index]);
        }
        public void dfs_recursive(Node node)
        {
            node.marked = true;
            Console.Write(node.data + ",");

            for (int i = 0; i < node.adjacent.Count; i++)
            {
                var adjacentNode = node.adjacent[i];
                if (adjacentNode.marked == false)
                {
                    dfs_recursive(adjacentNode);
                }
            }
        }

BFS (너비 우선 탐색)

레벨 단위로 검색하는 방법

큐를 이용

최단 경로, 임의의 경로를 찾을때 사용

최단거리, 최소 획수 구하는 곳에 쓰임

		// 큐를 이용한 bfs
        public void bfs(int index)
        {
            Node root = nodes[index];
            Queue<Node> queue = new Queue<Node>();
            queue.Enqueue(root);
            root.marked = true;

            while (queue.Count > 0)
            {
                var node = queue.Dequeue();
                for (int i = 0; i < node.adjacent.Count; i++)
                {
                    var adjacentNode = node.adjacent[i];
                    if (adjacentNode.marked == false)
                    {
                        adjacentNode.marked = true;
                        queue.Enqueue(adjacentNode);
                    }
                }
                Console.Write(node.data + ",");
            }
        }