読者です 読者をやめる 読者になる 読者になる

Training for D-Day

ブログの内容は個人の見解であり、所属する企業を代表するものではありません。

C#で深さ優先検索(DFS)と幅優先検索(BFS)の実装

Qiitaにも投稿しましたが。

C#で深さ優先検索(DFS)と幅優先検索(BFS)の実装 - Qiita

深さ優先検索

    public class DFS
    {
        public static void Search( Node root )
        {
            if(root == null)
            {
                return;
            }
            Visit(root);
            root.Visited = true;
            if (root.Children != null)
            { 
                foreach (var node in root.Children)
                {
                    if(!node.Visited)
                    {
                        Search(node);
                    }
                }
            }
        }

        private static void Visit(Node root)
        {
            // nop
        }
    }

    public class Node
    {
        public bool Visited { get; set; }

        public Node[] Children { get; set; }
    }

幅優先検索

        public static void Search( Node root )
        {
            var queue = new Queue<Node>();
            root.Visited = true;
            Visit(root);
            queue.Enqueue(root);

            while(queue.Count != 0)
            {
                var current_node = queue.Dequeue();
                if (current_node.Children != null)
                { 
                    foreach (var node in current_node.Children)
                    {
                        if(!node.Visited)
                        {
                            Visit(node);
                            node.Visited = true;
                            queue.Enqueue(node);
                        }
                    }
                }
            }
        }

        private static void Visit(Node root)
        {
            // nop
        }

Queueの使い方がポイントですね。

GitHubにもあげてあります。 https://github.com/Koki-Shimizu/DFS