《算法设计手册》面试题解答 第五章:图的遍历 附:DFS应用之找挂接点

简介:

第五章面试题解答

5-31.

  DFS和BFS使用了哪些数据结构?

解析:

  其实刚读完这一章,我一开始想到的是用邻接表来表示图,但其实用邻接矩阵也能实现啊?后来才发现应该回答,BFS用队列实现;DFS可以用栈实现也可以改写成递归形式。用栈来消除递归改写DFS也出现在《算法导论》的练习题22.3-6。

 

5-32.

  写一个函数,在遍历二叉查找数的时候,输出第i个结点。

解析:

  模仿DFS遍历时维护一个进入时间数组和完成时间数组的特点,维护一个全局变量n,在中序遍历的时候,每遍历一个结点就n++,直到n=i时打印这个结点,或者遍历完成时仍然n!=i时报错即可。

 

题外话:

  第5章“图遍历”的Interview Problems部分确实只有这两题,而第6章“带权图算法”干脆就没Interview Problems这一部分。其实图本身的表示就比较复杂,几个基本的图算法虽然思路不难,但是代码量不小,同时要写繁琐的初始化方法,写具体算法实现时还要用到各种辅助数据结构,编码起来想少都不行。况且就算真写出来了,正确性的证明又很费功夫(比如拓扑排序、强联通分支),因此面试时除了专门做这个方向的,很少会考到具体的代码书写,更不用说其他变形、改进了。这也就是为什么图相关的面试题并不多的原因。

  另外提一下,《算法设计手册》上的拓扑排序和强联通分支算法是基于边分类的,而且它把DFS写成了一个可扩充的框架;而《算法导论》则是利用最后完成时间来实现这两个算法,在此之前把DFS写成了一个子程序供这两个算法调用。究竟孰优孰劣我不评价,从先入为主和对我而言易于理解的角度和来说,我更倾向于使用后者。

 

DFS应用之找挂接点(Articulation Vertices,《算法导论》中文版的翻译) 

  既然提到了《算法设计手册》上DFS的框架写法了,这个算法正好来进行演示。(《算法导论》思考题22-2曾提到了这个概念)。

  先来看看《算法设计手册》版DFS框架:

//图用邻接表实现
//entry_time[]  某结点开始处理的时间
//exit_time[]    某结点处理完毕的时间
//discoverd[]    某个结点是否已被发现
//process_vertex_early() 某个结点刚发现时采取的处理
//process_edge() 对边的处理
//process_vertex_late() 某个结点所有邻接边处理完后的动作
//以上三个函数决定了DFS的行为,如果只需要基本的功能,可以实现为空操作,或者输出该结点/边用于追踪遍历过程

dfs(graph *g, int v)
{
    edgenode *p; /* temporary pointer */
    int y; /* successor vertex */
    if (finished) return; /* allow for search termination */

    discovered[v] = TRUE;
    time = time + 1;
    entry_time[v] = time;
    process_vertex_early(v);
    p = g->edges[v];
    while (p != NULL) {
          y= p->y;
          if (discovered[y] == FALSE) {
               parent[y] = v;
               process_edge(v,y);
               dfs(g,y);
          }
          else if ((!processed[y]) || (g->directed))
               process_edge(v,y);
           if (finished) return;
               p = p->next;
     }
     process_vertex_late(v);
     time = time + 1;
     exit_time[v] = time;
     processed[v] = TRUE;
}    
《算法设计手册》版DFS框架

  挂接点是指,如果我们从连通图中删除这个结点,会导致图不再连通。下图中的白点就是挂接点,可以把它看作为图上最脆弱的点。

 

  使用DFS或BFS写一个暴力算法很简单:删除一个结点,用DFS或BFS判断是否连通;恢复原图,删除下一个结点继续判断,直至所有接点都判断过。如果结点数n个,边数m个,暴力算法时间复杂度为O(n(m+n))。

  现在用DFS遍历时生成树的角度来看。对于这棵树上所有在原图的边,归为TREE边;其余所有边是BACK边,即它们指向一个先于这个结点遍历的另一个结点。

  可以发现一些规律:

DFS树的叶结点不可能是挂接点,删去它树的连通性未被破坏。只有树的内结点可能是挂接点。

对于DFS树的根,如果它只有一个孩子,那么删去它和删去一个叶结点是一样的。而孩子多于1个时,删去根会导致孩子们不再连通,也即它是挂接点。 

对于一个BACK边,它连接的两个结点的TREE路径(即DFS时形成的路径)上的所有结点都不可能是挂接点。

  寻找挂接点需要维护BACK边连接DFS树上结点与其祖先的信息。用reachable_ancesor[v]表示结点v用BACK边能连接的最老祖先(初始化为v),tree_out_degree[v]表示结点在DFS树的出度。edge_classification(int x,int y)用于判断(x,y)是TREE还是BACK。

复制代码
int reachable_ancestor[MAXV+1]; /* earliest reachable ancestor of v */
int tree_out_degree[MAXV+1]; /* DFS tree outdegree of v */
process_vertex_early(int v)
{
    reachable_ancestor[v] = v;
}

process_edge(int x, int y)
{
    int class; /* edge class */
    class = edge_classification(x,y);
    if (class == TREE)
        tree_out_degree[x] = tree_out_degree[x] + 1;
    if ((class == BACK) && (parent[x] != y)) {
        if (entry_time[y] < entry_time[ reachable_ancestor[x] ] )
            reachable_ancestor[x] = y;
    }
}

int edge_classification(int x, int y)
{
    if (parent[y] == x) 
        return TREE;
    else
        return BACK;
}
复制代码

  下面是v与祖先的连通性和v是否是挂接点的关系,一共是三种情况:

  用代码实现在process_vertex_late()里,即:

复制代码
process_vertex_late(int v)
{
    bool root; /* is the vertex the root of the DFS tree? */
    int time_v; /* earliest reachable time for v */
    int time_parent; /* earliest reachable time for parent[v] */
    if (parent[v] < 1) { /* test if v is the root */
        if (tree_out_degree[v] > 1)
            printf("root articulation vertex: %d \n",v);
        return;
    }

    root = (parent[parent[v]] < 1); /* is parent[v] the root? */
    if ((reachable_ancestor[v] == parent[v]) && (!root))
        printf("parent articulation vertex: %d \n",parent[v]);

    if (reachable_ancestor[v] == v) {
        printf("bridge articulation vertex: %d \n",parent[v]);
        if (tree_out_degree[v] > 0) /* test if v is not a leaf */
            printf("bridge articulation vertex: %d \n",v);
    }

    time_v = entry_time[reachable_ancestor[v]];
    time_parent = entry_time[ reachable_ancestor[parent[v]] ];
    if (time_v < time_parent)
        reachable_ancestor[parent[v]] = reachable_ancestor[v];
}
复制代码

   最后几行用entry_time[v]表示v的年龄,time_v是v通过BACK边达到的最老结点。如果v的parent能通过v的BACK到达v的最老祖先,那么parent(v)肯定不是挂接点,下次处理parent(v)时做出这样的标记让它能通过v的BACK到达v的最老祖先。

 






本文转自五岳博客园博客,原文链接:www.cnblogs.com/wuyuegb2312/p/3264943.html,如需转载请自行联系原作者

目录
相关文章
|
6天前
|
运维 监控 算法
监控局域网其他电脑:Go 语言迪杰斯特拉算法的高效应用
在信息化时代,监控局域网成为网络管理与安全防护的关键需求。本文探讨了迪杰斯特拉(Dijkstra)算法在监控局域网中的应用,通过计算最短路径优化数据传输和故障检测。文中提供了使用Go语言实现的代码例程,展示了如何高效地进行网络监控,确保局域网的稳定运行和数据安全。迪杰斯特拉算法能减少传输延迟和带宽消耗,及时发现并处理网络故障,适用于复杂网络环境下的管理和维护。
|
14天前
|
机器学习/深度学习 算法
算法系列之搜索算法-深度优先搜索DFS
深度优先搜索和广度优先搜索一样,都是对图进行搜索的算法,目的也都是从起点开始搜索,直到到达顶点。深度优先搜索会沿着一条路径不断的往下搜索,直到不能够在继续为止,然后在折返,开始搜索下一条候补路径。
91 62
算法系列之搜索算法-深度优先搜索DFS
|
1天前
|
存储 人工智能 算法
通过Milvus内置Sparse-BM25算法进行全文检索并将混合检索应用于RAG系统
阿里云向量检索服务Milvus 2.5版本在全文检索、关键词匹配以及混合检索(Hybrid Search)方面实现了显著的增强,在多模态检索、RAG等多场景中检索结果能够兼顾召回率与精确性。本文将详细介绍如何利用 Milvus 2.5 版本实现这些功能,并阐述其在RAG 应用的 Retrieve 阶段的最佳实践。
通过Milvus内置Sparse-BM25算法进行全文检索并将混合检索应用于RAG系统
|
8天前
|
存储 缓存 监控
企业监控软件中 Go 语言哈希表算法的应用研究与分析
在数字化时代,企业监控软件对企业的稳定运营至关重要。哈希表(散列表)作为高效的数据结构,广泛应用于企业监控中,如设备状态管理、数据分类和缓存机制。Go 语言中的 map 实现了哈希表,能快速处理海量监控数据,确保实时准确反映设备状态,提升系统性能,助力企业实现智能化管理。
25 3
|
17天前
|
算法 Serverless 数据处理
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
46 12
|
16天前
|
算法 安全 网络安全
基于 Python 的布隆过滤器算法在内网行为管理中的应用探究
在复杂多变的网络环境中,内网行为管理至关重要。本文介绍布隆过滤器(Bloom Filter),一种高效的空间节省型概率数据结构,用于判断元素是否存在于集合中。通过多个哈希函数映射到位数组,实现快速访问控制。Python代码示例展示了如何构建和使用布隆过滤器,有效提升企业内网安全性和资源管理效率。
48 9
|
8天前
|
算法 安全 Java
探讨组合加密算法在IM中的应用
本文深入分析了即时通信(IM)系统中所面临的各种安全问题,综合利用对称加密算法(DES算法)、公开密钥算法(RSA算法)和Hash算法(MD5)的优点,探讨组合加密算法在即时通信中的应用。
14 0
|
17天前
|
机器学习/深度学习 人工智能 自然语言处理
解锁机器学习的新维度:元学习的算法与应用探秘
元学习作为一个重要的研究领域,正逐渐在多个应用领域展现其潜力。通过理解和应用元学习的基本算法,研究者可以更好地解决在样本不足或任务快速变化的情况下的学习问题。随着研究的深入,元学习有望在人工智能的未来发展中发挥更大的作用。
|
11天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM
本研究基于MATLAB 2022a,使用GRU网络对QAM调制信号进行检测。QAM是一种高效调制技术,广泛应用于现代通信系统。传统方法在复杂环境下性能下降,而GRU通过门控机制有效提取时间序列特征,实现16QAM、32QAM、64QAM、128QAM的准确检测。仿真结果显示,GRU在低SNR下表现优异,且训练速度快,参数少。核心程序包括模型预测、误检率和漏检率计算,并绘制准确率图。
83 65
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM
|
2天前
|
机器学习/深度学习 数据采集 算法
基于PSO粒子群优化的CNN-LSTM-SAM网络时间序列回归预测算法matlab仿真
本项目展示了基于PSO优化的CNN-LSTM-SAM网络时间序列预测算法。使用Matlab2022a开发,完整代码含中文注释及操作视频。算法结合卷积层提取局部特征、LSTM处理长期依赖、自注意力机制捕捉全局特征,通过粒子群优化提升预测精度。适用于金融市场、气象预报等领域,提供高效准确的预测结果。

热门文章

最新文章