SHARE
TWEET

Untitled

a guest May 25th, 2019 105 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Поиск циклов обходом в глубину (dfs) через матрицу смежности в ориентированном графе
  2. /*p_AdjacencyMatrix - указатель на матрицу смежности
  3. countOfEdge - кол-во вершин, countOfCycles - кол-во циклов
  4. usedEdge[] - здесь храним цвета для вершин*/
  5.  
  6. void dfs(int vertice, int** p_AdjacencyMatrix, unsigned short& countOfEdge, int &countOfCycles)
  7. {
  8.     int i;
  9.     usedEdge[vertice] = 1; //Окрашиваем вершину в серый
  10.     for (i = 0; i < countOfEdge; i++) {
  11.         if (p_AdjacencyMatrix[vertice][i] && !usedEdge[i]) {
  12.             dfs(i, p_AdjacencyMatrix, countOfEdge, countOfCycles);
  13.         }
  14.         if (p_AdjacencyMatrix[vertice][i] && (usedEdge[i] == 1)) {
  15.             countOfCycles++;
  16.         }
  17.     }
  18.     usedEdge[vertice] = 2; //Окрашиваем в чёрный
  19. }
  20.  
  21.  
  22. ///
  23.  
  24. int countOfCycles = 0;
  25.                 for (int i = 0; i < countOfEdge; i++)
  26.                     if (!usedEdge[i]) dfs(i, p_AdjacencyMatrix, countOfEdge, countOfCycles);
  27.                 cout <<"\n\t"<< countOfCycles;
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top