【数据结构笔记22】图的遍历例题：拯救007（应用DFS）、六度空间（应用BFS）

本次笔记内容：
6.3 应用实例：拯救007
6.4 六度空间

拯救007

题目与分析

题目

如上图，007在中心的孤岛上。他必须以鳄鱼为跳板，跳到岸上。那么，收到了这张卫星图，你将告诉007：他能抵达岸边吗？如果能，他该走哪条路呢？

首先应思考两个问题？

• 什么是图的顶点？
• 什么是图的边？

分析

鳄鱼与岸边是顶点，两者距离小于等于007的跳跃距离是边。

总体算法

假设007的第一跳（从孤岛上）距离与其他跳跃不一样。因此，不将007第一跳考虑在递归算法内，寻找第一跳之后的连通集。

void ListComponents(Graph G)
{
    for (each V in G)
        if (!visited[V])
        {
            DFS(V);
        }
}

void Save007(Graph G)
{
    for (each V in G)
    {
        if (!visited[V] && FirstJump(V))
        {
            answer = DFS(V);
            if (answer == YES)
                break;
        }
    }
    if (answer == YES)
        output("Yes");
    else
        output("No");
}

如上图，本算法可以利用类似ListComponents的思想。

本题目中的DFS算法如下。

int DFS(Vertex V)
{
    visited[V] = true;
    if (IsSafe(V))
        answer = YES;
    else
    {
        for (each W in G)
            if (!visited[W] && Jump(V, W))
            {
                answer = DFS(W);
                if (answer == YES)
                    break;
            }
    }
    return answer;
}

在这个问题中，图未必要用邻接表或者邻接矩阵来表示，怎么方便怎么来就好。

六度空间（Six Degrees of Separation）

题目

算法思路

• 对每个节点，进行广度优先搜索
• 搜索过程中累计访问的节点数
• 需要记录“层”数，仅计算6层以内的节点数

void SDS()
{
    for (each V in G)
    {
        count = BFS(V);
        Output(count / N);
    }
}

BFS中需要增加表示层数的变量。

如上图，在普通BFS算法中，增加level变量表示层数，last变量表示这一层结点最后一个，tail指向下一层进队列的最后一个结点。

int BFS(Vertex V)
{
    visited[V] = true;
    count = 1;
    level = 0;
    last = V; // level 指目前的层数
    Enqueue(V, Q);
    while (!IsEmpty(Q))
    {
        V = Dequeue(Q);
        for (V的每个邻接点W)
            if (!visited[W])
            {
                visited[W] = true;
                Enqueue(W, Q);
                count++;
                tail = W;
            }
        if (V == last)
        {
            level++;
            last = tail;
        }
        if (level == 6)
            break;
    }
    return count;
}