BYR Achieve · 镜像论坛

点基B满足：对于任意一个顶点Vj，一定存在B中的一个Vi,使得Vi是Vj的前代。点基包含：顶点数最小的点基权最小的点基(当所有的权为1时，权最小的点基变成了顶点数的最小的点基) 最高强连通分支：定义：如果在G中，不存在终点属于[Si]而起点不属于[Si]的弧，就称[Si]为最高强连通分支。性质：强连通分支Si与图G其他部分相连的所有弧都是向外伸展的。即表明任何非Si中的点与Si中的点没有有向边。说明，最小点基必须在强连通分支中取一个。所以最小点基的个数即为强连通分支的个数。权最小(顶点数最小)点基求法： 1) 找出图G的所有强连通分支 2) 从强连通分支中找出所有最高的强连通分支 3) 从每个最高的强连通分支中取一个权最小的顶点，组成的顶点集B就是一个G的权最小点基 /3)从每个最高强连通分支中任取一个顶点如何求最高强连通分支：强连通分支的充要条件：对于里面的任何顶点之间要相互可达。包含Vi的强连通分支：Vi的所有后代集合和所有前代集合的交集。求Vi所有后代的集合R 1)给Vi以标号+，Vi是已标号但未检查的顶点 2)看看是否有已标号但未检查的顶点，如果没有则计算结束，所有已标号的顶点构成集合R。如果有，则任取一点Vk，转入步骤3) 3)找出以Vk为起点的所有弧<k,j>一条一条的考虑这些弧，如果<Vk，Vj>的终点Vj没有标号，就给Vj以标号+，Vj成为已标号但未检查的点。同理求顶点Vi的所有前代集合。 //最小点基 #include <stdio.h> #include <string.h> #define maxn 100 bool s[maxn];// bool graph[maxn][maxn];// int n;// void init() { int i,j,e,k; scanf("%d",&n); for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ graph[i][j]=false; } } scanf("%d",&e); for(k=1;k<=e;k++){ scanf("%d%d",&i,&j); graph[i][j]=true; } } void make_s_i(int x,bool v_i[])// { bool next[maxn];// bool pre[maxn];// bool check[maxn];// bool more;// int i,j; for(i=1;i<=n;i++){// next[i]=false; pre[i]=false; check[i]=false; } next[x]=true;pre[x]=true; more=false; while(true){// more=false; for(i=1;i<=n;i++){ if(next[i] && !check[i]){ for(j=1;j<=n;j++){ if(graph[i][j] && !next[j]){ next[j]=true; } } more=true; check[i]=true; } } if(!more) break; } for(i=1;i<=n;i++){// check[i]=false; } while(true){ more=false; for(i=1;i<n;i++){ if(pre[i] && !check[i]){ for(j=1;j<=n;j++){ if(graph[j][i] && !pre[j]){ pre[j]=true; } more=true; check[i]=true; } } } if(!more) break; } for(i=1;i<=n;i++){// v_i[i]=next[i] && pre[i]; } } bool highest(bool s_i[]) { int i,j; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(graph[i][j] && !s_i[i] && s_i[j]) return false; } } return true; } int main() { bool s_i[maxn]; int i,j; init(); for(i=1;i<=n;i++){ s[i]=false; } for(i=1;i<=n;i++){ if(!s[i]){// make_s_i(i,s_i); if(highest(s_i)){ printf("%d ",i); } for(j=1;j<=n;j++){ s[j]=s[j] || s_i[j]; } } } return 0; }

最小点基的模块代码[转帖]