看图判断是不是有向无环图
#include
#include
#include
using namespace std;
class Graph {
int vertexNum;
list
public:
Graph(int _vertexNum) {
vertexNum = _vertexNum;
adjacents = new list
}
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
for(v = 0; v for (iter = adjacents[v].begin(); iter != adjacents[v].end(); iter++)
indegree[*iter]++;
}
}
bool Graph::topologicalSort() {
int ver_count = 0;
stack
int *indegree = new int[vertexNum];
memset(indegree, 0, sizeof(int) * vertexNum);
findIndegree(indegree, vertexNum);
int v;
for (v = 0; v if (0 == indegree[v])
m_stack.push(v);
while (!m_stack.empty()) {
v = m_stack.top();
m_stack.pop();
cout ver_count++;
for (list
if (0 == --indegree[*iter])
m_stack.push(*iter);
}
}
cout if (ver_count 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 else
cout cin.get();
return 0;
}
通过上述文章讲述的看图判断是不是有向无环图内容,想必朋友们都大致了解一二了吧!想要获取更多精彩的技术问题,来关注爱站技术频道网站即可。
上一篇:在C#中二分法求多项式的间值介绍
下一篇:C语言之纯虚函数与抽象类介绍