图的连通性问题

2019-11-08 03:16:21

字体：大中小

来源：转载

供稿：网友

图的表示方法

#define E 1000000#define V 100000struct Edge{ int v;//终止点 int c;//边权点 int next;//下一个结点}p[E];int head[V];//链表头int e;//边总数void init()//初始化{ memset(head,-1,sizeof(head)); e=0;}void addnote(int u,int v,int c)//加边{ p[e].v=v; p[e].c=c; p[e].next=head[u]; head[u]=e++;}

无向图

连通分量

方法一：并查集

init_set(|V|);for each(u,v) in E union(u,v);//条件find(a)=find(b),说明a,b同属于一个连通分量

方法二：深搜

dfs(u){ vis[u]=eis; for each (u,v) in E if(!vis[v]) dfs(v);}memset(vis,0,sizeof(vis));eid=0;for each v in V{ if(!vis[v]) { ++eid; dfs(v); }}

有向图

弱连通分量

去掉边的方向以后形成的无向图是连通图，没有孤立点算法：把有向边看作无向边，用并查集或深搜

强连通分量

Tarjan算法

void tarjan(int u){ vis[u]=true; dfn[u]=low[u]=++Time; stack.push(u); for each (u,v) in E if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]); else if(ins[v]) //只有回边才更新low值，过滤掉横跨边 low[u]=min(low[u],dfn[v]); end for if(low[u]>=dfn[u])//low[u]是否受过回边牵连 { do { v=stack.pop(); PRint v; }while(u!=v);//打印一组强连通的顶点集 }}

找环

（1）拓扑排序

bool toposort(int n,int *que){ int i,j,v; static int deg[MAXN],stk[MAXN],top,sz; memset(deg,0,sizeof(deg)); for(int i=0;i<n;i++) { for(int j=p[i],~j;j=e[j].next)//枚举i的邻边 { v=e[j].v; deg[v]++; } } for(top=i=0;i<n;i++) { if(!deg[i]) stk[top++]=i; } sz=0; while(top) { v=stk[--top]; que[sz++]=v; for(int i=p[v];~i;i=e[i].next) { v=e[i].v; --deg[v]; if(!deg[v]) stk[top++]=v; } } return (sz==n);//返回是否无环}

（2）用强连通分量来做，寻找图的强连通子图（3）用改进的DFS解决问题

//C[N]的值//0:此结点没有被访问过//-1:此结点被访问过至少1次，其后代结点正在被访问//1:其后代结点都被访问过void dfs(u){ C[u]=-1;//回边的标志 for each(u,v) in E if(!C[v]) dfs(v); else if(C[v]==-1)//回边，存在环 circle_found(); C[u]=1;//横跨边、前向边的标志}

边连通分量与桥

性质：（1）边连通分量不含桥，含有桥的子图不是边连通分量（2）任何一个无向连通图都恰好由桥和边连通分量组成（3）如果将每个边连通分量缩成一个点，那么新图必然是一棵树，每一条树边在原图就是一个桥算法：定义low[u]的值为搜索树中u的树边、回边、前向边的关联结点中low的最小值，设v是一个树边的关联结点，那么low[u]比low[v]大是说明u-v是一个桥，复杂度为O(|E|)

void edge_conn(fa,u){ vis[u]=true; dfn[u]=low[u]=++Time; stack.push(u); for each (u,v) in E if not vis[v] then edge_conn(u,v); low[u]=min(low[u],low[v]); if low[v]>dfn[u] then //说明深搜树中，(u,v)是树边 print(u,v) //v的子树没有越过u的回边，可见(u,v)是桥 do { v=stack.pop(); print v; }while(u!=v);//记录一个边连通分量 end if else if u!=fa and low[v]<low[u] low[u]=dfn[v]; end for}

双连通分量与割点

性质：双连通分量不含割点，含有割点的子图不是双连通分量，但可能是边连通量。 |连通分量|>|边连通分量|>|双连通分量| 算法：

dfs(fa,u){ int i; dfn[u]=low[u]=++Time; vis[u]=true; for each (u,v) in E if(v==fa) continue; if vis[i] then low[u]=min(low[u],dfn[v]); else dfs(u,v); low[v]=min(low[u],low[v]); if(low[v]>=dfn[u]) cut[u]++; //cut[u]表示点u的存在与否导致的连通分量的变化数目 end if end for if(fa!=-1) cut[u]++;}

上一篇：谈一谈我眼中的常见修饰符(private,final,static)

下一篇：linuxC通讯录