Итерация списка смежности
может ли кто-нибудь объяснить мне, как int v используется в качестве индекса для списка, это просто значение в указанном индексе списка, тогда почему мы проверяем
if color[v]==GRAY
#include <iostream> #include <list> enum Color{WHITE, GRAY, BLACK}; class Graph { int V; std::list<int>*adjList; bool DFSUtil(int v, int color[]); public: Graph(int V); void addEdge(int v, int w); bool isCyclic(); }; Graph::Graph(int V) { this->V=V; adjList=new std::list<int>[V]; } void Graph::addEdge(int v, int w) { adjList[v].push_back(w); } bool Graph::DFSUtil(int u, int color[]) { color[u]=GRAY; std::list<int>::iterator it; for(it=adjList[u].begin(); it!=adjList[u].end(); it++) { int v=*it; if(color[v]==GRAY) { return true; } if(color[v]==WHITE && DFSUtil(v, color)) { return true; } } color[u]=BLACK; return false; } bool Graph::isCyclic() { int *color=new int[V]; for(int i=0; i<V; i++) { color[i]=WHITE; } for(int i=0; i<V; i++) { if(color[i]==WHITE) { if(DFSUtil(i, color)) { return true; } } } return false; } int main() { // Create a graph given in the above diagram Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); if (g.isCyclic()) std::cout << "Graph contains cycle"; else std::cout << "Graph doesn't contain cycle"; return 0; }
Что я уже пробовал:
Я пытался понять это с помощью отладки
nv3
Цвет массива-это массив с тем же количеством элементов, что и узлы графа. Представьте себе, что каждый узел имеет номер узла от 0 до V-1. Линия
int v=*it;
извлекает номер узла одного из списков смежности. Мы можем проверить цвет этого узла по цвету[v]. Думайте о цвете как о дополнительном свойстве каждого узла графа. Поскольку он используется только в isCyclic функции, он только выделяется там и хранится в виде параллельного массива.
Обратите внимание также на ошибки в этом коде: цвет никогда не освобождается! И списки смежности тоже!
Member 13277493
большое вам спасибо, я их починю. И еще один вопрос: они представляют собой столько же связанных списков, сколько и вершин, я прав? Для каждой вершины существует связанный список, созданный ее смежными вершинами.