图论算法模板整理及思路不断更新绝对精品-白红宇

图论算法模板整理及思路不断更新绝对精品

阅读量：6586 次

发布时间：2019-06-24

本文共 14494 字，大约阅读时间需要 48 分钟。

DFS

1 #include
      
        2 #include
       
         3 #include
        
           4 using namespace std; 5 queue
         
          q; 6 int map[1001][1001]; 7 int vis[1001]; 8 int n,m; 9 void bfs(int p)10 {11     q.push(p);12     vis[p]=1;13     printf("%c-->",char(q.front()+64));14     while(q.size()!=0)15     {    16         int k=q.front();17         q.pop();18         for(int i=1;i<=n;i++)19         {20             21             if(vis[i]==0&&map[k][i]==1)22             {23                 printf("%c-->",char(i+64));24                 //q.pop();25                 q.push(i);26                 vis[i]=1;27             }28         }29     }30 }31 int main()32 {33     34     scanf("%d%d",&n,&m);35     for(int i=1;i<=m;i++)36     {37         char x,y;38         //scanf("\n%d %d",&x,&y);39         cin>>x>>y;40         x=x-64;41         y=y-64;42         map[x][y]=map[y][x]=1;43     }44     bfs(1);45     return 0;46 }

DFS

BFS

1 #include
      
        2 #include
       
         3 #include
        
           4 using namespace std; 5 queue
         
          q; 6 int map[1001][1001]; 7 int vis[1001]; 8 int n,m; 9 void bfs(int p)10 {11     q.push(p);12     vis[p]=1;13     printf("%c-->",char(q.front()+64));14     while(q.size()!=0)15     {    16         int k=q.front();17         q.pop();18         for(int i=1;i<=n;i++)19         {20             21             if(vis[i]==0&&map[k][i]==1)22             {23                 printf("%c-->",char(i+64));24                 //q.pop();25                 q.push(i);26                 vis[i]=1;27             }28         }29     }30 }31 int main()32 {33     34     scanf("%d%d",&n,&m);35     for(int i=1;i<=m;i++)36     {37         char x,y;38         //scanf("\n%d %d",&x,&y);39         cin>>x>>y;40         x=x-64;41         y=y-64;42         map[x][y]=map[y][x]=1;43     }44     bfs(1);45     return 0;46 }

BFS

Flyoed

思路：三层循环遍历中间节点

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 int a[101][101]; 6 int pass[101][101]; 7 int main() 8 { 9     memset(a,999999,sizeof(a));10     int n,m;11     scanf("%d%d",&n,&m);12     for(int i=1;i<=m;i++)13     {14         int x,y,zhi;15         scanf("%d%d%d",&x,&y,&zhi);16         a[x][y]=zhi;17         a[y][x]=zhi;18     }19     for(int k=1;k<=n;k++)20     {21         for(int i=1;i<=n;i++)22         {23             for(int j=1;j<=n;j++)24             {25                 if(a[i][j]>a[i][k]+a[k][j])26                 {27                     a[i][j]=a[i][k]+a[k][j];28                     pass[i][j]=k;29                 }30             }31         }32     }33     printf("%d %d\n",a[1][4],a[2][6]);34     printf("%d %d\n",pass[1][4],pass[2][6]);35     return 0;36 }

Flyoed

1 for (k = 1; k <= n; k++)2         for (i = 1; i <= n; i++)3             for (j = 1; j <= n; j++)4 　           dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]);

Flyod求图的连通性

Dijkstra

主要思想：每次找到一个能到达的最近的点，来更新到达其他点的距离

思路：

1.需要一个dis数组记录需要求的点到其他点的最短路径 pre数组记录前驱

2.（1）初始化:dis[]=∞ dis[开始的点]=0 pre[开始的点]=0

　（2）<1>for(int i=1;i<=顶点总数;i++)

　　　　　　找到dis[i]最小的点

　　　　　　vis[找到的点]=1

　　　　　　for(与找到的点相连的点)

　　　　　　if(dis[find]+w[find][i]<dis[i])

　　　　　　{

　　　　　　　　1.松弛

　　　　　　　　2.pre[i]=find 记录前驱

　　　　　　}

end

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 int a[101][101]; 6 int dis[101]; 7 int maxn=0x7f; 8 int vis[1001]; 9 int pass[1001];10 void print(int bg,int ed)11 {12     int ans[101];13     int now=1;14     ans[now]=ed;15     now++;16 //    ans[now]=ed;17     //now++;18     int tmp=pass[ed];19     while(tmp!=bg)20     {21         ans[now]=tmp;22         now++;23         tmp=pass[tmp];24     }25     ans[now]=bg;26     for(int i=now;i>=1;i--)27     {28         if(i!=1)29         printf("%d-->",ans[i]);30         else31         printf("%d",ans[i]);32     }33 }34 int main()35 {36     memset(a,maxn,sizeof(a));37     int n,m;38     int beginn=1;39     scanf("%d%d",&n,&m);40     for(int i=1;i<=m;i++)41     {42         int x,y,zhi;43         scanf("%d%d%d",&x,&y,&zhi);44         a[x][y]=zhi;45         a[y][x]=zhi;46     }47     48     for(int i=1;i<=n;i++)49     {50         if(a[beginn][i]!=maxn)51         {52             dis[i]=a[beginn][i];53         }54     }55     dis[beginn]=0;56     for(int i=1;i<=n;i++)57     {58         int minn=maxn;59         int k=-1;60         for(int j=1;j<=n;j++)61         {62             if(dis[j]<=minn&&vis[j]==0)63             {64                 minn=dis[j];65                 k=j;66             }67         }68         vis[k]=1;69         for(int j=1;j<=n;j++)70         {71             if(dis[k]+a[k][j]<=dis[j])72             {73                 dis[j]=dis[k]+a[k][j];74                 pass[j]=k;75             }76         }77     }78     for(int i=1;i<=n;i++)79     {80     cout<
         
          <<" ";81     if(i==1)cout<

Dijkstra

SPFA

主要思想：初始时将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时结束

思路：需要变量：

　　　 1.需要一个dis数组记录需要求的点到其他点的最短路径

　　　2.pre数组记录前驱

　　　3.queue队列

　　　4.vis数组记录该点是否在队列中

　　begin

　　1.初始化:dis[]=∞ dis[开始的点]=0 pre[开始的点]=0

　　2.while(队列不为空)

　　　（1）取出顶点 vis[顶点]=false

　　　（2）for(与顶点相连的点)

　　　　　　if(dis[find]+w[find][i]<dis[i])

　　　　　　{

　　　　　　　　1.松弛

　　　　　　　　if(i不在队列中)

　　　　　　　　{

　　　　　　　　　　加入队列

　　　　　　　　　　vis[i]=true;

　　　　　　　　}　　　　　　　　　　　

end;

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 int map[101][101]; 7 int dis[101]; 8 bool vis[101]; 9 queue
          
           q;10 int n,m;11 int bg=1;12 void spfa()13 {14     dis[bg]=0;15     vis[bg]=1;16     q.push(bg);17     dis[bg]=0;18     do19     {20         int k=q.front();    21         for(int j=1;j<=n;j++)22         {23             if(dis[j]>dis[k]+map[k][j])24             {25                 dis[j]=dis[k]+map[k][j];26                 if(vis[j]==0)27                 {28                     q.push(j);29                     vis[j]=1;30                 }31             }32         }33         q.pop();34         vis[k]=0;35     }while(q.size()!=0);36     for(int i=1;i<=n;i++)37     cout<
           
            <

SPFA邻接矩阵存储

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int MAXN=30001; 7 const int maxn=0x7fffffff; 8 struct node 9 {10     int u;11     int v;12     int w;13     int next;14 }edge[MAXN]; 15 int num=1;16 int head[MAXN];17 int n,m,begin,end;18 int dis[MAXN];19 int vis[MAXN];20 void spfa()21 {22     for(int i=1;i<=n;i++)dis[i]=maxn;23     queue
          
           q;24     vis[begin]=1;25     q.push(begin);26     dis[begin]=0;27     while(q.size()!=0)28     {29         int p=q.front();30         q.pop();31         vis[p]=0;32         for(int i=head[p];i!=-1;i=edge[i].next)33         {34             if(dis[edge[i].v]>dis[p]+edge[i].w&&dis[p]!=maxn)35             {36                 dis[edge[i].v]=dis[p]+edge[i].w;37                 if(vis[edge[i].v]==0)38                 {39                     q.push(edge[i].v);40                     vis[edge[i].v]=1;41                 }42             }43         }44     }45     printf("%d",dis[end]);46 }47 int main()48 {49     scanf("%d%d%d%d",&n,&m,&begin,&end);50     for(int i=1;i<=n;i++)head[i]=-1;51     for(int i=1;i<=m;i++)52     {53         scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w);54         edge[num].next=head[edge[num].u];55         head[edge[num].u]=num++;56         edge[num].w=edge[num-1].w;57         edge[num].u=edge[num-1].v;58         edge[num].v=edge[num-1].u;59         edge[num].next=head[edge[num].u];60         head[edge[num].u]=num++;61     }62     spfa();63     return 0;64 }

SPFA邻接表存储

http://codevs.cn/problem/1269/

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int MAXN=100001; 7 const int maxn=0xfffffff; 8 struct node 9 {10     int u;11     int v;12     int w;13     int next;14 }edge[MAXN];15 int num=1;16 int head[MAXN];17 int n,m;18 int dis[MAXN];19 int vis[MAXN];// 是否在队列中 20 int tot=0;21 int pre[MAXN];// 记录次短路 22 void spfa()23 {24     dis[1]=0;25     vis[1]=1;26     queue
          
           q;27     q.push(1);28     while(q.size()!=0)29     {30         int p=q.front();31         q.pop();32         vis[p]=0;33         for(int i=head[p];i!=-1;i=edge[i].next)34         {35             int to=edge[i].v;36             if(dis[to]>dis[p]+edge[i].w)37             {38                 pre[to]=dis[to];// 记录下更新之前的长度 即次长 39                 dis[to]=dis[p]+edge[i].w;40                 //if(edge[i].v==n)tot++;41                 if(vis[to]==0)42                 {43                     q.push(to);44                     vis[to]=1;45                 }46             }47             else if(dis[to]!=dis[p]+edge[i].w&&pre[to]>dis[p]+edge[i].w)48             {49                 pre[to]=dis[p]+edge[i].w;// 根据条件，此时需要更新，否则就不是次短路 50                 if(vis[to]==0)51                 {52                     q.push(to);53                     vis[to]=1;54                 }55             }56             if(pre[to]>pre[p]+edge[i].w)// 同理，需要更新 57             {58                 pre[to]=pre[p]+edge[i].w;59                 if(vis[to]==0)60                 {61                     q.push(to);62                     vis[to]=1;63                 }64             }65         }66     }67 }68 int main()69 {70     scanf("%d%d",&n,&m);71     for(int i=1;i<=n;i++)72     {73         head[i]=-1;74         dis[i]=maxn;75         pre[i]=maxn;76     }77     for(int i=1;i<=m;i++)78     {79         scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w);80         edge[num].next=head[edge[num].u];81         head[edge[num].u]=num++;82     }83     spfa();84     if(pre[n]!=maxn)85     printf("%d",pre[n]);86     else87     {88         printf("-1");89     }90     return 0;91 }

SPFA求次短路

单源最短路径输出

主要思想

主要利用递归的思想，一层一层的进行迭代

1 void print(int x)2 {3     if(pre[a][x]==0)return;4     print(pre[a][x]);5     cout<<"->"<

单源最短路的输出

Tarjan算法

思路：

基本思路：

1.初始化

2.入栈

3.枚举：

　　　　1.不在队列中->访问，进行赋值，

　　　　2.在队列中->赋值

4.寻找根->输出结果

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 struct node { 6     int v,next; 7 } edge[1001]; 8 int DFN[1001],LOW[1001]; 9 int stack[1001],heads[1001],visit[1001],cnt,tot,index;10 void add(int x,int y) {11     edge[++cnt].next=heads[x];12     edge[cnt].v = y;13     heads[x]=cnt;14     return ;15 }16 void tarjan(int x) { //代表第几个点在处理。递归的是点。17     DFN[x]=LOW[x]=++tot;// 新进点的初始化。18     stack[++index]=x;//进站19     visit[x]=1;//表示在栈里20     for(int i=heads[x]; i!=-1; i=edge[i].next) {21         if(!DFN[edge[i].v]) {22             //如果没访问过23             tarjan(edge[i].v);//往下进行延伸，开始递归24             LOW[x]=min(LOW[x],LOW[edge[i].v]);//递归出来，比较谁是谁的儿子／父亲，就是树的对应关系，涉及到强连通分量子树最小根的事情。25         } else if(visit[edge[i].v ]) {26             //如果访问过，并且还在栈里。27             LOW[x]=min(LOW[x],DFN[edge[i].v]);//比较谁是谁的儿子／父亲。就是链接对应关系28         }29     }30     if(LOW[x]==DFN[x]) { //发现是整个强连通分量子树里的最小根。31         do {32             printf("%d ",stack[index]);33             visit[stack[index]]=0;34             index--;35         } while(x!=stack[index+1]);//出栈，并且输出。36         printf("\n");37     }38     return ;39 }40 int main() {41     memset(heads,-1,sizeof(heads));42     int n,m;43     scanf("%d%d",&n,&m);44     int x,y;45     for(int i=1; i<=m; i++) {46         scanf("%d%d",&x,&y);47         add(x,y);48     }49     for(int i=1; i<=n; i++)50         if(!DFN[i])  tarjan(1);//当这个点没有访问过，就从此点开始。防止图没走完51     return 0;52 }

Tarjan

Kruskal算法

主要思想：

Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。直到选取了n-1条边为止。

思路：

算法描述:

初始化并查集。father[x]=x。

2.tot=0

3.将所有边用快排从小到大排序。sort

4.计数器 k=0;

5.for (i=1; i<=M; i++) //循环所有已从小到大排序的边

if 这是一条u,v不属于同一集合的边(u,v)(因为已经排序，所以必为最小)，

begin

　①合并u,v所在的集合，相当于把边(u,v)加入最小生成树。

　 ②tot=tot+W(u,v)

③k++

④如果k=n-1,说明最小生成树已经生成，则break;

end;

6. 结束，tot即为最小生成树的总权值之和。

http://codevs.cn/problem/3315/

3315 时空跳跃者的魔法

1 #include
          
            2 #include
           
             3 #include
            
              4 #include
             
               5 #include
              
                6 using namespace std; 7 const int MAXN=1000001; 8 const int maxn=0x7fffffff; 9 int x[MAXN];10 int y[MAXN];11 int z[MAXN];12 int tas[MAXN];13 struct node14 {15     int u;16     int v;17     double w;18     int next;19 }edge[MAXN];20 int num=1;21 int head[MAXN];22 int f[MAXN];23 int comp(const node & a, const node & b)24 {25     if(a.w
               
                p)79 {80 printf("Death");81 }82 else83 {84 printf("%.0lfTas",tot);85 }86 return 0;87 }

Kruskal

拓扑排序

算法实现：

a) 数据结构：indgr[i]: 顶点i的入度;

　　 stack[ ]: 栈

b) 初始化:top=0 (栈顶指针置零)

c) 将初始状态所有入度为0的顶点压栈

d) I=0 (计数器)

e) while 栈非空(top>0)

i. 栈顶的顶点v出栈；top-1; 输出v；i++；

ii. for v的每一个后继顶点u

1. indgr[u]--; u的入度减1

2. if （u的入度变为0）顶点u入栈

f) 算法结束

http://codevs.cn/problem/2833/

2833 奇怪的梦境

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6 using namespace std; 7 const int MAXN=30001; 8 struct node 9 {10     int u;11     int v;12     int w;13     int next;14 }edge[MAXN];15 int num=1;16 int head[MAXN];17 int rudu[MAXN];18 int tot=0;19 int n,m;20 stack
            
             s;21 void topsort()22 {23 for(int i=1;i<=n;i++)24 {25 if(rudu[i]==0)26 {27 s.push(i);28 tot++;29 }30 }31 while(s.size()!=0)32 {33 int p=s.top();34 s.pop();35 for(int i=head[p];i!=-1;i=edge[i].next)36 {37 rudu[edge[i].v]--;38 if(rudu[edge[i].v]==0)39 {40 s.push(edge[i].v);41 tot++;42 }43 }44 }45 if(tot==n)printf("o(∩_∩)o");46 else47 {48 printf("T_T\n%d",n-tot);49 //printf("%d",tot);50 }51 }52 int main()53 {54 55 scanf("%d%d",&n,&m);56 for(int i=1;i<=n;i++)head[i]=-1;57 for(int i=1;i<=m;i++)58 {59 scanf("%d%d",&edge[num].u,&edge[num].v);60 edge[num].next=head[edge[num].u];61 rudu[edge[num].v]++;62 head[edge[num].u]=num++;63 }64 topsort();65 return 0;66 }