什么是搜索算法

上一節(jié)介紹了圖的基本概念洽议，這一節(jié)介紹圖的搜索算法荐绝。

圖的搜索算法，最直觀的理解就是從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的路徑旷痕。

最簡(jiǎn)單的是廣度優(yōu)先搜索和深度優(yōu)先搜索碳锈，這也是這一節(jié)介紹的內(nèi)容。另外還有A*欺抗、IDA*等啟發(fā)式搜索算法售碳。

本節(jié)內(nèi)容以無(wú)向圖為例，以下代碼是圖的代碼實(shí)現(xiàn)绞呈。

// 無(wú)向圖
class Graph
{
    private int v;  // 頂點(diǎn)個(gè)數(shù)

    private LinkedList<int>[] adj; // 鄰接表

    public Graph(int v)
    {
        this.v = v;
        adj = new LinkedList<int>[v];

        for (int i = 0; i < v; i++)
        {
            adj[i] = new LinkedList<int>();
        }
    }

    public void AddEdge(int s, int t)
    {
        // 無(wú)向圖贸人，一條邊要存兩次
        adj[s].AddLast(t);
        adj[t].AddLast(s);
    }
}

廣度優(yōu)先搜索

廣度優(yōu)先搜索（Breadth-First-Search），簡(jiǎn)稱(chēng)BFS佃声。一種“地毯式”的搜索策略艺智，即先搜索跟起始點(diǎn)最近的頂點(diǎn)，慢慢往外擴(kuò)散搜索圾亏。

廣度優(yōu)先搜索

代碼實(shí)現(xiàn)如下：

public void BFS(int s, int t)
{
    if (s == t) return; // 起始點(diǎn)和終止點(diǎn)相同十拣，直接返回封拧。

    Queue<int> queue = new Queue<int>();  // 
    bool[] visited = new bool[v];   // 用于記錄頂點(diǎn)是否被訪(fǎng)問(wèn)過(guò)。
    visited[s] = true;

    int[] prev = new int[v];  // 記錄當(dāng)前頂點(diǎn)的前置頂點(diǎn)
    for (int i = 0; i < v; i++)
    {
        prev[i] = -1;
    }

    queue.Enqueue(s);

    while (queue.Count > 0)
    {
        // 下一層入隊(duì)
        int w = queue.Dequeue();

        var head = adj[w].First;

        while (head != null)
        {
            int q = head.Value;

            if (!visited[q])
            {
                prev[q] = w;
                if (q == t)
                {
                    Print(prev, s, t);
                    return;
                }
                visited[q] = true;
                queue.Enqueue(q);
            }

            head = head.Next;
        }
    }
}

private void Print(int[] prev, int s, int t)
{
    if (prev[t] != -1 && t != s)
        Print(prev, s, prev[t]);

    Console.Write(t + " ");
}

通過(guò)下圖來(lái)介紹BFS是如何執(zhí)行的夭问。

BFS流程

時(shí)間復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(E)泽西。E表示圖的邊數(shù)
• 空間復(fù)雜度：O(V)。V表示圖的頂點(diǎn)數(shù)

深度優(yōu)先搜索

深度優(yōu)先搜索（Depth-First-Search）缰趋，簡(jiǎn)稱(chēng)DFS捧杉。最直觀的例子是“走迷宮”，往最里面走埠胖，遇到分叉路先走一邊然后再退回來(lái)走另一邊糠溜，直到走到終點(diǎn)。

深度優(yōu)先搜索

代碼實(shí)現(xiàn)如下：

public void DFS(int s, int t)
{
    found = false;

    bool[] visited = new bool[v];
    int[] prev = new int[v];
    for (int i = 0; i < v; i++)
    {
        prev[i] = -1;
    }

    RecurDfs(s, t, visited, prev);
    Print(prev, s, t);
}

private void RecurDfs(int w, int t, bool[] visited, int[] prev)
{
    if (found) return;

    visited[w] = true;

    if (w == t)
    {
        found = true;
        return;
    }

    var head = adj[w].First;
    while (head != null)
    {
        int q = head.Value;
        if (!visited[q])
        {
            prev[q] = w;
            RecurDfs(q, t, visited, prev);
        }

        head = head.Next;
    }
}

時(shí)間復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(E)直撤。E表示圖的邊數(shù)
• 空間復(fù)雜度：O(V)非竿。V表示圖的頂點(diǎn)數(shù)

案例分析

如何找出社交網(wǎng)絡(luò)中某個(gè)用戶(hù)的三度好友關(guān)系？

社交網(wǎng)絡(luò)可以用圖來(lái)表示谋竖，找出某個(gè)用戶(hù)的三度好友红柱，即是從某個(gè)頂點(diǎn)（某個(gè)用戶(hù)）走三步到達(dá)的頂點(diǎn)（三度好友）。

可使用BFS或DFS來(lái)實(shí)現(xiàn)蓖乘，增加一個(gè)值來(lái)保存好友是第幾度的锤悄，遍歷過(guò)程里把度分別為1、2嘉抒、3的頂點(diǎn)保存到結(jié)果集里零聚。