java如何在图形中查找连接器?
我在这里有点挣扎,因为老实说,我的大脑被炸了,我不知道该怎么办
我的任务是在一个无向的、未加权的图中找到连接器
该任务声称:在无向图中,如果至少有两个其他顶点x和w,且x和w之间的每条路径都经过v,则顶点v是一个连接符
别误会我,我明白这意味着什么,但我做这件事是无可救药的。当我浏览这个图表时(建议我使用DFS),我到底应该做什么
我只想在正确的道路上完成这件事
非常感谢您的帮助
你可以在下面搜索框中键入要查询的问题!
我在这里有点挣扎,因为老实说,我的大脑被炸了,我不知道该怎么办
我的任务是在一个无向的、未加权的图中找到连接器
该任务声称:在无向图中,如果至少有两个其他顶点x和w,且x和w之间的每条路径都经过v,则顶点v是一个连接符
别误会我,我明白这意味着什么,但我做这件事是无可救药的。当我浏览这个图表时(建议我使用DFS),我到底应该做什么
我只想在正确的道路上完成这件事
非常感谢您的帮助
# 1 楼答案
您正在描述的连接器是剪切垂直(或连接点):https://en.wikipedia.org/wiki/Biconnected_component)
为了找到无向图中的所有连接点,我们可以使用一种改进的DFS算法。一般的想法是在图上运行DFS,同时用两个变量标记每个节点n:整数低位(n)和整数DFS(n)。如果节点v的邻居w具有低(w)>;=dfs(v),节点v是一个关节点。伪代码描述如下:
该算法的运行时间与基本DFS算法相同:O(V+E),其中V是图中的顶点数,E是图中的边数