图的盲目搜索

图的盲目搜索指的是不考虑边的开销的条件下的搜索。通常是为了遍历一个图或是找到一条两点之间的任意路径。盲目搜索分为深度优先搜索和广度优先搜索，它们的思想和实现同树的先序遍历、层序遍历很相似（毕竟树是图的子集）。

一、深度优先搜索（Depth First Search）

思路

深度优先搜索总是尽可能地深入一个图，当走到死胡同时才开始回溯，回到上一个点继续搜索。类比树的先序遍历就容易想到可以通过栈或是递归实现。我们需要定义一个栈Stack用于储存待搜索的节点，定义一个集合Visited用于储存搜索过的节点，每搜索到一个节点，将其相邻的没有搜索过的节点压入Stack，将其自身加入Visited。由于栈的先入后出原则，可以保证优先遍历下一层的节点而非同一层的相邻节点。知道栈清空就表示搜索完毕。该算法能实现连通图的遍历，若是非连通图则还需要做特殊处理。

实现

public static class DFS<T>
{
    private static List<Node<T>> result = new List<Node<T>>();

    private static Graph<T> graph;

    private static HashSet<Node<T>> visited = new HashSet<Node<T>>();

    // 递归版本
    public static List<Node<T>> DFSSearchRecursive(Graph<T> g, Node<T> start)
    {
        result.Clear();
        if (g == null || g.NodeNum == 0)
        {
            Debug.LogError("图为空！");
            return result;
        }

        graph = g;
        visited.Clear();
        DFSCore(start);
        return result;
    }

    private static void DFSCore(Node<T> node)
    {
        visited.Add(node);
        result.Add(node);
        var adjNode = graph[node].FirstAdjNode;
        while (adjNode != null)
        {
            if (!visited.Contains(adjNode.Data))
            {
                DFSCore(adjNode.Data);
            }
            adjNode = adjNode.Next;
        }
    }


    // 非递归版本
    public static List<Node<T>> DFSSearchStack(Graph<T> graph,Node<T> start)
    {
        if (graph == null || graph.NodeNum == 0)
        {
            Debug.LogError("图为空！");
            return new List<Node<T>>();
        }

        var stack = new Stack<Node<T>>();
        var visited = new HashSet<Node<T>>();
        var res = new List<Node<T>>();
        stack.Push(start);
        while (stack.Count > 0)
        {
            var node = stack.Pop();
            if (visited.Contains(node)) continue;
            visited.Add(node);
            res.Add(node);
            var adjNode = graph[node].FirstAdjNode;
            while (adjNode != null)
            {
                stack.Push(adjNode.Data);
                adjNode = adjNode.Next;
            }
        }
        return res;
    }
}

优化

当一个问题的状态空间非常复杂，复杂到无法在开始之前就创建好整个状态空间的图，只能在每一步进行节点的扩展，此时深度优先搜索就有可能在错误的路径上陷得非常深，甚至无法回来。一种解决办法是限制搜索的深度，到达深度限制后就自动回溯。但要将深度限制设置为多少才合适又成了一个问题，针对这个问题，可以使用迭代加深深度优先搜索，顾名思义，就是一开始将搜索深度设置为较小值，若没有搜索到则再加大搜索深度，直到完成为止。

二、广度优先搜索（Breadth First Search）

思路

广度优先搜索从源节点开始检查从它出发的每一个节点，然后再从刚检查过的节点继续展开，相比于深度优先搜索，广度优先搜索可以找到达到目标节点的最优路径（包含最少边数的路径）。其实现与广度优先搜索类似，只需要将栈改成队列，队列的先进先出原则可以保证优先遍历当前节点同一层级的节点而非下一层级的节点。

实现

public static List<Node<T>> BFSSearchRecursive(Graph<T> graph, Node<T> start)
    {
        if (graph == null || graph.NodeNum == 0)
        {
            Debug.LogError("图为空！");
            return new List<Node<T>>();
        }

        var queue = new Queue<Node<T>>();
        var visited = new HashSet<Node<T>>();
        var res = new List<Node<T>>();
        queue.Enqueue(start);
        while (queue.Count > 0)
        {
            var node = queue.Dequeue();
            if (visited.Contains(node)) continue;
            visited.Add(node);
            res.Add(node);
            var adjNode = graph[node].FirstAdjNode;
            while (adjNode != null)
            {
                queue.Enqueue(adjNode.Data);
                adjNode = adjNode.Next;
            }
        }
        return res;
    }

缺陷

广度优先搜索除了搜索小空间之外，在其他地方使用会显得比较笨拙，假设分枝数为b，深度为d，则我们需要检测的节点数为

$1+b^1+b^2+...+b^d$

如果被搜索的图分支数非常高，那么搜索效率将非常低。当状态空间复杂到需要一边搜索一遍扩展节点时，搜索将更加耗时。

参考资料：

《人工智能编程案例精粹》第5章：图的秘密生命
【C#数据结构系列】图 - 宇霍飞

Demo地址：https://github.com/Luciano-0/Graph.git