成立网站公司需要什么,中山网页设计,建网页的公司,长沙网站设深度优先搜索的利用。 在一个无向连通图中#xff0c;如果删掉某个顶点后#xff0c;图不再连通#xff08;即任意两点之间不能互相到达#xff09;#xff0c;我们称这样的顶点为割点。 在一个无向连通图中#xff0c;如果删掉某条边后#xff0c;图不在连通#xff0… 深度优先搜索的利用。 在一个无向连通图中如果删掉某个顶点后图不再连通即任意两点之间不能互相到达我们称这样的顶点为割点。 在一个无向连通图中如果删掉某条边后图不在连通这就是割边。 我们来看一个例子
重要城市 我们已经掌握了敌人的城市地图为了在战争中先发制人决定向敌人的某个城市上空投放炸弹来切断敌人城市之间的通讯和补给城市地图如下。 肉眼可见删除二号顶点后图便不在连通。那么我们如何设计程序来判断呢 最直接的方法是遍历每一个顶点判断该点删除后其它顶点是否连通用邻接表存储时间复杂度为。 现在要讲的Tarjan算法在朴素算法的基础上优化可以把时间复杂度降低到。
Tarjan算法(图的割点) Tarjan算法相较于朴素方法我认为就是在深度搜索的时候已经处理了哪些是割点因为遍历的时候肯定会遇到割点而不需要再遍历n个顶点去删除所以它的时间复杂度去除了外面的变成了。 为了突出Tarjan算法部分我们先用邻接矩阵来写这道题时间复杂度为。 所以最主要的就是深度搜索部分我们先来想一下朴素方法的深度搜索其实就是构成了一个生成树每一个无向连通图都有生成树 本图的一个生成树如上所示num数组来记录每个顶点的时间戳每个结点的右上角表示第几个被访问到如num[3]2,表示顶点3第二个被访问。 正如前面所说遍历的时候肯定会遇到割点如果生成树上的一个子结点在图中不经过它的父结点就不能访问已经遍历过的其它结点那么它的父节点就肯定是割点了。根节点没有父节点时间戳最小需要另外判断 下面这个难题就转变了如果判断子节点不经过父节点访问其它节点。这里我们用一个low数组来存储一个节点在不经过父节点的情况下能访问到最远结点的时间戳。 对于某个顶点u如果至少一个顶点v即顶点的儿子使得(两个数组都是存的时间戳)那么u点为割点。 对于本例5号顶点的儿子只有6号结点且low[6]的值为3而5号顶点的时间戳为num[5]为5low[6]num[5],可以回到祖先因此5号结点不是割点。 2号顶点的时间戳为num[2]为3low[5]3low[5]num[2],不可以回到祖先因此2号结点不是割点。 完整代码详细理解深度搜索部分
#includestdio.h
int n,m;/*顶点数和边数*/
int root;/*根结点*/
int e[9][9]{0};/*邻接矩阵*/
int num[9]{0},low[9]{0},flag[9]{0};
/*num记录时间戳low记录不经过父节点到达的最远时间戳
flag记录是否为割点*/int min(int a,int b)
{return ab ? a:b;
}void dfs(int cur,int father,int index)
{int child0;index;num[cur]index;low[cur]index;for (int i 1; i n; i){if (e[cur][i]1){if (num[i]0)/*i顶点没有杯访问过*/{child;/*子结点1*/dfs(i,cur,index);/*继续往下遍历*/low[cur]min(low[cur],low[i]);/*包含通过子节点访问的最早时间戳*/if (cur!root low[i] num[cur])/*当前结点不为根结点子节点不能不通过父节点访问到之前的结点该点为割点*//*不能为根结点是因为low[i]最小为root*/{flag[cur]1;}else if(curroot child2)/*为根结点且在生成树中不是图有两个儿子*//*生成树中有两个儿子肯定是割点没有两个儿子也有可能是割点*/flag[cur]1;}else if (i!father)/*访问到的不是父节点代表可以绕过了父节点*/{low[cur]min(low[cur],num[i]);} }}return ;
}int main()
{int x,y;scanf(%d %d,n,m);for (int i 1; i m; i){scanf(%d%d,x,y);e[x][y]1;e[y][x]1;/*无向图*/}root 1;dfs(1,root,0);for (int i 1; i n; i){if (flag[i]1){printf(%d ,i);}}return 0;
} 输入格式: 输入m1行第一行两个数n和mn表示n个顶点m表示m条边。接下来的m行每行形如“a b”用来表示一条边。 输出格式: 输出一行一个数表示花费的最少银子数。
输入样例 6 7 1 4 1 3 4 2 3 2 2 5 2 6 5 6 输出样例 2 图的割边 如下图所示左边的图没有割边右边的图有割边 图的割边其实子需要修改上面代码中的一个部分将改为即到达的顶点不包括其父结点和已经遍历的时间戳小于父结点的结点这就证明该子节点与父节点相连的边为割边。 由于割边不需要额外判断是否为根节点故判断那一部分可以删除。 完整代码注意输出部分
#includestdio.h
int n,m;/*顶点数和边数*/
int root;/*根结点*/
int e[9][9]{0};/*邻接矩阵*/
int num[9]{0},low[9]{0};
/*num记录时间戳low记录不经过父节点到达的最远时间戳*/int min(int a,int b)
{return ab ? a:b;
}void dfs(int cur,int father,int index)
{index;num[cur]index;low[cur]index;for (int i 1; i n; i){if (e[cur][i]1){if (num[i]0)/*i顶点没有杯访问过*/{dfs(i,cur,index);/*继续往下遍历*/low[cur]min(low[cur],low[i]);/*包含通过子节点访问的最早时间戳*/if (low[i] num[cur]){printf(%d-%d\n,cur,i);}}else if (i ! father)/*访问到的不是父节点代表可以绕过了父节点*/{low[cur]min(low[cur],num[i]);} }}return ;
}int main()
{int x,y;scanf(%d %d,n,m);for (int i 1; i m; i){scanf(%d%d,x,y);e[x][y]1;e[y][x]1;/*无向图*/}root 1;dfs(1,root,0); return 0;
}
输入格式: 输入m1行第一行两个数n和mn表示n个顶点m表示m条边。接下来的m行每行形如“a b”用来表示一条边。 输出格式: 输出一行一个数表示花费的最少银子数。
输入样例 6 6 1 4 1 3 4 2 3 2 2 5 5 6 输出样例 5-6 2-5 参考文献
《啊哈算法》
