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