精华内容
下载资源
问答
  • 有向图的拓扑排序

    万次阅读 2016-03-15 23:01:41
    有向图的拓扑排序    有向图的拓扑排序的基本思想是:首先在有向图中选取一个没有前驱的顶点,将其输出,从有向图中删除该顶点,并且删除以该顶点为尾的所有有向图的边。重复以上的步骤,直到图中的所有顶点均输出...

                                                                                   有向图的拓扑排序

        

          本文取自《数据结构与算法》(C语言版)(第三版),出版社是清华大学出版社。

          本博文作为学习资料整理。源代码是VC++ 6.0上可执行程序,我挪到了VS2010中执行。

        在VS2010中新建C++ Win32 控制台应用程序项目,创建结果截图:

               

          有向图的拓扑排序的基本思想是:首先在有向图中选取一个没有前驱的顶点,将其输出,从有向图中删除该顶点,并且删除以该顶点为尾的所有有向图的边。重复以上的步骤,直到图中的所有顶点均输出或是图中的顶点均没有前驱为止。对于后者,说明有向图中存在环,不能进行拓扑排序。

           以下以AOV(Activity On Vertex Network)网为例,演示求解拓扑排序的步骤:

                          

           C++ Win32 控制台应用程序,代码如下:topSort.cpp

      #include "stdafx.h"
      #include<stdio.h>
      #include<string.h>
      #define MAXNODE 20
      typedef struct
      {
        char vertex;
      }VerNode;
    
      typedef struct
      {
        int adj;
      }Arc;
    
      typedef struct
      {
        VerNode vexs[MAXNODE];
        Arc arcs[MAXNODE][MAXNODE];
        int m_numOfVexs;
      }Graph;
    
      int mFind(char aim, VerNode* arry)
      {
        int pos=-1;
        int i=0;
        for(i=0; i<MAXNODE; i++)
        {
          if(aim==arry[i].vertex)
          {
            pos=i;
            return pos;
          }
        }
        return pos;
      }
    
      void showGraph(Graph aGraph, int num)
      {
        int i=0;
        int j=0;
        printf("\n NODES:\n");
        for(i=0; i<num; i++)
        {
          printf(" %c", aGraph.vexs[i].vertex);
        }
        printf("\n ARCS:\n");
        for(i=0; i<num; i++)
        {
          for(j=0; j<num; j++)
          {
            printf(" %d", aGraph.arcs[i][j].adj);
          }
          printf(" \n");
        }
      }
    
      //添加顶点
      void addVexs(Graph* aGraph, char vex)
      {
        aGraph->m_numOfVexs++;
        aGraph->vexs[aGraph->m_numOfVexs].vertex=vex;
      }
    
      //添加边
      void addArcs(Graph* aGraph, char aStart, char aEnd)
      {
        int p_x=mFind(aStart,aGraph->vexs);
        int p_y=mFind(aEnd,aGraph->vexs);
        aGraph->arcs[p_x][p_y].adj=1;
      }
    
      //图的初始化
      void initGraph(Graph* aGraph)
      {
        int i=0;
        int j=0;
        aGraph->m_numOfVexs=-1;
        for(i=0; i<MAXNODE; i++)
        {
          for(j=0; j<MAXNODE; j++)
            aGraph->arcs[i][j].adj=0;
        }
      }
    
      int getInDegree(int i, Graph* aGraph)
      {
        int InDegree=0;
        int j=0;
        for(j=0; j<aGraph->m_numOfVexs; j++)
          InDegree+=aGraph->arcs[j][i].adj;
        return InDegree;
      }
    
      int topSort(Graph* aGraph)
      {
        int i;
        int isOK=1;
        int vexsIsOut[MAXNODE];
        for(i=0; i<aGraph->m_numOfVexs; i++)
        {
          vexsIsOut[i]=0;
        }
        while(isOK==1)
        {
          isOK=0;
          for(i=0; i<aGraph->m_numOfVexs; i++)
          {
            if(vexsIsOut[i]==0&&getInDegree(i,aGraph)==0)
            {
              int j;
              printf("%c ",aGraph->vexs[i].vertex);
              vexsIsOut[i]=1;
              for(j=0; j<aGraph->m_numOfVexs; j++)
              {
                aGraph->arcs[i][j].adj=0;
              }
              isOK=1;
            }
          }
        }
        for(i=0; i<aGraph->m_numOfVexs; i++)
        {
          if(vexsIsOut[i]==0)
            return 0;
        }
        return 1;
      }
    
      int main(void)
      {
        char node='a';
        char input1='a';
        char input2='a';
        //将图初始化
        Graph g_graph;
        initGraph(&g_graph);
    
        //根据用户的输入添加顶点
        printf("Please input the vexs( end with #):\n");
        while(1)
        {
          if(node=='#')
            break;
          if(scanf("%c,",&node)==1)
          {
            if(node=='\n')
              continue;
            addVexs(&g_graph,node);
          }
        }
    
        //根据用户的输入添加边
        printf("Please input arcs, just like this \"startNod,endNode\" \n");
        while(1)
        {
          if(input1=='#')
            break;
          if(scanf("%c,%c",&input1, &input2)==2)
          {
            if(input1=='\n'||input2=='\n')
              continue;
            addArcs(&g_graph, input1, input2);
          }
        }
    
        //输出图
        showGraph(g_graph, g_graph.m_numOfVexs);
    
        printf("The topsort is: \n");
        if(topSort(&g_graph)==0)
          printf("There is a circle in the graph!! \n");
        return 0;
      }
    

           Ctrl+F5执行topSort.cpp代码,结果如下图:

          

    展开全文
  • 有向图的拓扑排序 Method Example 给定一个n个点m条边的有向图,图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1。 若一个由图中所有点构成的序列A满足:对于图...

    有向图的拓扑排序

    Method

    Example

    给定一个n个点m条边的有向图,图中可能存在重边和自环。

    请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1。

    若一个由图中所有点构成的序列A满足:对于图中的每条边(x, y),x在A中都出现在y之前,则称A是该图的一个拓扑序列。

    输入格式

    第一行包含两个整数n和m

    接下来m行,每行包含两个整数x和y,表示存在一条从点x到点y的有向边(x, y)。

    输出格式

    共一行,如果存在拓扑序列,则输出拓扑序列。

    否则输出-1。

    数据范围

    1≤n,m≤1051≤n,m≤105

    输入样例:

    3 3
    1 2
    2 3
    1 3
    

    输出样例:

    1 2 3
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, m;
    int h[N], e[N], ne[N], idx;
    int q[N], d[N];
    
    void add(int a, int b)
    {
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
    }
    
    bool topsort()
    {
        int hh = 0, tt = -1;
        //d[i] 存储点i的入度
        for (int i = 1; i <= n; i ++)
            if (!d[i])
                q[++ tt] = i;//入队
        
        while (hh <= tt)
        {
            
            int t = q[hh ++];
            //枚举t的所有出边
            for(int i = h[t]; i != -1; i = ne[i])
            {
                int j = e[i];
                d[j] --;//删除j
                if (d[j] == 0) q[++ tt] = j;//删除完将j插入队列
            }
        }
        
        return tt == n - 1;
        
    }
    
    int main()
    {
         cin >> n >> m;
         
         memset(h, -1, sizeof h);
         
         
         for (int i = 0; i < m; i ++)
         {
             int a, b;
             cin >> a >> b;
             add(a, b);
             d[b] ++;
         }
         
         if (topsort())
         {
             for (int i = 0; i < n; i ++) printf("%d ", q[i]);
             puts("");
         }
         else puts("-1");
         
         return 0;
    }

     

     

     

     

     

    展开全文
  • 有向图的拓扑排序 Kahn算法

    拓扑排序是对有向无圈图的顶点的一种排序,使得如果存在一条从vi到vj的路径,那么在排序中,vi必须出现在vj的前面

    首先,我们需要准备一个vector<int> link[maxn],link[i] 存放顶点i所有连接到的顶点,同时还要维护一个队列或者栈来存放所有入度为0的顶点。

    下面,直接上图:

    假如有这样一个有向图:
    在这里插入图片描述

    1. 我们发现只有顶点1的入度为0,所以把顶点1给去掉,并把1加入结果数组。res=[1]
      在这里插入图片描述
    2. 目前就还剩顶点2和顶点5的入度为0,随机去掉一个,我们去掉2,并把2加入res数组res=[1,2]

    在这里插入图片描述
    3. 目前顶点5的入度为0,把顶点5给去掉。res=[1,2,5]
    在这里插入图片描述
    4. 目前顶点4的入度为0,把顶点4给去掉。res=[1,2,5,4]
    在这里插入图片描述
    5. 目前顶点3的入度为0,把顶点3给去掉。res=[1,2,5,4,3]

    直到最后不剩下顶点时,排序结束,1 2 5 4 3即为该图的一个拓扑排序。

    细节:

    1. 拓扑排序的结果并不唯一,比如在上面第二步,我们先去掉的是顶点2,如果我们先去掉的是顶点5,那么拓扑排序的结果可能是1 5 4 3 2
    2. 假如图中有环,比如下图,那么所有的顶点的入度都不为0,排序无法进行下去,拓扑排序将不存在。所以可以通过拓扑排序来判断图中有没有环。
      在这里插入图片描述

    代码如下:

    // Kahn算法
    
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define maxn 1024
    vector<int> link[maxn];   //顶点i的邻接表
    queue<int> q;  //存放所有入度为0的顶点
    int in[maxn];   //顶点i的入度
    int n;  //顶点个数
    int m;  //边的个数
    int res[maxn];   //存放排序后的结果
    
    /*
    新增一条由n1指向n2的有向边
    */
    void lnk(int n1,int n2){
        link[n1].push_back(n2);   //n1顶点的邻接表加入n2
        ++in[n2];                 //n2的入度+1
    }
    
    int main() {
    	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
        //建图
    	n = 13;
        m = 15;
        lnk(1,2);
        lnk(1,6);
        lnk(1,7);
        lnk(3,1);
        lnk(3,4);
        lnk(4,6);
        lnk(6,5);
        lnk(7,4);
        lnk(7,10);
        lnk(8,7);
        lnk(9,8);
        lnk(10,11);
        lnk(10,12);
        lnk(10,13);
        lnk(12,13);
        //扫描in数组,将入度为0的顶点加入队列
        for(int i = 1;i <= n;++i){
            if(!in[i]){
                q.push(i);
            }
        }
    
        int index = 0;   //res的下标
        while(!q.empty()){
            int node = q.front();
            q.pop();    //拿出一个结点
            res[index++] = node; //存入结果数组
            //逐一移除跟它相连的边
            for(auto it = link[node].begin();it != link[node].end();++it){
                --in[*it];   //顶点入度-1
                if(!in[*it]){
                    //如果入度为0,加入队列
                    q.push(*it);
                }
            }
        }
        //如果index<n,那么加入结果数组的顶点数量一定是小于n的
        //说明该图有环
        if(index == n){
            for(int i = 0;i<n;++i){
                cout << res[i] << " \n"[i == n-1];
            }
        }else{
            cout << "circulation" << endl;
        }
    
    	return 0;
    }
    

    练习:LeetCode No207. 课程表

    展开全文
  • 有向图的拓扑排序 DFS实现

    DFS是Kahn算法的逆过程,DFS就是一直沿着一个路径走,直到某个顶点没有出度之后再往回走。

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define maxn 1024   //最大顶点数
    bool tag[maxn];   //标记一下顶点i有没有被访问过
    int res[maxn];  //结果数组
    int index = 0;  //结果数组的索引
    vector<int> edges[maxn];   //邻接表
    int n,m;  //n:顶点个数,m:边的个数
    
    
    void dfs(int n){
        //直接标记该顶点已被访问
        tag[n] = 1;
        //逐一dfs
        for(auto it = edges[n].begin();it != edges[n].end();++it){
            if(!tag[*it]){
                dfs(*it);
            }
        }
        //返回之前将该顶点加入结果数组
        res[index++] = n;
    }
    
    /*
    新增一条由n1指向n2的有向边
    */
    void lnk(int n1,int n2){
        edges[n1].push_back(n2);   //n1顶点的邻接表加入n2
    }
    
    int main() {
    	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
        memset(tag,0,sizeof(tag));
        //建图
        n = 13;
        m = 15;
        lnk(1,2);
        lnk(1,6);
        lnk(1,7);
        lnk(3,1);
        lnk(3,4);
        lnk(4,6);
        lnk(6,5);
        lnk(7,4);
        lnk(7,10);
        lnk(8,7);
        lnk(9,8);
        lnk(10,11);
        lnk(10,12);
        lnk(10,13);
        lnk(12,13);
        //从1到n逐一dfs
        for(int i = 1;i<=n;++i){
            if(!tag[i]){
                dfs(i);
            }
        }
        //判断index和n的大小
        //如果index==n,那么排序完成,如果index<n,那么图有环
        if(index == n){
            //需要倒序输出
            for(int i = n-1;i>=0;--i){
                cout << res[i] << " \n"[i == 0];
            }
        }else{
            cout << "circulation" << endl;
        }
    	return 0;
    }
    
    
    
    展开全文
  • 有向图的拓扑排序 拓扑排序是宽度优先搜索的一个很重要的应用场景,下面使用宽度优先搜索代码实现。 #include <iostream> #include <cstring> #include <algorithm> using namespace std; ...
  • 思路: 用数组模拟链表,首先如果能用拓扑排序则其一定是有向无...请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1。 若一个由图中所有点构成的序列A满足:对于图中的每条边(x, y),x在A中都出现在y之
  • 力扣题解,利用有向图的拓扑排序解决课程表的课程依赖问题
  • 有向图的拓扑排序 拓扑排序介绍 什么是拓扑排序? 一个有向图的拓扑排序(Topological sort 或 Topological ordering)是根据其有向边从顶点U到顶点V对其所有顶点的一个线性排序 举个例子:让一个拓扑排序的图中的...
  • 力扣题解,210. 课程表 II,利用有向图的拓扑排序解决课程表的课程依赖问题。
  • 有向图的拓扑排序算法(java实现) import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class TopologicalOrder{ static class Node{ int pos; int val; Node next;...
  • 实现有向图的拓扑排序和关键路径计算。在此基础上,借助OpenCV将图及其关键路径画出来。函数CriticalPath() -> 源文件CriticalPath.cpp*/ 下面将代码贴出 里面有详细的注释 最终的结果:由opencv制成 input....
  • 有向图的拓扑排序问题 -----邻接表存储: 这里的邻接表存储方式其中在vnnode结构体中加入了count(入度)。 在拓扑排序过程中,每次找读入为0的进栈,之后每出栈一个顶点就要循环遍历邻近所有(注意,这里的 所有)有边...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,349
精华内容 1,739
关键字:

有向图的拓扑排序