最小生成树模板
prim
int g[N][N];
bool st[N];
int dist[N];
int prim(){
memset(dist,INF,sizeof(dist));
memset(st,false,sizeof(st));
int res=0;
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j]&&(t==-1||dist[j]<dist[t])){
t=j;
}
}
if(i&&dist[t]==INF){
return INF;
}
st[t]=true;
if(i) res+=dist[t];
for(int j=1;j<=n;j++){
dist[j]=min(dist[j],g[t][j]);
}
}
return res;
}
kruskal
int f[N];
struct edge{
int a,b,w;
bool operator <(const edge& n)const{
return w<n.w;
}
}edge[M];
int find(int x){
if(f[x]!=x){
f[x]=find(f[x]);
}
return f[x];
}
int kruskal(){
int res=0;
sort(edge,edge+m);
for(int i=1;i<n;i++){
f[i]=i;
}
int cnt=0;
for(int i=0;i<m;i++){
int a=edge[i].a,b=edge[i].b,w=edge[i].w;
a=find(a),b=find(b);
if(a!=b){
f[a]=b;
res+=w;
cnt++;
}
}
if(cnt<n-1){
return INF;
}
return res;
}
matrix tree求最小生成树的个数
无向图的最小生成树的个数为对应的基尔霍夫矩阵的任意n-1阶主子式的行列式的绝对值
Kahn拓扑排序
topsort()
bool topsort(){
int hh=0,tt=-1;//tt表示数组中的入度为0的节点的下标
for(int i=1;i<n;i++){
if(!d[i]){
q[++tt]=i;//对于入度为0的节点
}
}
while(hh<=tt){
int t=q[hh++];
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
if(--d[j]==0){
q[++tt]=j;
}
}
}
return tt==n-1; //如果所有节点都入队了,说明存在拓扑序列,否则不存在拓扑序列
}
已知无向图中存在一个环,求该环 dfs,bfs,拓扑排序
vector<int> cir;
stack<int> path;
bool dfs_cir(int u,int p){ //无环图通过p标记父节点
st[u]=true;
path.push(u);
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j!=p){
if(st[j]){//表示已经在前面标记过了
//找出环上的所有点
while(path.top()!=j){
cir.push_back(path.pop());
path.pop();
}
cir.push_back(j);
return true;
}
if(dfs_cir(j,u)){return true;}
}
}
path.pop();
return false;
}
SPFA算法
(1)首先建立一个队列,最初队列中只有起点1
(2)去除队头节点x,扫描他的所有出边(x,y,z),若dist[y]>dist[x]+z;则使用dist[x]+z更新dist[y]。
同时,对于更新节点如果不在队列中,则入队。
(3)重复上述步骤,直到队列为空。
在任意时刻,队列都保存了待扩展的节点,最终,所有节点都会收敛到满足三角不等式。
void spfa(){
memset(d,0x3f,sizeof(d)); //数组d[i]表示节点i到起点1之间的最短路径
memset(v,0,sizeof(v)); //标记节点是否在队列中,如果在则为1,否则为0
d[1]=0,v[1]=1;//起点距离为0,即将入队,标记为1
q.push(1);
while(q.size()){
int x=q.front(),q.pop();
v[x]=0;//节点x出队,标记更改为0
//扫描所有出边
for(int i=h[x];~i;i=ne[i]){
int j=e[i];
int weight=w[i];
if(d[j]>d[x]+weight){
d[j]=d[x]+weight;
if(!v[j]){
q.push(j);
v[j]=1;
}
}
}
}
}
对一个图的连通块进行标记
void dfs(int x){
v[x]=cnt;
for(int i=h[x];~i;i=ne[i]){
int j=e[i];
if(v[j]) continue;
dfs(j);//递归的方式进行标记
}
}
for(int i=1;i<=n;i++){
if(!v[i]){ //v[]标记了每一个点属于哪一个连通块,初始时将所有的都属于0 cnt=0;//从1开始标记
cnt++;
dfs(i);//将同一个连通块的节点全部标记
}
}
tarjan算法求无向图的割点
int num;
void tarjan(int x){
dfn[x]=low[x]=++num;
int flag=0;//标记次数,当x是根节点时
for(int i=h[x];~i;i=ne[i]){
int j=e[i];
if(!dfn[j]){
tarjan(j);
low[x]=min(low[x],low[j]);
if(low[j]>=dfn[x]){
flag++;
if(flag>1||x!=1){
cut[x]=true;
}
}
}else{
low[x]=min(low[x],dfn[j]);
}
}
}
统计删除割点之后每一个连通块中的节点数量
int num,Size[N];
void tarjan(int x){
dfn[x]=low[x]=++num;
int flag=0,Size[x]=1;
int sum=0;//所有子连通块的节点数量总和
for(int i=h[x];~i;i=ne[i]){
int j=e[i];
if(!dfn[j]){
tarjan(j);
Size[x]+=Size[j];
low[x]=min(low[x],low[j]);
if(low[j]>=dfn[x]){
flag++;
sum+=Size[j];
if(flag>1||x!=1){
cut[x]=true;
}
}
}else{
low[x]=min(low[x],dfs[j]);
}
}
}
tarjan算法求无向图中的割边 需要成对标记边
int num;
int bridge[M*2];
void tarjan(int x,int in_edge){
dfn[x]=low[x]=++num;
for(int i=h[x];~i;i=ne[i]){
int j=e[i];
if(!dfn[j]){
tarjan(j);
low[x]=min(low[x],low[j]);
if(low[y]>dfn[j]){
bridge[i]=bridge[i^1]=true;//对双向编号的边同时进行标记
}
}else if(i!=(in_edge^1)){ //需要对无向边双向边去除
low[x]=min(low[x],dfn[j]);
}
}
}