图的存储

假设是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*]; //无向图，建图时边的个数为两倍

int head[maxn],tot=; ///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=; i<=n; i++)

        for(int j=head[i]; j！=-; 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=;

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=;j<=n;j++)///找出入度为0的点，放入最小优先队列，小的值先弹出

    {

        if(indegree[j]==) {

            myque.push(j);

        }

    }

    for(int i=;i<=n;i++)

    {

        int toptmp=myque.top();

        ans.push_back(toptmp);///把已找出的数放入数组

        myque.pop();

        for(int j=;j<=n;j++)

        {

            if(graph[toptmp][j])

            {

                indegree[j]--;///删除第一个数后，它指向的点的入度-1

                if(indegree[j]==)///如果入度为0，加入队列

                    myque.push(j);

            }

        }

    }

///最后输出即可

    for(int i=;i<ans.size()-;i++)

        printf("%d ",ans[i]);

    printf("%d\n",ans[ans.size()-]);

}

int main()

{

    int n=,m=;

    while(scanf("%d %d",&n,&m)!=EOF)

    {

        memset(indegree, , sizeof(indegree));

        memset(graph, false, sizeof(graph));

        for (int i = ; 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 ;

}

拓扑序列

最小代价生成树

一个有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[][],low[];///g是邻接矩阵,low是当前顶点到源点的最短距离

bool vis[];///该点是否被访问

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=;i<m;i++)///输入图

    {

      int a,b,c;

      scanf("%d%d%d",&a,&b,&c);

      g[a][b]=c;///单向图

     }

    for(i=;i<n;i++)///初始化此时low数组

      low[i]=cost[][i];

    vis[]=true;

    for(i=;i<=n;i++)

    {

      int minn=inf;

      for(j=;j<=n;j++)///

      {

        if(!vis[j]&&low[j]<minn)

        {

          minn=low[j];

          k=j;

        }

      }

      vis[k]=true;

      for(j=;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 ;

}

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=;i<=n;i++)

        for(int j=;j<=n;j++)

            dist[i][j]=g[i][j];

    int min_circle=INF;

    for(int k=;k<=n;k++)///枚举k

    {

        ///先判断环，后更新，保证判断环时的dist[i][j]不经过 k

        for(int i=;i<k;i++)

        {

            for(int j=i+;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=;i<=n;i++)

        {

            for(int j=;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求无向图的最小环

巴特西

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

图的存储

DFS/BFS

拓扑序列

适用问题：

最小代价生成树

最短路径

最新文章

热门文章