Member 13277493 Ответов: 1

Итерация списка смежности


может ли кто-нибудь объяснить мне, как 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

большое вам спасибо, я их починю. И еще один вопрос: они представляют собой столько же связанных списков, сколько и вершин, я прав? Для каждой вершины существует связанный список, созданный ее смежными вершинами.

1 Ответов

Рейтинг:
4

KarstenK

Да, ибо для каждой вершины создается запись в созданном списке, но у вас список есть какой-то маленький, используя указатель int, но используя приведение для вставки записи.

Важный совет: используйте для члена класса V длинное и лучшее имя, например "индекс" или вершина, чтобы отделить его от входных переменных. Vars обычно находятся в нижнем регистре.

Код становится понятнее и интереснее читать:

Graph::Graph(int v)
{
    this->vertex = v;
    adjList = new std::list<int>[v];
}


nv3

Я не думаю, что "вершина" - это хорошее название для V, поскольку оно относится к максимальному числу вершин, поддерживаемых этим объектом. "maxVertices", вероятно, даст лучшее представление.

Но это не единственная плохая практика в Кодексе. "adjList" должен быть "adjLists", поскольку это набор списков. И я бы действительно рекомендовал использовать массив вместо списка в этом контексте.

KarstenK

конечно самое подходящее имя должно быть выбрано ;-)