最新公告
  • 欢迎您光临欧资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 深度优先搜索(depth-firstsearch)的算法介绍及应用

    深度优先搜索是前序遍历的推广。我们从某个顶点v开始处理v,然后递归促进所有与v相邻的顶点。如果这个过程在一棵树上执行,那么树的所有顶点都会被系统地访问。如果我们在任意图上运行这个过程,我们需要小心以避免循环。为此,当我们访问一个顶点 v 时,由于我们已经到达该点c语言无向图连通分量,我们可以将该点标记为已访问,并递归调用深度优先搜索所有尚未标记的相邻顶点。

    这里我们假设,对于一个无向图,每条边(v,w)在邻接表中出现两次c语言无向图连通分量,一次是(v,w),一次是(w,v)。下图是深度优先搜索的通用样式模板。

    void Dfs(Vertex V)
    {
        Visited[V] = True;
        for each W adjancent to V
            if(!Visited[W])
                Dfs(W)
    }

    无向图

    当且仅当每个节点都被任何节点的深度优先搜索访问时,无向图是连通的。如果我们正在处理的图没有连接,那么我们可以找到所有连接的分支并将我们的算法依次应用于每个分支。

    掌握算法-图论-深度优先搜索的应用-无向图和双连通性

    无向图

    让我们从上面的图 A 开始,作为深度优先搜索的示例。

    此时 A 被标记为已访问,并递归调用 Dfs(B)。

    Dfs(B) 将 B 标记为已访问并递归调用 Dfs(C)。

    Dfs(C) 将 C 标记为已访问并递归调用 Dfs(D)。

    Dfs(D)遇到A和B,但是两个节点都已经访问过了,所以不能递归调用。

    Dfs(D) 也看到 C 是相邻的顶点,但是 C 也被访问过,所以这里也没有进行递归调用,

    所以 Dfs(D) 返回到 Dfs(C)。

    Dfs(C)看到B是邻接,忽略它,发现之前没见过的顶点E也是邻接,所以调用Dfs(E)。

    Dfs(E)以E为记号,忽略A和C,返回Dfs(C)。

    Dfs(C) 返回到 Dfs(B)。Dfs(B) 忽略 A 和 D 并返回。Dfs(A) 忽略 D 和 E 返回。

    现在我们以图形方式描述深度优先生成树的步骤。树的根是 A,即要访问的第一个顶点。图中的每条边 (v, w) 都出现在树中。我们在处理 (v, w) 时发现 w 是未标记的,或者在处理 (w, v) 时发现 v 是未标记的,那么我们将其表示为树的一条边。如果我们在处理 (v, w) 时发现 w 被标记,而在处理 (w, v) 时 v 被标记,那么我们画一条虚线,称为后边缘,表示该边缘实际上不是树。

    掌握算法-图论-深度优先搜索的应用-无向图和双连通性

    树将模拟我们执行的遍历。仅使用树边的前序编号告诉我们标记这些顶点的顺序。

    如果图不连通,那么处理所有节点(和边)需要多次调用 Dfs,每次生成一棵树,整个集合就是一个深度优先的生成森林。

    双连接

    如果一个连通无向图中的任何一个顶点被删除,剩下的图仍然是连通的,那么这样的无向连通图称为双连通图。上一个图是双连通的。如果示例中的节点是计算机并且边缘是链接,那么如果任何一台计算机发生故障并无法运行,则 webmail 不受影响,当然与该计算机相关的邮件除外。同样,如果公共交通系统是双向连接的,如果站点被破坏,用户总是可以选择替代的出行路线。

    如果一个图不是双连接的,那么在移除它后不再连接的那些顶点称为关节点。这些节点在许多应用中都很重要。下图不是双连通的:顶点 C 和 D 是割点。

    掌握算法-图论-深度优先搜索的应用-无向图和双连通性

    深度优先搜索提供了一种线性时间算法,用于查找连通图中的所有切点。

    首先,从图中的任何顶点开始,执行深度优先搜索并在访问顶点时对其进行编号。对于每个顶点 v,我们称其为预序数 Num(v)。然后,对于深度优先搜索生成树上的每个顶点 v,计算编号最小的顶点,我们称之为 Low(v) — 从 v 开始,通过树的零个或多个边,并且可能到达更多一个(按顺序)背对边缘。

    掌握算法-图论-深度优先搜索的应用-无向图和双连通性

    上面显示的深度优先树,节点标记为 Num 和 Low

    从 A、B、C 出发的最低可达边数固定为 1(A),因为它们可以通过树的边 D,然后在背对边的边上回到 A。我们可以通过执行深度优先生成树的后续遍历来有效地计算 Low。根据low的定义,Low(v)为:

    中最小的。

    剩下要做的就是使用这些信息来找到所有的切点。根是一个切点当且仅当它有多个儿子,因为如果他有两个儿子,那么删除根会使节点断开连接并分布在不同的子树上;如果根只有一个儿子,则删除根。一个根只是从那个根中脱离出来。对于任何顶点 v,当且仅当它有某个子 w 使得 Low(w) >= Num(v) 时,它才是一个切点。请注意,此条件始终在根处满足,因此需要特殊测试。

    当我们检查算法确定的切点时。D有一个儿子E,Low(E)>=Num(D),两者都是4。因此,E到达D上方任意一点的方式只有一种,那就是通过D。同理C也是一个切点,因为 Low(G)>=Num(C)。

    掌握算法-图论-深度优先搜索的应用-无向图和双连通性

    通过在 C 中开始深度优先搜索获得的深度优先树

    伪代码如下:

    为了简化程序,这里的数组 Visited[]、Num[]、Low[] 和 Parent[] 是全局变量。我们还有一个名为 Counter 的全局变量,它为 Num[] 赋值以进行前序遍历。

    对顶点的 Num 分配

    void AssignNum(Vertex V)
    {
        Vertex W;
        Num[V] = Counter++;
        Visited[V] = True;
        for each W adjancent to V
            if(!Visited[W]){
                Parent[W] = V;
                AssignNum(W);
            }
    }

    用于计算 Low 并检查它是否是切点的伪代码

    void AssignNum(Vertex V)
    {
        Vertex W;
        Num[V] = Counter++;
        Visited[V] = True;
        for each W adjancent to V
            if(!Visited[W]){
                Parent[W] = V;
                AssignNum(W);
            }
    }
    void AssignLow(Vertex V)
    {
        Vertex W;
        Low[V] = Num[V];
        for each W adjancent to V
        {
            if(Num[W] > Num[V]){
                AssignLow(W);
                if(Low[W] >= Num[V]){
                    printf("%v is an articulation pointn");
                }
                Low[V] = Min(Low[V], LOW[W]]);
            }
        }
        else{
            if(Parent[V] != W){
                Low[V] = Min(Low[v], Num[W]);
            }
        }
    }

    以上两者的结合

    void FindArt(Vertex V)
    {
        Vertex W;
        Visited[V] = True;
        Low[V] = Num[V] = Counter++;
        for(each W adjancent to V)
        {
            if(!Visited[W]){
                Parent[W] = V;
                FindArt(W);
                if(Low[W] >= Num[V])
                    printf("%v is an articulation pointn");
                Low[V] = Min(Low[V], LOW[W]);    
            }
            else{
                if(Parent[V] != W){
                    LOW[V] = Min(LOW[V], Num[W]);
                }
            }
        }
    }

    站内大部分资源收集于网络,若侵犯了您的合法权益,请联系我们删除!
    欧资源网 » 深度优先搜索(depth-firstsearch)的算法介绍及应用

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    欧资源网
    一个高级程序员模板开发平台

    发表评论