做网站维护价格,企业网站建设实训体会,亚马逊联盟wordpress主题,长沙 网页制作【0】README
0.1#xff09; 本文总结于 数据结构与算法分析#xff0c; 源代码均为原创#xff0c; 旨在 理解 “DFS应用于找割点” 的idea 并用源代码加以实现#xff1b; 0.2#xff09; 必须要事先 做个specification的是#xff1a;对于给定图的除开起始vertex的那…【0】README
0.1 本文总结于 数据结构与算法分析 源代码均为原创 旨在 理解 “DFS应用于找割点” 的idea 并用源代码加以实现 0.2 必须要事先 做个specification的是对于给定图的除开起始vertex的那些 vertexes都可以通过我们的 rules见下文找出割点即对于根start我们需要做个special 的test参见main函数中最后的源码 【1】 无向图割点相关
1.1割点定义articulate point 如果一个图不是双连通的 那么将其删除后图将不再连通的那些顶点叫做割点
1.2双连通性定义 如果一个连通的无向图中的任一顶点删除之后 剩下的图仍然是连通的 那么这样的无向连通图就是 双连通的 1.3看个荔枝 如果节点是 路由器或者交换机 的话 边是网络链路 那么若有一台 路由器或者交换机 出故障而不能运行 则网络并不会受到影响的 【2】深度优先搜索提供一种找出连通图中的所有割点的线性时间算法
2.1首先 从图中任一顶点开始 执行深度优先搜索并在顶点被访问时给它们编号 对于每一个顶点我们称其为先序编号 Num(v) 注在源代码中vertexIndex 表示Num的含义下文不再累述) 2.2然后 对于深度优先搜索生成树上的每一个顶点v 计算编号最低的顶点 我们称之为 Lowv该点从v 开始 通过树的零条或多条边且可能还有一条背向边而达到 注在源代码中vertexLow 表示Low的含义下文不再累述) Attention右上图中的深度优先搜索树首先指出先序编号然后指出上述法则下可达到的最低编号顶点
2.3从A、B、C开始的可达到最低编号顶点为1A 因为它们都能够通过树的边到D 然后再由一条背向边回到A 2.4我们可以通过对该深度优先生成树执行一次后序遍历有效地算出 Low 根据low的定义可知Lowv是
1 Numv 2 所有背向边v, w中的最低Numw 3 树的所有边v, w中的最低Loww 以上三者中 的最小者对以上规则的分析 第一个条件是不选取边 第二种方法是不选取树的边 而是选取一条背向边第三种方法则是选择树的某些边以及可能还有一条背向边
Attention
A1由于我们需要对v 的所有儿子计算出 Low 值后才能计算Low(v) , 因此这是一个后序遍历A2对于任一条边v, w 我们只要检查Numv和 Numw就可以知道它是树的一条边还是一条背向边因为如果是深度优先树的边 Num(v) Num(w) 因为v比w先被访问到 而如果是背向边Num(v) Num(w)的 A3因此 Lowv 容易计算 我们仅仅需要扫描v 的邻接表应用适当 的法则并记住最小值。 所有的计算花费 O|E| |V| 【3】剩下要做的就是利用 这些信息找出所有的割点。
3.1对于根见本文README部分根是割点当且仅当它有多于一个的儿子根至少要有两个儿子因为如果它有两个儿子 那么删除根则使得节点不连通而分布在不同的子树上如果根只有一个儿子 那么除去该根只不过是断离该根。 3.2对于任何其他顶点v 它是割点当且仅当它有某个儿子w 使得Loww Num(v) 注意 这个条件在根处总是满足的 因此需要进行特别的测试干货 【4】source code printing results
4.1download source code https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter9/p242_dfs_findArticulation 4.2source code at a glancefor complete code , please click the given link above
4.2.1 找割点的函数
// find the articulation point from the given graph
void findArticulate(Vertex vertex, int depth)
{ int i;AdjTable temp; Vertex adjVertex; visited[vertex] 1; // update visited status of vertexvertexIndex[vertex] counter; // evaluating vertex index with countervertexLow[vertex] vertexIndex[vertex]; // the 1st rule: evaluating vertex low with countertemp adj[vertex]; while(temp-next){adjVertex temp-next-vertex; if(visited[adjVertex]) // judge whether the adjVertes was visited before {if(vertexIndex[vertex] vertexIndex[adjVertex] parent[vertex] ! adjVertex) {//parent[adjVertex] vertex; // building back side, attention of condition of building back side above //ex vertex 3, adjVertex 0// just for printing effectfor(i 0; i depth; i) printf( );printf(vertex[%c]-vertex[%c] (backside) \n, flag[vertex], flag[adjVertex]);// only if theres a backside, we apply the 2rd rule into the graphvertexLow[vertex] minimum(vertexLow[vertex], vertexIndex[adjVertex]); // the 2rd rule: find lowest vertexIndex[w] among all edges(v, w) }}// if(!visited[adjVertex])// theres the case no backside, and if condition sentences refers to case of backsideelse {parent[adjVertex] vertex; // just for printing effectfor(i 0; i depth; i) printf( );printf(vertex[%c]-vertex[%c] (building edge)\n, flag[vertex], flag[adjVertex]); findArticulate(adjVertex, depth1);if(vertex ! start) // judge whether the vertex is the start (root) or not if(vertexLow[adjVertex] vertexIndex[vertex])printf(\n\t vertex[%c] proves to be an articulation point !, flag[vertex]);vertexLow[vertex] minimum(vertexLow[vertex], vertexLow[adjVertex]); // the 3rd rule: find lowest verdexLow[w] among all edges(v, w) }temp temp-next; }
} 4.2.2 判断start顶点是否是割点的函数
int isStartArticulation()
{int i; AdjTable temp;Vertex adjVertex; temp adj[start]; while(temp-next){adjVertex temp-next-vertex; if(adjVertex start){temp temp-next;continue;}dfs(adjVertex, 1); for(i0; isize; i) if(visited[i] ! 1) // refers that the start vertex is the articulation pointreturn 1; temp temp-next;}return 0;
}
4.3printing results
