有向图的拓扑排序

andalousie

对于有向图，只需要在IsConnected里面只定义一个方向值等于一，另一个值不定义即可。graph.h

1. #if !defined (GRAPH_H)
   
2. #define GRAPH_H
   
3. #include "stack.h"
   
4. 
   
5. /************************************************************
   
6. 
   
7. Class Graph represents a Graph [V,E] having vertices V and
   
8. edges E.
   
9. 
   
10. ************************************************************/
    
11. class Graph {
    
12.     private:
    
13.         int    _n;  /// n is the number of vertices in the graph
    
14.         int ** _A;  /// A stores the edges between two vertices
    
15.         bool * visited;
    
16.         IStack reverse;
    
17.     public:
    
18.         Graph(int size = 2);
    
19.         ~Graph();
    
20.         bool isConnected(int, int);
    
21.         void addEdge(int x, int y);
    
22.         void DFS(int);
    
23.         void Toposort();
    
24. };
    
25. 
    
26. #endif

复制代码

graph.cc

1. #include <iostream>
   
2. #include "graph.h"
   
3. #include "stack.h"
   
4. 
   
5. Graph::Graph(int size) {
   
6.     int i, j;
   
7.     if (size < 2) _n = 2;
   
8.     else _n = size;
   
9.     _A = new int*[_n];
   
10.     for (i = 0; i < _n; ++i)
    
11.         _A[i] = new int[_n];
    
12.     for (i = 0; i < _n; ++i)
    
13.         for (j = 0; j < _n; ++j)
    
14.             _A[i][j] = 0;
    
15. }
    
16. 
    
17. Graph::~Graph() {
    
18.     for (int i = 0; i < _n; ++i)
    
19.     delete [] _A[i];
    
20.     delete [] _A;
    
21.     delete [] visited;
    
22. }
    
23. 
    
24. /******************************************************
    
25. Checks if two given vertices are connected by an edge
    
26. @param u vertex
    
27. @param v vertex
    
28. @return true if connected false if not connected
    
29. ******************************************************/
    
30. bool Graph::isConnected(int x, int y) {
    
31.     return (_A[x-1][y-1] == 1);
    
32. }
    
33. 
    
34. /*****************************************************
    
35. adds an edge E to the graph G.
    
36. @param u vertex
    
37. @param v vertex
    
38. *****************************************************/
    
39. void Graph::addEdge(int x, int y) {
    
40.     _A[x-1][y-1] = 1;
    
41. }
    
42. 
    
43. /*****************************************************
    
44. performs Depth First Search
    
45. @param x initial vertex
    
46. *****************************************************/
    
47. void Graph::DFS(int v)
    
48. {
    
49.     visited[v] = true;
    
50.     for(int w = 1; w <= _n; ++w)
    
51.     {
    
52.             if(isConnected(v, w) && !visited[w]) DFS(w);
    
53.     }
    
54.     reverse.push(v);
    
55. }
    
56. 
    
57. void Graph::Toposort(){
    
58.         visited = new bool[_n+1];
    
59.         for (int i = 1; i <= _n; ++i)
    
60.         visited[i] = false;
    
61.     for (int v = 1; v <= _n; ++v)
    
62.     {
    
63.             if(!visited[v]) DFS(v);
    
64.     }
    
65.     while(!reverse.isEmpty())
    
66.             std::cout << reverse.pop() << " ";
    
67. }

复制代码

stack.h, stack.cc参照我另一篇文章里面的代码。
Graph_search.cpp

1. #include <iostream>
   
2. #include "graph.h"
   
3. using namespace std;
   
4. 
   
5. int main(){   
   
6.         /** Creates a graph with 12 vertices */
   
7.     Graph g1(7);
   
8. 
   
9.     /** Adds edges to the graph */
   
10.     g1.addEdge(1, 6); g1.addEdge(1, 3);
    
11.     g1.addEdge(1, 2); g1.addEdge(4, 7);
    
12.     g1.addEdge(4, 6); g1.addEdge(4 ,5);
    
13.     g1.addEdge(6, 5); g1.addEdge(7, 5);
    
14.     g1.addEdge(7, 1); g1.addEdge(4, 3);
    
15.     g1.addEdge(2, 5);
    
16. 
    
17.     /** Explores all vertices findable from vertex 1 */
    
18.     g1.Toposort();
    
19. }

复制代码

cable5881

谢谢楼主分享！！！！！！！！

tlwangxd

学习

leslie初见

必须得顶下

tlwangxd

学习

Ayfkm

正在学习到需要用到这方面知识，谢谢楼主分享