判斷給定的圖是否是有向無環圖

判斷給定的圖是否是有向無環圖，方法是應用拓撲排序，代碼如下：

[cpp]
#include<iostream>  
#include<list>  
#include<stack>  
using namespace std; 
 
class Graph { 
    int vertexNum; 
    list<int> *adjacents; 
public: 
    Graph(int _vertexNum) { 
        vertexNum = _vertexNum; 
        adjacents = new list<int>[vertexNum]; 
    } 
    void findIndegree(int *indegree, int n); 
    bool topologicalSort(); 
    void addEdge(int v, int w); 
}; 
 
void Graph::addEdge(int v, int w) { 
    adjacents[v].push_back(w); 
} 
 
void Graph::findIndegree(int *indegree, int n) { 
    int v; 
    list<int>::iterator iter; 
    for(v = 0; v < vertexNum; v++) { 
        for (iter = adjacents[v].begin(); iter != adjacents[v].end(); iter++) 
            indegree[*iter]++; 
    } 
} 
 
bool Graph::topologicalSort() { 
    int ver_count = 0; 
    stack<int> m_stack; 
    int *indegree = new int[vertexNum]; 
    memset(indegree, 0, sizeof(int) * vertexNum); 
    findIndegree(indegree, vertexNum); 
    int v; 
    for (v = 0; v < vertexNum; v++) 
        if (0 == indegree[v]) 
            m_stack.push(v); 
    while (!m_stack.empty()) { 
        v = m_stack.top(); 
        m_stack.pop(); 
        cout << v << " "; 
        ver_count++; 
        for (list<int>::iterator iter = adjacents[v].begin(); iter != adjacents[v].end(); iter++) { 
            if (0 == --indegree[*iter]) 
                m_stack.push(*iter); 
        } 
    } 
    cout << endl; 
    if (ver_count < vertexNum) 
        return false; 
    return true; 
} 
 
int main(int argc, char *argv[]) { 
    Graph g(6); 
    g.addEdge(5, 2); 
    g.addEdge(5, 0); 
    g.addEdge(4, 0); 
    g.addEdge(4, 1); 
    g.addEdge(2, 3); 
    g.addEdge(3, 1); 
    if (g.topologicalSort()) 
        cout << "it is a topological graph" << endl; 
    else 
        cout << "it is not a topological graph" << endl; 
    cin.get(); 
    return 0; 
} 

#include<iostream>
#include<list>
#include<stack>
using namespace std;

class Graph {
 int vertexNum;
 list<int> *adjacents;
public:
 Graph(int _vertexNum) {
  vertexNum = _vertexNum;
  adjacents = new list<int>[vertexNum];
 }
 void findIndegree(int *indegree, int n);
 bool topologicalSort();
 void addEdge(int v, int w);
};

void Graph::addEdge(int v, int w) {
 adjacents[v].push_back(w);
}

void Graph::findIndegree(int *indegree, int n) {
 int v;
 list<int>::iterator iter;
 for(v = 0; v < vertexNum; v++) {
  for (iter = adjacents[v].begin(); iter != adjacents[v].end(); iter++)
   indegree[*iter]++;
 }
}

bool Graph::topologicalSort() {
 int ver_count = 0;
 stack<int> m_stack;
 int *indegree = new int[vertexNum];
 memset(indegree, 0, sizeof(int) * vertexNum);
 findIndegree(indegree, vertexNum);
 int v;
 for (v = 0; v < vertexNum; v++)
  if (0 == indegree[v])
   m_stack.push(v);
 while (!m_stack.empty()) {
  v = m_stack.top();
  m_stack.pop();
  cout << v << " ";
  ver_count++;
  for (list<int>::iterator iter = adjacents[v].begin(); iter != adjacents[v].end(); iter++) {
   if (0 == --indegree[*iter])
    m_stack.push(*iter);
  }
 }
 cout << endl;
 if (ver_count < vertexNum)
  return false;
 return true;
}

int main(int argc, char *argv[]) {
 Graph g(6);
 g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);
 if (g.topologicalSort())
  cout << "it is a topological graph" << endl;
 else
  cout << "it is not a topological graph" << endl;
 cin.get();
 return 0;
}