数据结构:图--拓扑排序

2014年11月12日 1点热度 0条评论 来源: lanmolei814

拓扑排序

拓扑排序

    在实际应用中,有向图的边可以看做是顶点之间制约关系的描述。把顶点看作是一个个任务,则对于有向边<Vi,Vj>表明任务Vj的启动需等到任务Vi完成之后,也就是说任务Vi先于任务Vj完成。对于一个有向图,找出一个顶点序列,且序列满足:若顶点Vi和Vj之间有一条边<Vi,Vj>,则在此序列中顶点Vi必在顶点Vj之前。这样的一个序列就称为有向图的拓扑序列(topological order)。

步骤

  1. 从有向图中选取一个没有前驱(入度为0)的顶点输出。
  2. 删除图中所有以它为起点的弧。

重复上述两个步骤,此时会出现两种情形
1.所有顶点都已输出,输出序列就是拓扑序列。
2.已没有无前驱的顶点,但任然有顶点没有输出,这表明该有向图是有环的。
可见拓扑排序可以检测有向图是否有环。
必须指出,即使是存储结构已确定,拓扑序列也不一定是唯一的。拓扑排序序列不仅跟存储结构有关也与具体采用的算法有关。

算法说明

    使用一个int型的数组indegree,来表示每个顶点的入度。于是,通过查找数组indegree就可得到前驱为零的顶点。下面的代码采取另一种做法:使用一队列,入度为零的顶点入队。这样每次输出入度为零的顶点时,只需出队即可,不必每次都检测整个indegree数组。
    这也说明拓扑序列不是唯一的。若每次都检测indegree数组,则输出的是入度为零的顶点中下标最小的。而使用队列则不一定是这样,它是先入度为零的先输出。

代码

类定义
[cpp] 
view plain
copy

  1. #include<iostream>    
  2. #include<iomanip>  
  3. #include<queue>  
  4. using namespace std;  
  5. /* 
  6. 用邻接矩阵实现图   
  7. 拓扑排序必须是有向图 
  8. */  
  9. class Graph  
  10. {  
  11. private:  
  12.     //顶点数    
  13.     int numV;  
  14.     //边数    
  15.     int numE;  
  16.     //顶点的入度  
  17.     int *indegree;  
  18.     //邻接矩阵    
  19.     int **matrix;  
  20. public:  
  21.     Graph(int numV);  
  22.     //建图    
  23.     void createGraph(int numE);  
  24.     //析构方法    
  25.     ~Graph();  
  26.     //获取顶点数    
  27.     int getVerNums()  
  28.     {  
  29.         return numV;  
  30.     }  
  31.     //获取边数    
  32.     int getEdgeNums()  
  33.     {  
  34.         return numE;  
  35.     }  
  36.     //拓扑排序  
  37.     void topologicalSort();  
  38.     //打印邻接矩阵    
  39.     void printAdjacentMatrix();  
  40.     //检查输入    
  41.     bool check(intint);  
  42. };  

类实现
[cpp] 
view plain
copy

  1. //构造函数,指定顶点数目  
  2. Graph::Graph(int numV)  
  3. {  
  4.     //对输入的顶点数进行检测  
  5.     while (numV <= 0)  
  6.     {  
  7.         cout << "顶点数有误!重新输入 ";  
  8.         cin >> numV;  
  9.     }  
  10.     this->numV = numV;  
  11.     //构建邻接矩阵,并初始化  
  12.     matrix = new int*[numV];  
  13.     int i, j;  
  14.     for (i = 0; i < numV; i++)  
  15.         matrix[i] = new int[numV];  
  16.     //由于权值对于拓扑排序并无作用,故采取无权图的做法  
  17.     for (i = 0; i < numV; i++)  
  18.     for (j = 0; j < numV; j++)  
  19.         matrix[i][j] = 0;  
  20.     //构建顶点的入度数组,并初始化  
  21.     indegree = new int[numV];  
  22.     for (i = 0; i < numV; i++)  
  23.         indegree[i] = 0;  
  24. }  
  25. void Graph::createGraph(int numE)  
  26. {  
  27.     /* 
  28.     对输入的边数做检测 
  29.     一个numV个顶点的有向图,最多有numV*(numV - 1)条边 
  30.     */  
  31.     while (numE < 0 || numE > numV*(numV - 1))  
  32.     {  
  33.         cout << "边数有问题!重新输入 ";  
  34.         cin >> numE;  
  35.     }  
  36.     this->numE = numE;  
  37.     int tail, head, i;  
  38.     i = 0;  
  39.     cout << "输入每条边的起点(弧尾)、终点(弧头)" << endl;  
  40.     while (i < numE)  
  41.     {  
  42.         cin >> tail >> head;  
  43.         while (!check(tail, head))  
  44.         {  
  45.             cout << "输入的边不正确!请重新输入 " << endl;  
  46.             cin >> tail >> head;  
  47.         }  
  48.         matrix[tail][head] = 1;  
  49.         indegree[head]++;  
  50.         i++;  
  51.     }  
  52. }  
  53. Graph::~Graph()  
  54. {  
  55.     int i;  
  56.     for (i = 0; i < numV; i++)  
  57.         delete[] matrix[i];  
  58.     delete[]matrix;  
  59.     delete[]indegree;  
  60. }  
  61. //拓扑排序  
  62. void Graph::topologicalSort()  
  63. {  
  64.     int i, vertex;  
  65.     queue<int> q;  
  66.     //入度为零的顶点入队  
  67.     for (i = 0; i < numV; i++)  
  68.     if (indegree[i] == 0)  
  69.         q.push(i);  
  70.     bool *visited = new bool[numV];  
  71.     for (i = 0; i < numV; i++)  
  72.         visited[i] = false;  
  73.     while (!q.empty())  
  74.     {  
  75.         vertex = q.front();  
  76.         q.pop();  
  77.         cout << setw(4) << vertex;  
  78.         visited[vertex] = true;  
  79.         for (i = 0; i < numV; i++)  
  80.         if (matrix[vertex][i] == 1)  
  81.         {  
  82.             //调整入度,入度为0则需入队  
  83.             if (!(--indegree[i]))  
  84.                 q.push(i);  
  85.         }  
  86.     }  
  87.     cout << endl;  
  88.     for (i = 0; i < numV; i++)  
  89.     if (!visited[i])  
  90.         cout << "该有向图有环!";  
  91.     cout << endl;  
  92.     delete[]visited;  
  93. }  
  94. //打印邻接矩阵    
  95. void Graph::printAdjacentMatrix()  
  96. {  
  97.     int i, j;  
  98.     cout.setf(ios::left);  
  99.     cout << setw(4) << " ";  
  100.     for (i = 0; i < numV; i++)  
  101.         cout << setw(4) << i;  
  102.     cout << endl;  
  103.     for (i = 0; i < numV; i++)  
  104.     {  
  105.         cout << setw(4) << i;  
  106.         for (j = 0; j < numV; j++)  
  107.             cout << setw(4) << matrix[i][j];  
  108.         cout << endl;  
  109.     }  
  110. }  
  111. bool Graph::check(int tail, int head)  
  112. {  
  113.     if (tail < 0 || tail >= numV || head < 0 || head >= numV)  
  114.         return false;  
  115.     return true;  
  116. }  

主函数
[cpp] 
view plain
copy

  1. int main()  
  2. {  
  3.     cout << "******拓扑排序***by David***" << endl;  
  4.     int numV, numE;  
  5.     cout << "建图..." << endl;  
  6.     cout << "输入顶点数 ";  
  7.     cin >> numV;  
  8.     Graph graph(numV);  
  9.     cout << "输入边数 ";  
  10.     cin >> numE;  
  11.     graph.createGraph(numE);  
  12.     cout << "打印邻接矩阵..." << endl;  
  13.     graph.printAdjacentMatrix();  
  14.     cout << "拓扑排序..."<<endl;  
  15.     graph.topologicalSort();  
  16.     system("pause");  
  17.     return 0;  
  18. }  

运行









完整代码下载:拓扑排序

    原文作者:lanmolei814
    原文地址: https://blog.csdn.net/lanmolei814/article/details/41053679
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。