`
Coco_young
  • 浏览: 126522 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

求割点和桥的DFS

 
阅读更多
//无向图求割点和桥
void dfs(int cur,int fa,int deep,int &time)
{
	visit[cur] =  1;
	DFN[cur] = LOW[cur] = deep;
	int soncnt = 0;
	for(int i=0;i<g[cur].size();i++)
	{
		int v = g[cur][i];
		if(!vis[v])
		{
			soncnt++;
			dfs(v,cur,deep+1,time);
			LOW[cur] = MIN(LOW[cur],LOW[v]);
			if(cur!=ROOT&&LOW[v]>=DFN[cur])//割点
			{
				cutv[cur] = 1;
			}
			if(cur==ROOT&&soncnt>=2)//割点
			{
				cutv[cur] = 1;
			}
			if(LOW[v]>DFN[cur])//桥
			{
				Brige[cur][v] = 1;
			}
		}
		else if(v!=fa)
		{
			LOW[cur] = MIN(DFN[v],LOW[cur]);
		}
	}
	LEAVE[cur] = time++;
}


分享到:
评论

相关推荐

    图论- 图的连通性- Tarjan 求割点与桥.rar

    Tarjan算法是一种深度优先搜索(DFS)的变体,用于高效地找出图中的割点和桥。算法的基本步骤包括: 1. 对图进行深度优先遍历,为每个访问到的顶点分配一个低点(low point)和一个深度优先次序(DFS number)。 2....

    割点、桥和连通分量1

    Tarjan算法在搜索过程中同时计算割点和SCC,而Kosaraju算法则先对原图进行一次DFS得到拓扑排序,再对反向图进行DFS求出SCC。 在实际问题中,例如POJ2186,题目要求找出所有通过传递关系都认为彼此受欢迎的奶牛数量...

    acm算法秘籍

    acm算法书,acmer必用的算法书。...割点和桥 拓扑排序 最短路 Dijkstra 最短路 SPFA 最短路 Floyed 次短路与第K短路 最近公共祖先 LCA 最小生成树 Kruskal 最小树形图 一般图的最大匹配 最大流 Dinic 最小割 费用流

    graph技术介绍.

    寻找割点和桥通常使用深度优先搜索(DFS)策略。low-link是一个辅助概念,表示从u的后代节点出发经过回边到达的最低顶点的深度。根节点若拥有至少两个子节点,则可能是割点;非根节点v若其low-link值大于或等于其...

    C++算法:图算法 (第3版)

    8. **图的割点和桥**:割点是指移除后会导致图不连通的顶点,桥是移除后会导致图不连通的边。理解和识别割点和桥有助于分析图的结构。 9. **图的染色问题**:图的染色问题可以用来解决资源分配和调度问题,例如四色...

    二分图资料

    3. **割点和桥检测**: 图中的割点(切割后导致连通性改变的顶点)和桥(切割后导致连通性改变的边)与二分图不兼容,因此检查图中是否存在割点和桥也可以判断是否为二分图。 **四、应用** 1. **网络设计**: 在...

    08 ArticulationPoint.rar

    DFS可以用于构建低点和桥的检测,低点是到达其所有子孙节点的DFS访问时间不超过从起点到该点的DFS访问时间的节点。桥是使得去掉后会增加连通分量的边。通过DFS,我们可以计算每个节点的低点值,并根据这些值确定割点...

    2019图论课件——电子科大杨春老师含复习ppt(全).zip

    10. **图的割点和桥**:割点是移除后会导致图不连通的顶点,桥是移除后会导致图不连通的边。理解和判断割点和桥有助于分析图的结构。 11. **图的算法应用**:图论算法在互联网路由、社交网络分析、电路设计、生物...

    图论的算法与程序设计

    9. 图的割点和桥:割点是删除后会将图分割成多个连通分量的顶点,桥是删除后会将图分割成多个连通分量的边。识别割点和桥有助于理解和分析图的结构。 10. 图的着色和覆盖问题:如独立集(互不相邻的顶点集合)和...

    shiyan55.zip_C++ 有向图

    DFS可以用于检测图中的环路、查找强连通分量以及计算割点和桥等任务。 **广度优先搜索(BFS)** 与DFS不同,BFS使用队列进行遍历,从起点开始,首先访问所有与其相邻的未访问节点,然后再依次访问它们的相邻节点。...

    危险系数1

    总的来说,解决这个问题需要对图的连通性、割点和桥有深入的理解,以及熟悉如何使用DFS、BFS和并查集等数据结构进行有效的算法设计。在实际编程实现时,还需要注意内存和时间的限制,确保算法的效率。

    图的连通_黄哲威.pdf

    割点和桥的概念通常应用于无向图中。割点是指删除该点及其相邻边后会导致图的连通分量数量增加的节点。桥则是指移除后同样导致连通分量数量增加的边。割点不一定会导致桥出现,但有桥必然存在对应的割点。在无向图中...

    改造成双连通图2

    这可以通过计算每个节点的割点(cut vertex)和桥(bridge)来完成,如果没有割点和桥,那么图就是双连通的。 总结来说,将图改造成双连通图是一个涉及图的遍历、连通分量识别、边的添加和验证的过程。它需要理解图...

    图论及其应用 一本介绍图论的好书

    割点和桥对于理解图的结构至关重要,而平面图则涉及到图的二维表示和图的四色定理。图的着色问题,如边着色和顶点着色,是图论中的经典问题,它们与实际问题如地图着色和资源分配问题相联系。 书中的另一个亮点是图...

    35-图算法-小结1

    9. **图的割点和桥**:割点是删除后导致图不连通的顶点,桥是删除后导致图不连通的边。理解这些概念有助于识别图的结构特性。 10. **图的染色问题**:例如四色定理,它是图论中的经典问题,表明任何平面图都可以用...

    图论算法.rar

    8. **图的割点和桥**:割点是指移除后会导致图不连通的顶点,桥是移除后会将图分为两个或更多连通分量的边。这些概念在分析网络的稳定性或脆弱性时很重要。 9. **图的矩阵表示**:邻接矩阵和邻接表是两种常用的图...

    电子科大研究生图论05-14年图论期末试题.pdf

    - 割点和桥(articulation point and bridge) - 哈密顿图(Hamiltonian graph) - 欧拉图(Eulerian graph)等 5. 图的遍历算法: - 深度优先搜索(DFS, Depth-First Search) - 广度优先搜索(BFS, Breadth-...

    图论及其应用习题解答.zip图论及其应用习题解答.zip

    7. **图的割点和桥**:割点是删除后会导致图不连通的顶点,桥是删除后会使得图分成分量的边,这些概念在网络可靠性分析中非常重要。 8. **图的同构**:判断两个图是否结构相同,这在图的分类和模式识别中发挥作用。...

    acm学习用的书

    - 图论基础:包括强连通分量、双联通分量、拓扑排序、割点和桥等。 - 最短路算法:Dijkstra算法、SPFA算法、Floyd算法。 - 最小生成树:Kruskal算法、Prim算法。 - 最大流算法:Dinic算法、最小割费用流。 - 特殊图...

Global site tag (gtag.js) - Google Analytics