无向图的割顶与桥
具体的概念和定义比较多,在刘汝佳<<训练指南>>P312-314页都有详细的介绍.
下面来写求无向图割顶和桥的DFS函数.我们令pre[i]表示第一次访问i点的时间戳,令low[i]表示i节点及其后代所能连回(通过反向边)的最早祖先的pre值.
下面的dfs函数返回的是当前遍历的节点u的low值.如果u是割顶还会标记u节点.且如果u->v(v是u的儿子节点)边是桥也会标记该边.
测试代码:
/*刘汝佳 训练指南P 312-314
测试输入数据:
6 6
0 1
1 2
1 3
2 4
2 5
4 5
输出为:
边(1, 2)是桥
边(1, 3)是桥
边(0, 1)是桥
割顶是:1
割顶是:2
注意上面 虽然0点是根节点且只有1个儿子,但是边(0,1)也是桥
*/
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=100000+10;
int n,m;
int dfs_clock;
vector<int> G[maxn];//点从0到n-1编号
int pre[maxn],low[maxn];
bool iscut[maxn];
int dfs(int u,int fa)
{
int lowu=pre[u]=++dfs_clock;
int child=0;
for(int i=0; i<G[u].size(); i++)
{
int v=G[u][i];
if(!pre[v])
{
child++;//未访问过的节点才能算是u的孩子
int lowv=dfs(v,u);
lowu=min(lowu,lowv);
if(lowv>=pre[u])
{
iscut[u]=true; //u点是割点
if(lowv>pre[u]) //(u,v)边是桥
printf("边(%d, %d)是桥\n",u,v);
}
}
else if(pre[v]<pre[u] && v!=fa)//v!=fa确保了(u,v)是从u到v的反向边
{
lowu=min(lowu,pre[v]);
}
}
if(fa<0 && (child==1||child==0) )
iscut[u]=false;//u若是根且孩子数<=1,那u就不是割顶
return low[u]=lowu;
}
int main()
{
while(scanf("%d%d",&n,&m)==2&&n)
{
dfs_clock=0;
memset(pre,0,sizeof(pre));
memset(iscut,0,sizeof(iscut));
for(int i=0;i<n;i++) G[i].clear();
for(int i=0;i<m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(0,-1);
for(int i=0;i<n;i++)if(iscut[i]==true)
printf("割顶是:%d\n",i);
}
return 0;
}
分享到:
相关推荐
首先,理解无向图中的桥(Cut Edge)或割边。在一个无向图中,如果移除某条边后,导致图中的某些顶点无法通过其他边相连,那么这条边就被称作桥。换句话说,桥是那些在删除后会将图分割成两个或多个不连通部分的边。...
在无向图中,如果有一条边,当它被移除后,原本连通的图分裂成两个或更多的不相交的连通分量,那么这条边就被称作"桥"。换句话说,桥是那些对图的连通性至关重要的边,没有它们,图的连通性将被破坏。这一点在实际...
这里提到的"tarjan点双与边双缩点"是一种基于Tarjan算法实现的无向图缩点方法。Tarjan算法是一个用于查找图中强连通分量和检测桥的有效算法。 首先,让我们理解Tarjan算法的基本思想。Tarjan算法通过深度优先搜索...
割边则是在无向图中,如果删除这条边,会导致原本连通的两个顶点变为不连通。这两种概念常用于分析图的结构稳定性,特别是在网络设计和容错系统中。 2. **最小生成树**(MST):MST是无向加权图中边的子集,它包含...
在图论中,无向图G是由顶点集V和边集E组成的数学结构,用于描述对象之间的连接关系。在图的分析中,点割集、边割集、割点、桥、连通度和双连通分支是关键概念,它们帮助我们理解图的结构特性。 1. **点割集**: 点...
图的割集是指在无向图中,移除某部分顶点和边后导致整个图不连通的顶点子集。图代数则是图论中研究图的代数结构和代数性质的一个分支,它借鉴了抽象代数中的概念和方法,为图的分析提供了一种新的工具和视角。 在唐...
1. **无向图与有向图**:无向图的边没有方向,而有向图的边具有方向性。有向边、无向边、平行边(多条边连接同一对节点)、环(一条边形成闭合路径)以及孤立节点(没有边连接的节点)都是基本概念。关联与邻接指的...
### 四、无向图:割顶、桥和双连通分量 割顶和桥分别是无向图中去除后会破坏图连通性的顶点和边。双连通分量是在无向图中,任意两点间至少存在两条不相交的路径的子图。 ### 五、强连通化和支配点 强连通化旨在...
- **无向图找桥**:桥是无向图中删去后会导致图不连通的边,可以使用Tarjan算法或Kosaraju算法来查找。 - **无向图连通度(割)**:计算无向图的连通分支,了解图的分块结构,常用DFS或BFS实现。 - **最大团问题*...
- 无向图求割点与桥:割点是无向图中去掉该点(以及与它相连的边)后,会导致原图不连通的点;桥是指去掉后会导致原图不连通的边。 - 无向图边双连通分量:在无向图中,若删除任一边都不会导致图不连通,则称该边...
寻找无向图中的“桥”——那些移除后会将图分割的边;计算无向图的连通度(割);以及解决最大团问题,这是组合优化问题的一种,通常用动态规划(DP)和DFS结合来求解。 2. **欧拉路径**:欧拉路径是指在一个图中,...
- 首先,将城市中的区域抽象为顶点,将桥抽象为边,构建一个无向图。 - 接着,检查每个顶点的度数。如果所有顶点的度数都是偶数,则存在一条欧拉回路。 - 如果不存在这样的路径,说明问题无解。 #### 最短路径问题 ...
- 无向图找桥:寻找无向图中的桥,即删除后会增加连通分支的边。 - 无向图连通度(割):研究图的最小割问题,用于图的网络流分析。 - 最大团问题DP+DFS:使用动态规划和深度优先搜索解决最大团问题。 - 欧拉路径:...
- **割点**: 对于一个无向图,如果删除一个节点后图的连通分量数增加,则称该节点为割点。 - **割边(桥)**: 如果删除一条边后图的连通性受到影响,即图分裂为两个不相连的子图,则称该边为割边。 - **连通性算法**...
- **无向图找桥**:在无向图中,桥是指如果移除后会导致图不连通的边。 - **无向图连通度(割)**:计算图的连通分量,理解图的结构和割点。 - **最大团问题**:寻找图中最大的完全子图,可以使用动态规划(DP)...
无向图的边没有特定的方向,而有向图的每条边都有明确的方向。在电路分析中,有向图特别有用,因为它们可以用来表示电流的流向。例如,一个电路图可以被看作是一个图,其中的节点代表电路的各个部分,边则表示电流...