算法－图的广度优先搜索，图的深度优先搜索

时间：2024-03-23 08:21:53

1.图的广度优先搜索
(1). 定义
图的广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索树或图的算法。这个算法从图的某一节点（源节点）开始，探索最靠近源节点的节点，然后是一层一层地向外扩展，直到找到目标节点或遍历完整个图。

下面是广度优先搜索的基本步骤：
a. 创建一个队列，将源节点入队。
b. 对源节点执行访问，同时标记其已经被访问。
c. 当队列不为空时，循环执行以下步骤：
c.1. 从队列中取出一个节点。
c.2. 遍历该节点的所有邻居节点。如果邻居节点未被访问过，访问此节点，再将其加入队列和标记其已经被访问。
d. 算法结束。

在广度优先搜索中，所有从源节点出发，到达同一层级的节点，都会被一同处理。因此，广度优先搜索可以找到从源节点到目标节点的最短路径（如果目标节点存在的话），这里的“最短”指的是路径上边的数量最少。

在编程实现广度优先搜索时，通常会用到队列这种数据结构，因为队列的特性是先进先出（FIFO），这正好符合广度优先搜索逐层向外扩展的需求。

值得注意的是，广度优先搜索在某些情况下可能不是最优的，例如当图很大或者结构复杂时，它可能需要遍历很多节点才能找到目标节点。在这种情况下，可能需要考虑使用其他搜索算法，如深度优先搜索（DFS）或启发式搜索算法等。

(2). 实例
在这里插入图片描述
针对上述图结构，我们可以借助广度优先搜索计算并打印一条A到G的边数最少的路径．

2.图的深度优先搜索
(1). 定义
深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

在图的深度优先搜索中，基本的思想是从某个顶点v开始，首先访问该顶点，然后依次从v的未被访问的邻接点出发，对图进行深度优先遍历，直至图中和v有路径相通的顶点都被访问。如果此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

深度优先搜索的具体步骤可以总结如下：
(1). 访问顶点v。
(2). 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问。

若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。需要注意的是，深度优先搜索的结果可能不唯一，因为搜索的顺序可能因不同的邻接点选择顺序而有所变化。

深度优先搜索在许多应用中都有重要的作用，如网络爬虫、人工智能、编译器设计等。在网络爬虫中，深度优先搜索可以帮助我们按照特定的路径去遍历网页；在人工智能中，深度优先搜索可以用于求解迷宫问题等；在编译器设计中，深度优先搜索可以用于语法分析树的构建等。

总的来说，深度优先搜索是一种强大且灵活的算法，可以处理各种复杂的图结构问题。
(2). 实例
在这里插入图片描述
上述是一个由边和节点构成的图结构．我们可以利用深度优先搜索找到从A到E的所有可行路径．并输出其中边数最少的一条路径的变数，及路径上的节点信息．

class NodeInfo{
public:
    char m_nName;
};

template<class T>
class Node{
public:
    T m_nEle;
};

template<class EdgeInfo>
class Edge{
public:
    bool m_bValid = false;
};

Node<NodeInfo> stNodes[10];
Edge<int> stEdges[10][10];
int ArrPath[1000][10];
int PathNum = 0;
int MinPath[10];
int MinNum = 10;
void Visit(int nCurIndex, int nEndIndex, int (&ArrIndex)[10], int nNum);
int main(){
    stNodes[0].m_nEle.m_nName = 'A';
    stNodes[1].m_nEle.m_nName = 'B';
    stNodes[2].m_nEle.m_nName = 'C';
    stNodes[3].m_nEle.m_nName = 'D';
    stNodes[4].m_nEle.m_nName = 'E';
    stNodes[5].m_nEle.m_nName = 'F';
    stNodes[6].m_nEle.m_nName = 'G';
    stNodes[7].m_nEle.m_nName = 'H';
    stNodes[8].m_nEle.m_nName = 'I';
    stNodes[9].m_nEle.m_nName = 'J';
    
    stEdges[0][1].m_bValid = true;
    stEdges[0][6].m_bValid = true;
    stEdges[1][2].m_bValid = true;
    stEdges[2][3].m_bValid = true;
    stEdges[2][5].m_bValid = true;
    stEdges[3][4].m_bValid = true;
    stEdges[5][3].m_bValid = true;
    stEdges[5][9].m_bValid = true;
    stEdges[6][5].m_bValid = true;
    stEdges[6][8].m_bValid = true;
    stEdges[7][6].m_bValid = true;
    stEdges[8][7].m_bValid = true;
    stEdges[8][9].m_bValid = true;
    stEdges[9][4].m_bValid = true;
    // 找到从A到E的所有可能路径
    int nFirstIndex = 0;
    int nEndIndex = 4;
    int ArrIndex[10];
    int nNum = 0;
    // 深度优先遍历
    Visit(nFirstIndex, nEndIndex, ArrIndex, nNum);
    // 打印结果
    printf("min path:%d\n", MinNum);
    for(int i = 0; i < MinNum; i++){
        printf("%c ", stNodes[MinPath[i]].m_nEle.m_nName);
    }
    printf("\n");
    printf("path num:%d\n", PathNum);
    while(true){
        printf("path index:\n");
        int nIndex = 0;
        scanf("%d", &nIndex);
        getchar();
        if(nIndex < 0){
            break;
        }
        for(int i = 0; i < 10; i++){
            printf("%c ", stNodes[ArrPath[nIndex][i]].m_nEle.m_nName);
        }
        printf("\n");
    }
    return 0;
}
// 从nCurIndex开始到nEndIndex的所有路径
void Visit(int nCurIndex, int nEndIndex, int (&ArrIndex)[10], int nNum){
    // 访问当前节点
    //stNodes[nCurIndex].m_nEle.m_bVisit = true;
    ArrIndex[nNum] = nCurIndex;
    nNum++;
    if(nCurIndex == nEndIndex){
        // 记录
        for(int i = 0; i < nNum; i++){
            ArrPath[PathNum][i] = ArrIndex[i];
        }
        PathNum++;
        // 比较&更新
        if(nNum < MinNum){
            MinNum = nNum;
            for(int i = 0; i < nNum; i++){
                MinPath[i] = ArrIndex[i];
            }
        }
        return;
    }
    // 在当前阶段基础上，继续走向每个分支
    for(int i = 0; i < 10; i++){
        int nOldNum = nNum;
        // 从当前沿着此分支继续走下去
        if(stEdges[nCurIndex][i].m_bValid){
            // 剪分支
            // 待访问节点不能已经出现在累计的访问路径上．将环路排除在结果外．
            int k = 0;
            for(; k < nNum; k++){
                if(ArrIndex[k] == i){
                    break;
                }
            }
            if(k >= nNum){
                Visit(i, nEndIndex, ArrIndex, nNum);
            }
        }
        // 分支走完需要撤销影响．以便继续从当前沿着后续分支继续走．防止数据被污染．走的过程中需要记录和更新的内容已经记录下来了．
        nNum = nOldNum;
    }
}

上述算法是一个典型的深度优先，递归，动态规划性质的算法．
此类算法典型特征：
(1). 递归算法．
(2). 参数部分提供当前阶段，截止阶段信息（方便知道何时停止后续递归），累计到当前的阶段性信息．
(3). 访问当前设计对阶段性信息记录，及到达截止阶段时比较＆更新全局信息．
(4). 从当前节点继续走向可行分支．
要走向的分支得存在．
需要进行剪枝分析．具体到上述，因为我们要求解最短路径，所以，需剪掉出现环路的分支．
(5). 走完一个分支后，需防止数据被污染．要分析从上一分支走的过程中那些数据被污染了，并判断是否需恢复．具体到上述，我们维护的阶段性信息被污染了．重新走后续分支时，我们需将其恢复到走首个分支前的状态．因为上述我们需借助阶段性信息来记录从起点到终点的路径信息．

相关文章