题目:求一个连通图的割点,割点的定义是,如果除去此节点和与其相关的边,图不再连通,描述算法。
分析:
1. 最简单也是最直接的算法是,删除一个点然后判断连通性,如果删除此点,图不再连通,则此点是割点,反之不是割点(图的连通性一般通过深搜来判定,是否能一次搜索完 全部顶点);
2. 通过深搜优先生成树来判定。从任一点出发深度优先遍历得到优先生成树,对于树中任一顶点V而言,其孩子节点为邻接点。由深度优先生成树可得出两类割点的特性:
(1)若生成树的根有两棵或两棵以上的子树,则此根顶点必为割点。因为图中不存在连接不同子树顶点的边,若删除此节点,则树便成为森林;
(2)若生成树中某个非叶子顶点V,其某棵子树的根和子树中的其他节点均没有指向V的祖先的回边,则V为割点。因为删去v,则其子树和图的其它部分被分割开来。
仍然利用深搜算法,只不过在这里定义visited[v]表示为深度优先搜索遍历图时访问顶点v的次序号,定义low[v]=Min{visited[v],low[w],visited[k]},其中w是顶点v在深度优先生成树上的孩子节点;k是顶点v在深度优先生成树上由回边联结的祖先节点。
割点判定条件:如果对于某个顶点v,存在孩子节点w且low[w]>=visited[v],则该顶点v必为关节点。因为当w是v的孩子节点时,low[w]>=visited[v],表明w及其子孙均无指向v的祖先的回边,那么当删除顶点v后,v的孩子节点将于其他节点被分割开来,从来形成新的连通分量。
#include <iostream>
#include <string>
#include <queue>
using namespace std;
#define MAXN 100
struct ArcNode
{
int adjVertex; //边到的顶点
ArcNode *next;
};
struct VNode
{
string data;
ArcNode *firstArc;
};
typedef VNode AdjList[MAXN];
struct Graph
{
int vertexNum;
int arcNum;
AdjList vertexs;
};
int Locate(Graph g,string str)
{
for(int i = 0;i<g.vertexNum;i++)
{
if(str == g.vertexs[i].data)
return i;
}
return -1;
}
void Create(Graph &g)
{
string start,end;
cout << "请输入顶点和边数:"<<endl;
cin>>g.vertexNum>>g.arcNum;
for(int i = 0;i<g.vertexNum;i++)
{
cout<<"请输入第"<<i<<"个顶点:"<<endl;
cin>>g.vertexs[i].data;
g.vertexs[i].firstArc = NULL;
}
for(int i = 0;i <g.arcNum;i++)
{
cout<<"请输入第"<<i<<"条边的起始和结束顶点"<<endl;
cin>>start>>end;
int m = Locate(g,start);
int n = Locate(g,end);
ArcNode *node = new ArcNode;
node->adjVertex = n;
node->next = g.vertexs[m].firstArc;
g.vertexs[m].firstArc = node;
ArcNode *node1 = new ArcNode;
node1->adjVertex = m;
node1->next = g.vertexs[n].firstArc;
g.vertexs[n].firstArc = node1;
}
}
void Print(Graph g)
{
for(int i = 0;i<g.vertexNum;i++)
{
cout << g.vertexs[i].data;
ArcNode *p = g.vertexs[i].firstArc;
while(p)
{
cout<<"-->"<<g.vertexs[p->adjVertex].data;
p = p->next;
}
cout <<endl;
}
}
int FirstAdjVex(Graph g,int v)//返回v的第一个邻接顶点序号
{
ArcNode *p = g.vertexs[v].firstArc;
if(p!= NULL)
return p->adjVertex;
else
return -1;
}
int NextAdjVex(Graph g,int v,int w) //返回顶点v相对于w的下一个邻接点的序号
{
ArcNode *p = g.vertexs[v].firstArc;
while(p)
{
if(p->adjVertex == w)
break;
p = p->next;
}
if(p->adjVertex !=w || !p->next)
return -1;
return p->next->adjVertex;
}
//求割点
int countN;
int visted[MAXN];
int low[MAXN];
void DFSCutPoint(Graph g,int v0)
{
int min = 0,w;
visted[v0] = min = ++countN;;//v0是第count个访问的顶点,min的初值为visited[v0],即v0的访问次序
for(ArcNode *p = g.vertexs[v0].firstArc;p;p=p->next)
{
w = p->adjVertex;
if(!visted[w])
{
DFSCutPoint(g,w);//从第w个顶点出发深搜,查找并输出关节点(割点),返回前求得low[w]
if(low[w] < min)//如果v0的孩子节点w的low[]小,说明孩子节点还与其他节点(祖先)相邻
min = low[w];
if(low[w]>=visted[v0] ) //v0的孩子节点w只与v0相连,则v0是关节点(割点)
cout<<g.vertexs[w].data<<" ";
}
else if(visted[w] < min)//w已访问,则w是v0生成树上祖先,它的访问顺序必小于min
min =visted[w];
}
low[v0] = min;//low[v0]取三者最小值
}
void FindCutPoint(Graph g)
{
visted[0] = true;
for(int i = 1;i<g.vertexNum;i++)
visted[i] = false;
ArcNode *p=g.vertexs[0].firstArc;
int v = p->adjVertex;
DFSCutPoint(g,v);
if(countN < g.vertexNum)
{
cout << g.vertexs[0].data<<" ";
while(p->next)
{
p = p->next;
v = p->adjVertex;
if(!visted[v])
DFSCutPoint(g,v);
}
}
}
int main()
{
Graph g;
Create(g);
cout<<"割点如下: "<<endl;
FindCutPoint(g);
return 0;
分享到:
相关推荐
生成1个100个点,300条边的无向图,对于图中的每个连通分支,计算其中的的割点。
图论- 图的连通性- Tarjan 求割点与桥.rar
这道题的目的是求如去除某个点,能把图分成多少个子图,求这样子图的最大数。...其实就是求割点,然后看每个割点能把图分成多少个子图,当然原图不一定是连通的。 割点的求法各个书籍上都有,其实就是用DFS进行遍历。
图文并茂地介绍了割点,桥,双连通子图,双连通分支,最近公共祖先(LCA), 其中穿插着例题与习题,每个知识点均有模板。
图论的基本知识:无向图与有向图、树和二叉树、赋权图与 网络。 图的搜索算法:二叉树与一般树的搜索算法(先根... 通信网络的可靠性问题*:连通图的割点与双连通性、生成双 连通分支算法。 代码最优化问题**
生成一个无向连通图,有100个点,1000条边,边上的权重是1到20之间的随机整数。用Kruskal或prim算法求得该图的最小生成树,验证局部搜索算法的对错。 实验7.已知Bellman-Ford算法能判断一个有向加权图是否含有负权重...
本文研究了边连通度为r的n阶连通图中距离谱半径最小的极图问题.利用组合的方法,确定了K(n-1,r)为唯一的极图,其中K(n-1,r)是由完全图Kn-1添加一个顶点v以及连接v与Kn-1中r个顶点的边所构成.上述结论推广了极图...
本课件主要讲解了并查集,割点和桥,强连通分量(Kosaraju, Tarjan)
简单来说,对于一个连通图,如果去掉某个顶点 (vertex),这个图就会被分割而变成非连通图,那么这个被去掉的点就被叫做“割点 (cut vertex)”,如下图。 在这个沙漏状的图中,去掉中间的顶点后,整个图就分割成两...
任一连通图的Hosoya多项式的定义如下:H(G)≡H(G,x):=∑dk≥0d(G,k)xk,其中d(G,k)是图G中距离为k的点对的个数。事实上,d(G,0)等于图G的点数,而d(G,k)等于图G的边数。设{Gi)P=1是一个两两不交的图的集合,...
1. 证明:一个图是 2 边连通的当且仅当任意两个顶点至少由两条边 2. 证明:不是块的连通图至少有两个块,每个恰有一个割点 3. 证明:若 G 是k ≥ 2的
割点/割边 7 点/边双联通 9 最短路 && 查分约束 11 Dijkstra 11 SPFA 13 Floyd_Wallshall 14 次短路 15 查分约束 16 2- SAT 17 生成树 18 最小生成树 18 最小树形图 20 拓扑排序 22 最大团 23 LCA 24 倍增 24 基于...
1.2 连通图 1.3 若干常见的图类 1.4 多重图与有向图 第2章 度 2.1 顶点的度 2.2 正则图 2.3 度序列 2.4 延伸阅读:图与矩阵 2.5 专题探索:不规则图 第3章 同构图 3.1 同构的定义 3.2 同构关系 3.3 ...
其中一个目录 图论 路径问题 0/1边权最短路径 BFS 非负边权最短路径(Dijkstra) 可以用Dijkstra解决问题的特征 负边权最短路径 Bellman-Ford Bellman-Ford的Yen-氏优化 差分约束系统 Floyd 广义路径...
7.15 若干图论问题:最小生成树 最短路 强连通分量、桥和割点 等 7.16 网络流算法:基本的网络流算法,Dinic算法,带上下界的网络流,最小费用流 7.17 数学题:组合数学,数论等 7.18 最小生成树和动态规划
双三角蛇图的调和标号,奚悦,杨元生,三角蛇图是由多个三角形的块所组成连通图, 并且块的割点是一条路径. David Moulton 证明了由p个块所组成的三角蛇图当p≡0,1(mod 4)时有��
通过分析单位圆盘图中极大独立集的性质和连通图的块一割点树结构,首次设计出在无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法。从理论上分析了该算法的时间复杂度,并证明了该算法的近似比为常数。
5) 若干图论问题:最小生成树 强连通分量、桥和割点等 6) 计算几何:线与线求交,线与面求交,求凸包,半平面求交等 7) 网络流算法:基本的网络流算法,Dinic算法,带上下界的网络流,最小费用流 8) 数学题:组合...
Tarjan 算法是图论中非常实用 / 常用的算法之一,能解决强连通分量,双连通分量,割点和桥,求最近公共祖先(LCA)等问题。 关于 Tarjan 算法,笔者将用一系列文章系统介绍 Tarjan 算法的原理以及其主要解决的问题...