欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

判斷給定的圖是不是有向無環(huán)圖實(shí)例代碼

 更新時(shí)間:2013年05月14日 14:43:18   作者:  
判斷給定的圖是不是是有向無環(huán)圖,方法是應(yīng)用拓?fù)渑判颍a如下

復(fù)制代碼 代碼如下:

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

相關(guān)文章

  • C++STL之vector模板類詳解

    C++STL之vector模板類詳解

    這篇文章主要為大家詳細(xì)介紹了C++vector模板類,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-03-03
  • C/C++?Qt?Tree與Tab組件實(shí)現(xiàn)分頁菜單功能

    C/C++?Qt?Tree與Tab組件實(shí)現(xiàn)分頁菜單功能

    這篇文章主要介紹了C/C++?Qt?Tree與Tab組件實(shí)現(xiàn)分頁菜單功能,實(shí)現(xiàn)一個(gè)類似于樹形菜單欄的功能,當(dāng)用戶點(diǎn)擊菜單欄中的選項(xiàng)時(shí)則會(huì)跳轉(zhuǎn)到不同的頁面上,本文簡單給大家分享實(shí)現(xiàn)代碼,感興趣的朋友跟隨小編一起看看吧
    2021-11-11
  • 深入淺出理解C語言指針的綜合應(yīng)用

    深入淺出理解C語言指針的綜合應(yīng)用

    指針是指向另一個(gè)變量的變量。意思是一個(gè)指針保存的是另一個(gè)變量的內(nèi)存地址。換句話說,指針保存的并不是普通意義上的數(shù)值,而是另一個(gè)變量的地址值。一個(gè)指針保存了另一個(gè)變量的地址值,就說這個(gè)指針“指向”了那個(gè)變量
    2022-02-02
  • C語言詳細(xì)實(shí)現(xiàn)猜拳游戲流程

    C語言詳細(xì)實(shí)現(xiàn)猜拳游戲流程

    在學(xué)習(xí)了循環(huán)、分支、和函數(shù)之后,可以寫一些簡單的小游戲來給自己的編程之路增添一份樂趣。不僅提升了編碼能力,還可以邊學(xué)邊玩,簡直妙哉妙哉
    2022-05-05
  • C/C++ 雙鏈表之逆序的實(shí)例詳解

    C/C++ 雙鏈表之逆序的實(shí)例詳解

    這篇文章主要介紹了C/C++ 雙鏈表之逆序的實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下
    2017-07-07
  • OpenCV計(jì)算圖像的水平和垂直積分投影

    OpenCV計(jì)算圖像的水平和垂直積分投影

    這篇文章主要為大家詳細(xì)介紹了OpenCV計(jì)算圖像的水平和垂直積分投影,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-12-12
  • C++17 使用 std::string_view避免字符串拷貝優(yōu)化程序性能

    C++17 使用 std::string_view避免字符串拷貝優(yōu)化程序性能

    這篇文章主要介紹了C++17 使用 std::string_view避免字符串拷貝優(yōu)化程序性能,幫助大家提高程序運(yùn)行速度,感興趣的朋友可以了解下
    2020-10-10
  • 關(guān)于移位操作的一點(diǎn)重要說明

    關(guān)于移位操作的一點(diǎn)重要說明

    下面小編就為大家?guī)硪黄P(guān)于移位操作的一點(diǎn)重要說明。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2016-12-12
  • 淺析C++中類模板的用法

    淺析C++中類模板的用法

    C++類模板是一種用于創(chuàng)建通用類的工具,它允許我們定義一個(gè)通用類,支持多種類型。本文就來簡單講講它的具體使用吧,感興趣的可以了解一下
    2023-04-04
  • C/C++中多重繼承詳解及其作用介紹

    C/C++中多重繼承詳解及其作用介紹

    這篇文章主要介紹了C/C++中多重繼承詳解及其作用介紹,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-09-09

最新評論