判断给定的图是否是有向无环图

判断给定的图是否是有向无环图，方法是应用拓扑排序，代码如下：

[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;
}

补充：软件开发 , C++ ,