邻接列表迭代 [英] Adjacency list iteration

问题描述

有人可以向我解释int v如何用作列表的索引，它只是列表指定索引中的值，那么为什么我们检查如果color [v] == GREY

  #include   <   iostream  >  
   #include   <  列表 >  
  
 枚举颜色{WHITE，GRAY，BLACK}; 
 
  class 图
 {
  int  V; 
 std :: list< int> * adjList; 
  bool  DFSUtil（ int  v， int  color []）; 
 
  public ：
图表（ 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））
 {
 返回  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 ; 
} 
} 
} 
 
 返回  false < /跨度>; 
} 
 
  int  main（）
 {
  //  创建上图中给出的图表 
图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<<  图表包含周期; 
  else  
 std :: cout<<  图表不包含循环; 
 
  return   0 ; 
} 

我的尝试：



我试图通过调试来理解它

解决方案

是的，因为每个顶点都会在创建的列表中获得一个条目，但是你列出了一些通过使用int指针，但使用强制转换插入一个条目。



重要提示：用于类成员V一个长而好的名称，如index或者顶点从输入变量中分离出来。 Vars通常是小写的。



代码变得更清晰，更有趣：



< pre lang =c ++> Graph :: Graph（ int v）
{
this - > vertex = v;
adjList = new std :: list< int> [v];
}

can someone explain to me how int v is used as an index for the list, it's just a value in the specified index of the list, then why we check 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;
}

What I have tried:

I have tried to understand it with debugging

解决方案

Yes, for for every vertex gets an entry in the list created, but you list has some small by using an int pointer, but using a cast to insert an entry.

Important tip: use for the class member V a long and better name like "index" or vertex to seperate it clearer from input vars. Vars are normally in lower case.

The code gets clearer and more fun to read:

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

这篇关于邻接列表迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！