看图判断是不是有向无环图

来源:爱站网时间:2022-03-16编辑:网友分享
我们可以来看看下面这张图片,判断下这幅图片是不是有向无环图,而它的代码是怎么实现的?接下来就让爱站技术频道小编来给大家讲解下,有需要的朋友可以自行参考。


#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   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   if (0 == indegree[v])
   m_stack.push(v);
 while (!m_stack.empty()) {
  v = m_stack.top();
  m_stack.pop();
  cout   ver_count++;
  for (list::iterator iter = adjacents[v].begin(); iter != adjacents[v].end(); iter++) {
   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语言之纯虚函数与抽象类介绍

相关阅读

热门软件源码

最新软件源码下载