图论相关知识（DFS、BFS、拓扑排序、最小代价生成树、最短路径）

时间：2020-07-23 02:23:37 收藏：0 阅读：157

图的存储

假设是n点m边的图：

邻接矩阵：很简单，但是遍历图的时间复杂度和空间复杂度都为n^2，不适合数据量大的情况

邻接表：略微复杂一丢丢，空间复杂度n+m，遍历图的时间复杂度为m，适用情况更广

前向星：静态链表，即用数组实现邻接表的功能。对于每个顶点，前向星存储的是该顶点的邻接边而非邻接点，head[maxn]存储的是顶点信息，edge[maxm]存储的是顶点对应的边的信息

struct Edge
{
    int to;///某个顶点u的邻接点 
    int next;///顶点u的下一条邻接边的编号 
    int val;///该邻接边的权值 
    Edge(){}
    Edge(int _to,int _next,int _val){
    to=_to;next=_next;val=_val;
} edge[maxm*2]; //无向图，建图时边的个数为两倍

int head[maxn],tot=0; ///head用来表示以i为起点的第一条边存储的位置，tot读入边的计数器
void add_edge(int from,int to,int valt)///在图中添加边，O(M)
{
    edge[tot]=Edge(to,head[from],valt);
    head[from]=tot++;
}
void read()  //遍历所有边，O(N*M)
{
    for(int i=0; i<=n; i++)
        for(int j=head[i]; j！=-1; j=edge[j].next)
}

前向星

DFS/BFS

DFS（深度优先搜索）：递归

BFS（广度优先搜索）：队列（访问顶点，顶点出队，搜索相邻顶点入队；只要队列不空，则重复如下操作：队首元素出队，从队首元素搜索相邻下一步）

记忆化搜索：需要提前计算打表，或者将已经访问的元素保存

适用问题：最优解、计数问题、图论等

最优解问题：DFS通常是搜索所有可能的结果来求最优解；BFS本身一层层向下搜索的特点，适合求解最优问题；
计数问题：DFS彻底完成一个分支之后再去进行下一个分支，并且搜索所有可能结果，所以更适合计数问题；BFS因为队列里同时有多个未完成的分支、所以在解计数问题中并不常见；
图论：DFS、BFS是图论中遍历图的方式，在最短路、迷宫类游戏中很常见。（BFS求最短路径，DFS求所有完整路径）

拓扑排序

适用问题：

在某一个有向图graph中，假设每一条有向边(u,v)代表节点u必须排在节点v的前面，那么按照这样的规则，将所有的节点进行排序，最终得出的序列就称为拓扑序列。只要能将事物抽象成有向图，并要求按规则排序，那么就可以考虑拓扑排序，比如选修课程的安排、按胜负排名次等。
拓扑排序只适用于有向无环图，所以使用拓扑排序的第一步就是先将问题抽象成有向图，进行图的初始化、建立等工作，然后运行拓扑排序算法即可。
顶点的顺序是保证所有指向它的下个节点在被指节点前面！(例如A—>B—>C那么A一定在B前面，B一定在C前面)。所以，这个核心规则下只要满足即可，所以拓扑排序序列不一定唯一！
简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

算法步骤：

新建node类，包含节点数值和它的指向(这里直接用list集合替代链表了)
初始化，添加每个节点指向的时候同时被指的节点入度+1！(A—>C)那么C的入度+1；
扫描一遍所有node。将所有入度为0的点加入一个栈(队列)。
当栈(队列)不空的时候，抛出其中任意一个node(栈就是尾，队就是头，顺序无所谓，上面分析了只要同时入度为零可以随便选择顺序)。将node输出，并且node指向的所有元素入度减一。如果某个点的入度被减为0，那么就将它加入栈(队列)。
重复上述操作，直到栈为空。

const int maxnum=505;
bool graph[maxnum][maxnum];///邻接矩阵，保存图
int indegree[maxnum];///每个点的入度
void top_sort(int n)///对n个数进行拓扑排序
{
    vector<int> ans;///保存拓扑序
    priority_queue<int, vector<int>, greater<int> >  myque;///维护节点入度
    for(int j=1;j<=n;j++)///找出入度为0的点，放入最小优先队列，小的值先弹出
    {
        if(indegree[j]==0) {
            myque.push(j);
        }
    }
    for(int i=1;i<=n;i++)
    {
        int toptmp=myque.top();
        ans.push_back(toptmp);///把已找出的数放入数组
        myque.pop();
        for(int j=1;j<=n;j++)
        {
            if(graph[toptmp][j])
            {
                indegree[j]--;///删除第一个数后，它指向的点的入度-1
                if(indegree[j]==0)///如果入度为0，加入队列
                    myque.push(j);
            }
        }
    }
///最后输出即可
    for(int i=0;i<ans.size()-1;i++)
        printf("%d ",ans[i]);
    printf("%d\n",ans[ans.size()-1]);
}
int main()
{
    int n=0,m=0;
    while(scanf("%d %d",&n,&m)!=EOF) 
    {
        memset(indegree, 0, sizeof(indegree));
        memset(graph, false, sizeof(graph));
        for (int i = 0; i < m; i++) 
        {
            int p1, p2;
            scanf("%d %d",&p1, &p2);
            if (!graph[p1][p2])
                    indegree[p2]++; ///统计p2的入度
            graph[p1][p2] = true;
        }
        top_sort(n);
    }
    return 0;
}

拓扑序列

最小代价生成树

一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的n-1边，同时这些边的权值和最小。最小生成树是权值之和最小的极小生成树。（假设N点M边）

Prime算法：邻接矩阵实现，时间复杂度O（N^2），对点贪心，适合稠密图

输入：一个加权连通图，其中顶点集合为V，边集合为E；
初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
重复下列操作，直到Vnew = V：
- 在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
- 将v加入集合Vnew中，将<u, v>边加入集合Enew中；
输出：使用集合Vnew和Enew来描述所得到的最小生成树。

Kruskal算法：邻接表实现，复杂度O(E*lnE)，对边贪心，适用于稀疏图.

记Graph中有v个顶点，e个边
新建图Graph_new，Graph_new中拥有原图中相同的e个顶点，但没有边
将原图Graph中所有e个边按权值从小到大排序
循环：从权值最小的边开始遍历每条边，直至图Graph中所有的节点都在同一个连通分量中（if 这条边连接的两个节点于图Graph_new中不在同一个连通分量中，则添加这条边到图Graph_new中）

最短路径

单源最短路径——Dijkstra：

单源最短路问题，可以得到一点到其他各点之间的最短路
边的权值不能为负
使用邻接矩阵，算法的运行时间是 O(N^2)。使用邻接表，时间复杂度O(MlogN)

const int inf=0x3f3f3f3f;
int g[605][605],low[605];///g是邻接矩阵,low是当前顶点到源点的最短距离
bool vis[605];///该点是否被访问
int main()
{
  int m,m,i,j,k;
  while(scanf("%d%d",&n,&m)!=EOF)
  {
    memset(g,inf,sizeof(g));
    memset(low,inf,sizeof(low));
    memset(vis,inf,sizeof(vis));
    for(i=0;i<m;i++)///输入图
    {
      int a,b,c;
      scanf("%d%d%d",&a,&b,&c);
      g[a][b]=c;///单向图
     }
    for(i=1;i<n;i++)///初始化此时low数组
      low[i]=cost[1][i];
    vis[1]=true;
    for(i=2;i<=n;i++)
    {
      int minn=inf;
      for(j=1;j<=n;j++)///
      {
        if(!vis[j]&&low[j]<minn)
        {
          minn=low[j];
          k=j;
        }
      }
      vis[k]=true;
      for(j=1;j<=n;j++)///更新最短距离
     {
        if(!vis[j]&&low[k]+g[k][j]<low[j])
        {
          low[j]=low[k]+g[k][j];
        }
      }
  }
  if(low[n]==inf)
    printf("-1\n");
  else
    printf("%d\n",low[n]);
  return 0;  
}

Dijkstra单源最短路径

全源最短路径——Floyed：

多源最短路问题，可以得到任意两点之间的最短路；查找无向图中最小环
边的权值不能为负值
使用邻接矩阵，时间复杂度是O(N^3)。不适用于大量数据。

int n,g[maxn][maxn];///g[i][j]表示从i到j的距离，inf表示i，j之间不直接连通
int dist[maxn][maxn];///dist[i][j]表示i到j的最短距离
int floyed()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dist[i][j]=g[i][j];
    int min_circle=INF;
    for(int k=1;k<=n;k++)///枚举k
    {
        ///先判断环，后更新，保证判断环时的dist[i][j]不经过 k
        for(int i=1;i<k;i++)
        {
            for(int j=i+1;j<k;j++)
            {
                if(dist[i][j]!=INF&&g[i][k]!=INF&&g[j][k]!=INF)///环至少要有3个结点
                    min_circle=min(min_circle,dist[i][j]+g[i][k]+g[j][k]);
                    ///i-j不经过k的最短路 + 边i-k + 边j-k
            }
        }
        
        ///以下和求全源最短路一致，更新以k为中介点的最短路
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(dist[i][k]!=INF&&dist[k][j]!=INF)
                    dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    return min_circle;
}

Floyed求无向图的最小环

原文：https://www.cnblogs.com/Littlejiajia/p/13359977.html