精华内容
下载资源
问答
  • 图论相关算法

    2013-05-27 16:59:52
    各种图论算法,包括 dijkstra fold prim kruskaral 深度优先搜索,广度优先搜索 拓扑排序 aoe网络
  • 数学建模图论相关算法,介绍了无向图、有向图等定义,Dijkstra算法等
  • 晚上学习了一些图论相关算法: 单源最短路径算法: Bellman-Ford 算法: Bellman-Ford 算法是一种用于计算带权有向图中单源最短路径(SSSP:Single-Source Shortest Path)的算法。该算法由 Richard Bellman 和 ...

    晚上学习了一些图论相关算法:

    单源最短路径算法:

    Bellman-Ford 算法:

    Bellman-Ford 算法是一种用于计算带权有向图中单源最短路径(SSSP:Single-Source Shortest Path)的算法。该算法由 Richard Bellman 和 Lester Ford 分别发表于 1958 年和 1956 年,而实际上 Edward F. Moore 也在 1957 年发布了相同的算法,因此,此算法也常被称为 Bellman-Ford-Moore 算法。

    Bellman-Ford 算法和 Dijkstra 算法同为解决单源最短路径的算法。对于带权有向图 G = (V, E),Dijkstra 算法要求图 G 中边的权值均为非负,而 Bellman-Ford 算法能适应一般的情况(即存在负权边的情况)。一个实现的很好的 Dijkstra 算法比 Bellman-Ford 算法的运行时间要低。

    Bellman-Ford 算法采用动态规划(Dynamic Programming)进行设计,实现的时间复杂度为 O(V*E),其中 V 为顶点数量,E 为边的数量。Dijkstra 算法采用贪心算法(Greedy Algorithm)范式进行设计,普通实现的时间复杂度为 O(V2),若基于 Fibonacci heap 的最小优先队列实现版本则时间复杂度为 O(E + VlogV)。

    Bellman-Ford 算法描述:

    创建源顶点 v 到图中所有顶点的距离的集合 distSet,为图中的所有顶点指定一个距离值,初始均为 Infinite,源顶点距离为 0;
    计算最短路径,执行 V - 1 次遍历;
    对于图中的每条边:如果起点 u 的距离 d 加上边的权值 w 小于终点 v 的距离 d,则更新终点 v 的距离值 d;
    检测图中是否有负权边形成了环,遍历图中的所有边,计算 u 至 v 的距离,如果对于 v 存在更小的距离,则说明存在环;

     

    代码:

     1 //从顶点from指向顶点to的权值为cost的边
     2 struct edge{
     3     int from,to,cost;
     4 };
     5 
     6 edge es[MAX_V];//
     7 
     8 int d[MAX_V];  //最短距离
     9 int V,E;       //V是顶点数,E是边数
    10 
    11 //求解从顶点s出发到所有点的最短距离
    12 void shortest_path(int s)
    13 {
    14     for(int i=0; i<V; i++)  
    15         d[i] = INF;  //0x3f3f3f3f 
    16     d[s]=0;
    17     while(true){
    18         bool update=false;
    19         for(int i=0; i<E; i++){
    20             edge e=es[i];
    21             if(d[e.from]!=INF && d[e.to] >d[e.from]+e.cost){
    22                 uopdate=true;
    23             }
    24         }
    25         if(!update)
    26             break;
    27     }     
    28 }

     

     

    Dijkstra算法  

    1.定义概览 

    Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。注意该算法要求图中不存在负权边。

    问题描述:在无向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到由顶点 V0 到其余各点的最短路径。(单源最短路径)

     

    2.算法描述

    1)算法思想:设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径 , 就将加入到集合S中,直到全部顶点都加入到S中,算法就结束了),第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离,是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

    2)算法步骤:

    a.初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},若v与U中顶点u有边,则<u,v>正常有权值,若u不是v的出边邻接点,则<u,v>权值为∞。

    b.从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。

    c.以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。

    d.重复步骤b和c直到所有顶点都包含在S中。

    执行动画过程如下图

    STL代码:

     1 struct edge{int to, cost;};//图的边  
     2 typedef pair<int,int> P;//保存的结果,first为最短距离,second为相应顶点  
     3   
     4 int V;  
     5 vector<edge> G[MAX_V];  
     6 int d[MAX_V];  
     7   
     8 void dijkstra(int s){  
     9     //通过制定greater<P>参数,堆按照first从小到大的顺序取出值
    10     priority_queue<P,vector<P>,greater<P>> que;  
    11     fill(d,d+V,INF);  
    12     d[s]=0;  
    13     que.push(P(0,s));  
    14   
    15     while(!que.empty()){  
    16         P p=que.top(); que.pop();  
    17         int v=p.second;  
    18         for(int i=0;i<G[v].size;i++){  
    19             edge e=G[v][i];  
    20             if(d[e.to]>d[v]+e.cost){  
    21                 d[e.to]=d[v]+e.cost;  
    22                 que.push(P(d[e.to],e.to));  
    23             }  
    24         }  
    25     }  
    26 }  

     代码实现:

     1 #define INF 0x3f3f3f3f
     2 #define MAX 101
     3 
     4 int dis[MAX],vis[MAX];
     5 int mp[MAX][MAX];
     6 
     7 int dijkstra(int s,int e)
     8 {
     9     memset(vis,0,sizeof(vis));
    10     for(int i=1; i<=e; i++)
    11         dis[i]=mp[s][i];
    12     dis[s]=0;
    13     vis[s]=1;
    14     while(true){
    15         int min=INF;
    16         int p;
    17         for(int i=1; i<=e; i++){
    18             if(!vis[i] && dis[i]<min){
    19                 min=dis[i];
    20                 p=i;
    21             }
    22         }
    23         if(min==INF)
    24             break;
    25         vis[p]=1;
    26         for(int i=1; i<=e; i++){
    27             if(!vis[i] && dis[i]>min+mp[p][i])
    28                 dis[i]=min+mp[p][i];
    29         }
    30     }
    31 }

     

    SPFA: 

    是一种求单源最短路的算法

    几乎所有的最短路算法其步骤都可以分为两步

    1.初始化

    2.松弛操作

    判断有无负环:

      如果某个点进入队列的次数超过N次则存在负环(SPFA无法处理带负环的图)

     1 int spfa(int s)
     2 {
     3     queue<int> q;
     4     while(!q.empty())
     5         q.pop();
     6     q.push(s);
     7     dis[s]=1.0;
     8     vis[s]=1;
     9     num[s]++;
    10     while(!q.empty()){
    11         s=q.front();
    12         q.pop();  
    13         vis[s]=0;
    14         for(int i=0; i<list[s].size(); i++){
    15             int p=list[s][i];
    16             if(dis[p]<dis[s]*mp[s][p]){
    17                 dis[p]=dis[s]*mp[s][p];
    18                 if(!vis[p]){
    19                     vis[p]=1;
    20                     q.push(p);
    21                     num[p]++;
    22                     if(num[p]==n)
    23                         return 0;
    24                 }
    25             }
    26         }
    27     }
    28     return 1;
    29 }

     

     

     1 int spfa_bfs(int s)
     2 {
     3     queue <int> q;
     4     memset(d,0x3f,sizeof(d));
     5     d[s]=0;
     6     memset(c,0,sizeof(c));
     7     memset(vis,0,sizeof(vis));
     8 
     9     q.push(s);  vis[s]=1; c[s]=1;
    10     //顶点入队vis要做标记,另外要统计顶点的入队次数
    11     int OK=1;
    12     while(!q.empty())
    13     {
    14         int x;
    15         x=q.front(); q.pop();  vis[x]=0;
    16         //队头元素出队,并且消除标记
    17         for(int k=f[x]; k!=0; k=nnext[k]) //遍历顶点x的邻接表
    18         {
    19             int y=v[k];
    20             if( d[x]+w[k] < d[y])
    21             {
    22                 d[y]=d[x]+w[k];  //松弛
    23                 if(!vis[y])  //顶点y不在队内
    24                 {
    25                     vis[y]=1;    //标记
    26                     c[y]++;      //统计次数
    27                     q.push(y);   //入队
    28                     if(c[y]>NN)  //超过入队次数上限,说明有负环
    29                         return OK=0;
    30                 }
    31             }
    32         }
    33     }
    34 
    35     return OK;
    36 
    37 }

     

     

    求多源、无负权边的最短路:

    Floyd算法

    1.定义概览

    Floyd-Warshall算法(Floyd-Warshall algorithm)是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3),空间复杂度为O(N2)。

     

    2.算法描述

    1)算法思想原理:

         Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话,首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题,我们需要为这个目标重新做一个诠释(这个诠释正是动态规划最富创造力的精华所在)

          从任意节点i到任意节点j的最短路径不外乎2种可能,1是直接从i到j,2是从i经过若干个节点k到j。所以,我们假设Dis(i,j)为节点u到节点v的最短路径的距离,对于每一个节点k,我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立,如果成立,证明从i到k再到j的路径比i直接到j的路径短,我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j),这样一来,当我们遍历完所有节点k,Dis(i,j)中记录的便是i到j的最短路径的距离。

    2).算法描述:

    a.从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。   

    b.对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

    3).Floyd算法过程矩阵的计算----十字交叉法

     

    代码:

    1 int d[MAX_V][MAX_V];  //d[u][v] 表示边e=(u,v)的权值(不存在时设为INF,不过d[i][i]=0)
    2 int v;
    3 
    4 void warshall_floyd(){
    5     for(int k=0; k<V; k++)
    6         for(int i=0; i<V; i++)
    7             for(int j=0; j<V; j++)
    8                 d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    9 }

     

    最小生成树: 

    Prim算法

    1.概览

    普里姆算法Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点英语Vertex (graph theory)),且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克英语Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆英语Robert C. Prim)独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。

    给定一个无向图,如果它的某个子图中任意两个顶点都互相连通并且是一棵树,那么这课树就叫做生成树(Spanning Tree).如果边上有权值,那么是的边权和最小的生成树叫做最小生成树(MST,Minimum Spanning Tree) 

     

     

    2.算法简单描述

    1).输入:一个加权连通图,其中顶点集合为V,边集合为E;

    2).初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),Enew = {},为空;

    3).重复下列操作,直到Vnew = V:

    a.在集合E中选取权值最小的边<u, v>,其中u为集合Vnew中的元素,而v不在Vnew集合当中,并且v∈V(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);

    b.将v加入集合Vnew中,将<u, v>边加入集合Enew中;

    4).输出:使用集合Vnew和Enew来描述所得到的最小生成树。

     

     代码:

     1 void prim()
     2 {
     3     memset(vis,0,sizeof(vis));
     4     memset(dis,INF,sizeof(dis)); 
     5     dis[1]=0;
     6     ans=0;
     7     dis[0]=INF;
     8     while(true){
     9         int m=0;
    10         for(int i=1; i<=n; i++){
    11             if(!vis[i] && dis[i]<dis[m])
    12                 m=i;
    13         }
    14         if(m==0)
    15             break;
    16         vis[m]=1;
    17         ans+=dis[m];
    18         for(int i=1; i<=n; i++)
    19             dis[i]=min(dis[i],mp[m][i]);
    20     }
    21 }

     

    Kruskal算法

     

    1.概览

    Kruskal算法是一种用来寻找最小生成树的算法,由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是,Kruskal算法在图中存在相同权值的边时也有效。

     

    2.算法简单描述

    1).记Graph中有v个顶点,e个边

    2).新建图Graphnew,Graphnew中拥有原图中相同的e个顶点,但没有边

    3).将原图Graph中所有e个边按权值从小到大排序

    4).循环:从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中

                    if 这条边连接的两个节点于图Graphnew中不在同一个连通分量中

                                             添加这条边到图Graphnew

     

     

     1 struct edge{int u,v,cost;};
     2 
     3 bool cmp(edge &e1,const edge &e2){
     4     return e1.cost < e2.cost;
     5 }
     6 
     7 edge es[MAX_E];  
     8 int V,E;   //顶点数和边数
     9 
    10 int kruskal(){
    11     sort(es,es+E,cmp);       //按照edge.cost的顺序从小到大排列
    12     init_union_find(V);      //并查集的初始化
    13     int res=0;
    14     for(int i=0; i<E; i++){
    15         edge e=es[i];
    16         if(!same(e.u,e.v)){
    17             unite(e.u,e.v);
    18             res+=e.cost;
    19         }
    20     }
    21     return res;
    22 }

     

     

     

     

     

     

     

     图论所刷题目的链接:   http://www.cnblogs.com/qscqesze/p/4547000.html

     

     

    参考书籍:<<挑战程序设计竞赛>>

    参考博客:http://blog.csdn.net/yutianzuijin/article/details/11618651

                http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

                http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html

                http://www.cnblogs.com/scau20110726/archive/2012/11/18/2776124.html

                http://blog.csdn.net/v_july_v/article/details/6181485

    转载于:https://www.cnblogs.com/wangmengmeng/p/5277225.html

    展开全文
  • 图论相关算法.ppt

    2019-12-06 02:29:00
    图 论 Elementary Graph Algorithms 图的定义 图是由顶点集合以及顶点间的关系的集合组成的一种关系的数学表示 G = VE 其中顶点是由有穷非空集合 顶点之间的关系边是有穷集合 Path (x , y)表示从x到y的一条单向通路...
  • acm图论相关算法

    2015-04-12 08:41:02
    acm题的图算法,虽然只有一部分,但还是可以用的
  • 图论相关算法模板

    2018-11-28 17:26:00
    Tarjan算法: 强连通分量(边双联通分量):(堆栈存点) 1 int head[maxn]; 2 struct edge 3 { 4 int to,nxt,from; 5 }e[50005]; 6 int cnt; 7 inline void addedge(int u,int v) 8 { 9 e[+...

    先贴代码,开坑待填

     

    Tarjan算法:

    强连通分量(边双联通分量):(堆栈存点)

     1 int head[maxn];
     2 struct edge
     3 {
     4     int to,nxt,from;
     5 }e[50005];
     6 int cnt;
     7 inline void addedge(int u,int v)
     8 {
     9     e[++cnt].to=v;
    10     e[cnt].from=u;
    11     e[cnt].nxt=head[u];
    12     head[u]=cnt;
    13 }
    14 int dfn[maxn],low[maxn],f[maxn],ttime,tot,num[maxn];
    15 bool vis[maxn];
    16 stack<int>st;
    17 void dfs(int u,int fa)
    18 {
    19     st.push(u);
    20     low[u]=dfn[u]=++ttime;
    21     f[u]=fa;
    22     vis[u]=1;
    23     for(int i=head[u];i;i=edge[i].nxt)
    24     {
    25         int v=edge[i].to;
    26         //if(v==fa) continue;对于无向图需要特殊处理
    27         if(!dfn[v])
    28         {
    29             dfs(v,u);
    30             low[u]=min(low[u],low[v]);
    31         }
    32         else if(vis[v])
    33             low[u]=min(dfn[v],low[u]);
    34     }
    35     if(low[u]==dfn[u])
    36     {
    37         ++tot;
    38         while(1)
    39         {
    40             int tmp=st.top();
    41             num[tmp]=tot;
    42             vis[tmp]=0;
    43             st.pop();
    44             if(tmp==u)
    45                 break;
    46         }
    47     }
    48 }
    View Code

     点双联通分量:(堆栈存边)

     1 int cnt;
     2 int head[maxn];
     3 struct Edge
     4 {
     5     int nxt,to,val;
     6 }edge[maxn*10];
     7 inline void addedge(int x,int y){edge[++cnt].to=y;edge[cnt].nxt=head[x];head[x]=cnt;}
     8 int dfn[maxn],low[maxn],f[maxn],ttime,tot,num[maxn];
     9 int iscut[maxn];
    10 typedef pair<int,int> P;
    11 stack<P>st;
    12 void dfs(int u,int fa)
    13 {
    14     low[u]=dfn[u]=++ttime;
    15     f[u]=fa;
    16     int son=0;
    17     for(int i=head[u];i;i=edge[i].nxt)
    18     {
    19         int v=edge[i].to;
    20         if(v==fa)
    21             continue;
    22         if(!dfn[v])
    23         {
    24             son++;
    25             st.push(P(u,v));
    26             dfs(v,u);
    27             low[u]=min(low[u],low[v]);
    28             if(dfn[u]<=low[v])
    29             {
    30                 iscut[u]=1;
    31                 ++tot;
    32                 while(1)
    33                 {
    34                     P tmp=st.top();
    35                     st.pop();
    36                     num[tmp.first]=num[tmp.second]=tot;//属于点双连通分量
    37                     if(tmp.first==u&&tmp.second==v)
    38                         break;
    39                 }
    40             }
    41         }
    42         else if(dfn[v]<dfn[u])//后向边
    43         {
    44             low[u]=min(dfn[v],low[u]);
    45             st.push(P(u,v));
    46         }
    47     }
    48     if(fa==0&&son==1)
    49         iscut[u]=0;
    50 }
    View Code

    桥的判定:

    边(u,v)中dfn[u]<low[v] 

    割点的判定:

    边(u,v)中dfn[u]<=low[v](非dfs根)

    儿子个数大于1(dfs根)

    2-SAT

    建图:

    原文:https://blog.csdn.net/pengwill97/article/details/82083764

    判断是否可行:

    将原图用tarjan强连通分量缩点,若任意一个点都与其对立点不在同一个强连通分支里,则存在可行方案,反则不可

     

    最大流:

     

     1 const int MAXN = 2010;//点数的最大值
     2 const int MAXM = 1200010;//边数的最大值
     3 const int INF = 0x3f3f3f3f;
     4 struct Edge
     5 {
     6     int to,next,cap,flow;
     7 } edge[MAXM]; //注意是 MAXM
     8 int tol;
     9 int head[MAXN];
    10 void init()
    11 {
    12     tol = 2;
    13     memset(head,-1,sizeof(head));
    14 }
    15 void addedge(int u,int v,int w,int rw = 0)
    16 {
    17     edge[tol].to = v;
    18     edge[tol].cap = w;
    19     edge[tol].flow = 0;
    20     edge[tol].next = head[u];
    21     head[u] = tol++;
    22     edge[tol].to = u;
    23     edge[tol].cap = rw;
    24     edge[tol].flow = 0;
    25     edge[tol].next = head[v];
    26     head[v] = tol++;
    27 }
    28 int Q[MAXN];
    29 int dep[MAXN],cur[MAXN],sta[MAXN];
    30 bool bfs(int s,int t,int n)
    31 {
    32     int front = 0,tail = 0;
    33     memset(dep,-1,sizeof(dep[0])*(n+1));
    34     dep[s] = 0;
    35     Q[tail++] = s;
    36     while(front < tail)
    37     {
    38         int u = Q[front++];
    39         for(int i = head[u]; i != -1; i = edge[i].next)
    40         {
    41             int v = edge[i].to;
    42             if(edge[i].cap > edge[i].flow && dep[v] == -1)
    43             {
    44                 dep[v] = dep[u] + 1;
    45                 if(v == t)return true;
    46                 Q[tail++] = v;
    47             }
    48         }
    49     }
    50     return false;
    51 }
    52 int dinic(int s,int t,int n)
    53 {
    54     int maxflow = 0;
    55     while(bfs(s,t,n))
    56     {
    57         for(int i = 0; i < n; i++)cur[i] = head[i];
    58         int u = s, tail = 0;
    59         while(cur[s] != -1)
    60         {
    61             if(u == t)
    62             {
    63                 int tp = INF;
    64                 for(int i = tail-1; i >= 0; i--)
    65                     tp = min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
    66                 maxflow += tp;
    67                 for(int i = tail-1; i >= 0; i--)
    68                 {
    69                     edge[sta[i]].flow += tp;
    70                     edge[sta[i]^1].flow -= tp;
    71                     if(edge[sta[i]].cap-edge[sta[i]].flow == 0)
    72                         tail = i;
    73                 }
    74                 u = edge[sta[tail]^1].to;
    75             }
    76             else if(cur[u] != -1 && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to])
    77             {
    78                 sta[tail++] = cur[u];
    79                 u = edge[cur[u]].to;
    80             }
    81             else
    82             {
    83                 while(u != s && cur[u] == -1)
    84                     u = edge[sta[--tail]^1].to;
    85                 cur[u] = edge[cur[u]].next;
    86             }
    87         }
    88     }
    89     return maxflow;
    90 }
    View Code

     

     

    费用流:

     

     1 #include<bits/stdc++.h>
     2 const int MAXN = 10000;
     3 const int MAXM = 100000;
     4 const int INF = 0x3f3f3f3f;
     5 struct Edge
     6 {
     7     int to,next,cap,flow,cost;
     8 } edge[MAXM];
     9 int head[MAXN],tol;
    10 int pre[MAXN],dis[MAXN];
    11 bool vis[MAXN];
    12 int N;//节点总个数,节点编号从 0∼N-1
    13 void init(int n)
    14 {
    15     N = n;
    16     tol = 0;
    17     memset(head,-1,sizeof(head));
    18 }
    19 void addedge(int u,int v,int cap,int cost)
    20 {
    21     edge[tol].to = v;
    22     edge[tol].cap = cap;
    23     edge[tol].cost = cost;
    24     edge[tol].flow = 0;
    25     edge[tol].next = head[u];
    26     head[u] = tol++;
    27     edge[tol].to = u;
    28     edge[tol].cap = 0;
    29     edge[tol].cost = -cost;
    30     edge[tol].flow = 0;
    31     edge[tol].next = head[v];
    32     head[v] = tol++;
    33 }
    34 bool spfa(int s,int t)
    35 {
    36     std::queue<int>q;
    37     for(int i = 0; i < N; i++)
    38     {
    39         dis[i] = INF;
    40         vis[i] = false;
    41         pre[i] = -1;
    42     }
    43     dis[s] = 0;
    44     vis[s] = true;
    45     q.push(s);
    46     while(!q.empty())
    47     {
    48         int u = q.front();
    49         q.pop();
    50         vis[u] = false;
    51         for(int i = head[u]; i != -1; i = edge[i].next)
    52         {
    53             int v = edge[i].to;
    54             if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost )
    55             {
    56                 dis[v] = dis[u] + edge[i].cost;
    57                 pre[v] = i;
    58                 if(!vis[v])
    59                 {
    60                     vis[v] = true;
    61                     q.push(v);
    62                 }
    63             }
    64         }
    65     }
    66     if(pre[t] == -1)
    67         return false;
    68     else
    69         return true;
    70 }
    71 //返回的是最大流,cost 存的是最小费用
    72 int minCostMaxflow(int s,int t,int &cost)
    73 {
    74     int flow = 0;
    75     cost = 0;
    76     while(spfa(s,t))
    77     {
    78         int Min = INF;
    79         for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
    80         {
    81             if(Min > edge[i].cap - edge[i].flow)
    82                 Min = edge[i].cap - edge[i].flow;
    83         }
    84         for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
    85         {
    86             edge[i].flow += Min;
    87             edge[i^1].flow -= Min;
    88             cost += edge[i].cost * Min;
    89         }
    90         flow += Min;
    91     }
    92     return flow;
    93 }
    View Code

     

    转载于:https://www.cnblogs.com/iamamori/p/10033434.html

    展开全文
  • 题目稍微有难度,但是前三道还算比较水,第一道题因为是图论题,当时一看就是裸的tarjan算法的模板题,但是好久没写这算法,临时上网找的模板,可惜忘了重边处理,就没过,在此也总结下图论相关算法及知识: ...
    今天是暑假集训的第四场比赛,题目稍微有难度,但是前三道还算比较水,第一道题因为是图论题,当时一看就是裸的tarjan算法的模板题,但是好久没写这算法,临时上网找的模板,可惜忘了重边处理,就没过,在此也总结下图论的相关算法及知识:


    1、图的存储
    (1)邻接矩阵:这个方法不用多说了,最傻逼简单的方法,但是今天在网上学到了一个用邻接矩阵处理重边的方法,里面map[i][j]存放的是i到j之间边的条数,为什么要这么做呢,因为tarjan算法求的是割点和割边,当求到一个点low[v]>dfn[v],因为有重边的存在,所以还不能马上断定这个点使割点,还得判断map[u][v]==1才行
    (2)邻接表:这里不想说数据结构书上那个很复杂方法了,这里直接用STL里面的vector存储即可,这样存储的好处就是能有效利用空间,缺点就是查询慢,比邻接矩阵慢
    具体做法:
    struct node
    {
        int v;//边的终点
        int w;//边的权值
        node(int _v,int _w)
        {
            v = _v;
            w = _w;
        }
    };
    vector<int>g[maxn];
    void add_edge(int u,int v,int w)
    {
        g[u].push_back(node(v,w));
    }
    (3)前向星,邻接表
    struct node
    {
        int v;
        int w;
        int next;
    }e[maxn];
    void add(int u,int v,int w)
    {
        e[id].v = v;
        e[id].w = w;
        e[id].next = first[u];
        first[u] = id++;
    }
    2、图的基本算法
    (1)求一个图是否连通
    这个基本就是跑一遍DFS就好了,但是必须掌握的算法,所谓图是否连通,我理解的就是图中任意一点都有一条路径能到达其他任一点
    代码:
    void dfs(int x)
    {
        vis[x] = 1;//设置访问标记数组
        dot++;//表示已经访问过的点数
        for(int i=first[x];i!=-1;i=e[i].next)//当访问到一个点时,向他的边延伸搜索
        {
            int v = e[i].v;
            if(!vis[v])
            {
                dfs(v);
            }
        }
    }
    //最后如果一个图联通,那么dot==n//图中点的个数
    (2)求图的割点,割边算法
    这个就是tarjan算法,这里不详细解释了,有时间单独写一篇日志,这里直接贴模板吧,感觉大多数tarjan算法的代码都差不多,这里稍微解释下什么叫割点、割边,割点就是删除一个连通图中某一个点后,连通分量增加,以此类推,割边就是删除一条边后,连通分量有所增加
    代码:
    void tarjan(int u,int fa)
    {
        dfn[u]=low[u]=++idex ;
        for(int i=first[u];i!=-1;i=e[i].next){
            int v=e[i].v ;
            int w=e[i].w ;
            if(!dfn[v]){
                tarjan(v,u) ;
                low[u]=Min(low[u],low[v]) ;
                if(low[v]>dfn[u]&&map[u][v]==1)
                         bridge.push_back(w) ;
            }
            else if(v!=fa)
                low[u]=Min(low[u],dfn[v]) ;
        }
    }
    //其实代码不是很难,只要记住一点,就是low[v]>dfn[u],当满足这个条件的时候,就是割点
    展开全文
  • 包括:TSP算法,图遍历算法,最短路算法,最小生成树算法,最大流及工具箱图论函数。
  • COGS图论相关算法 最小生成树 Kruskal+ufs int ufs(int x) { return f[x] == x ? x : f[x] = ufs(f[x]); } int Kruskal() { int w = 0; for(int i=0; i<n; i++) f[i] = i; s...
    • COGS图论相关算法

    • 最小生成树

      • Kruskal+ufs

        int ufs(int x) {
            return f[x] == x ? x : f[x] = ufs(f[x]);
        }
        int Kruskal() {
            int w = 0;
            for(int i=0; i<n; i++)
                f[i] = i;
            sort(e, e+n);
            for(int i=0; i<n; i++) {
                int x = ufs(e[i].u), y = ufs(e[i].v);
                if(x != y) {
                    f[x] = y;
                    w += e[i].w;
                }
            } return w;
        }
                    


      • Prim

        int Prim() {
            int w = 0;
            priority_queue<pair<int, int> > q;
            bool l[N] = {0};
            l[1] = 1; q.push(make_pair(0, 1));
            for(int k=1; k<n; k++) {
                int u = q.top().second; q.pop();
                for(int i=0; i<G[u].size(); i++)
                    if(!l[G[u][i]])
                        q.push(make_pair(-c[u][i], G[u][i]));
                while(!q.empty() && l[q.top().second])
                    q.pop();
                l[q.top().second] = 1;
                w += -q.top().first;
                q.pop();
            } return w;
        }
                    


    • 最短路径

      • Dijkstra+priority_queue

        void Dijkstra(int s) {
            priority_queue<pair<int, int> > q;
            bool l[N] = {0}; l[s] = 1;
            fill_n(f, n, INF); f[s] = 0;
            q.push(make_pair(-f[s], s));
            while(!q.empty()) {
                int u = q.front().second; q.pop();
                for(int i=0; i<G[u].size(); i++) {
                    int v = G[u][i];
                    if(f[v] > f[u] + c[u][i]) {
                        f[v] = f[u] + c[u][i];
                        if(!l[v]) {
                            l[v] = 1;
                            q.push(make_pair(-f[v], v));
                        }
                    }
                }
            }
        }
                    


      • Bellman-Ford (SPFA)

        void BellmanFord(int s) { // SPFA
            queue<int> q;
            bool l[N] = {0}; l[s] = 1;
            fill_n(f, n, INF); f[s] = 0;
            q.push(s);
            while(!q.empty()) {
                int u = q.front(); q.pop();
                l[u] = 0;
                for(int i=0; i<G[u].size(); i++) {
                    int v = G[u][i];
                    if(f[v] > f[u] + c[u][i]) {
                        f[v] = f[u] + c[u][i];
                        if(!l[v]) {
                            l[v] = 1;
                            q.push(v);
                        }
                    }
                }
            }
        }
                    


      • Floyd

        void Floyd() {
            for(int k=0; k<n; k++)
                for(int i=0; i<n; i++)
                    for(int j=0; j<n; j++)
                        f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
        }
                    


    • 二分图

      • ufs 验证

      • Hungary

        bool DFS(int u) {
            for(int i=0; i<G[u].size(); i++) {
                int v = G[u][i];
                if(!l[v]) {
                    l[v] = 1;
                    if(!f[v] || DFS(f[v])) {
                        f[v] = u;
                        return true;
                    }
                }
            } return false;
        }
        int Hungary() {
            int w = 0;
            for(int i=0; i<n; i++) {
                fill_n(l, l+n, 0);
                if(DFS(i))
                    w++;
            } return w;
        }
                    


    • 连通分量

      • Tarjan

        stack<int> s;
        void Tarjan(int u) {
            dfn[u] = low[u] = ++time;
            l[u] = 1;
            s.push(u);
            for(int i=0; i<G[u].size(); i++) {
                int v = G[u][i];
                if(!dfn[v]) {
                    Tarjan(v);
                    low[u] = min(low[u], low[v]);
                } else if(l[v])
                    low[u] = min(low[u], dfn[v]);
            }
            if(dfn[u] == low[u]) {
                w++;
                do {int v;
                    l[v = s.top()] = 0;
                    f[v] = w;
                    s.pop();
                } while(u != v);
            }
        }
        void SCC() {
            fill_n(dfn, n, 0);
            for(int i=0; i<n; i++)
                if(!dfn(i))
                    Tarjan(i);
        }
                    


    • *网络流

      • 最大流:Edmonds-Karp

      • 费用流:Bellman-Ford 找增广路,或者用贪心求解

    联赛会考什么预测


    联赛六道题目可能会考什么

    1.模拟,栈和队列
    2.动态规划,贪心
    3.搜索,对搜索结果的处理,搜索中的模拟
    4.模拟,数学;字符串处理
    5.建图,连通分支、最小生成树、二分图;二分查找
    6.网络流类似 AOV 网可用贪心解;数论,高精度

    基本上就是这样了,其他的想到了也不会做。

    转载于:https://www.cnblogs.com/tham/p/6827178.html

    展开全文
  • 其涵盖了数据结构中图章节的大部分算法 #include #include #include #include #include #ifndef ONCE_GRAPH #define ONCE_GRAPH const int MAX_NUM=32767; const int QUEUESIZE=100; struct ArcNode {int adjvex; ...
  •  最小生成树(Kruscal算法) #include "iostream" #include "cstdlib" #include "cstring" #include "cstdio" #define N 10000 #define M 100000 using namespace std; struct edge //边集 { int start; //起点 ...
  • 图论常识汇总: 所有顶点之间都有边的图称为完全图 n个顶点的无向图有n(n-1)/2条边,n个顶点的有向图有n(n-1)条边 一个顶点的度数表示他的边的个数 所有顶点的度数除以二分之一就是边数。如果是有向图,那么还...
  • 图论相关算法汇总(一)

    千次阅读 2015-09-15 16:17:26
     算法描述:  (1)将起始节点放入队列尾部  (2)While(队列不为空)  取得并删除队列首节点Node  处理该节点Node  把Node的未处理相邻节点加入队列尾部 三. 深度优先遍历(DFS)  ...
  • 1. 最小生成树(Kruscal算法) 基本思想:kruskal 算法总共选择 n-1 条边(共n个点),所使用的贪婪准则是:从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路...
  • 最小生成树 Kruskal+ufs int ufs(int x) { return f[x] == x ? x : f[x] = ufs(f[x]); } int Kruskal() { int w = 0; for(int i=0; in; i++) f[i] = i; sort(e, e+n); for(int i=0; in
  • 前段时间学习图论相关算法,就做了一个C#版的演示程序,这个程序涉及到了如下算法: 深度优先搜索遍历(Depth First Search), 广度优先搜索遍历(Breath Frist Search), 最小生成树(Minimum Spanning Tree), ...
  • 这篇文章是笔者,学习《数据结构与算法分析——java语言描述第三版》一书的第九章图论部分,根据书中的提示加上自己的理解,编写的源代码。注意点:1.使用HashMap + LinkedList的方式来实现邻接表。2.实现了广度优先...
  • 图论算法——最短路径算法 图论算法——最小生成树算法 图论算法——强连通分量 有向图 无向图 图论算法——并查集 (在kruskal中有用到,在这里不再多说) 图论算法——拓扑排序与关键路径算法 ...
  • 图论算法相关

    2019-10-16 19:21:02
    二、最短路径算法 https://mp.weixin.qq.com/s/i5YNtG-rDrCGEeKD9B8VWQ 迪杰斯特拉: 使用一张表,记录起点到所有点的距离,并且不断刷新 如果需要得到路径,可以使用一个from[]数组,表示当前下标的前一个。 ...
  • 数据结构-图论相关功能及算法
  • 图论相关算法

    2015-02-05 00:00:08
    算法具体的形式包括: 单源最短路径 已知起始结点, 求最短路径的问题. 考虑使用 Dijkstra 算法. 全局最短路径 求图中所有的最短路径. 考虑使用 Floyd 算法. 两点最短路径 已知起点和终点, 求两结点之间的...
  • 图论的概念,算法,以及相关的程序设计 pdg格式文件
  • 图论算法与程序设计 各种常用的图论算法以及相关程序
  • 在这里做一下总结,主要针对近期学到的一些建模技巧,同时也非常感谢有朋友能够给出图论算法相关的精彩讲解或者知识链接。 算法总结: 欧拉回路问题:判断图是否存在欧拉回路或者欧拉通路,输出一条欧拉回路。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 646
精华内容 258
关键字:

图论相关算法