判断给定的图是不是有向无环图实例代码
本文导语: 代码如下:#include#include#includeusing namespace std; class Graph { int vertexNum; list *adjacents;public: Graph(int _vertexNum) { vertexNum = _vertexNum; adjacents = new list[vertexNum]; } void findIndegree(int *indegree, int n); bool topologicalSort(); void addEdge(int v, int...
#include
#include
#include
using namespace std;
class Graph {
int vertexNum;
list *adjacents;
public:
Graph(int _vertexNum) {
vertexNum = _vertexNum;
adjacents = new list[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::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 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