Python中的List是C中数组的一个很好的替代品，list甚至比数组更好地存储数据。考虑使用list而不是set，因为我已经看到在python中使用list是多么的通用，因为list是可变的，并且为了让代码不断添加图中的访问元素，我想使用list是一个不错的选择。快乐的编码！

你不能总是在两者之间做出选择。
如果node是一个范围很小的无符号整数，那么将其用作列表索引将是更好的选择：在这种情况下，您不需要hashmap的逻辑（set的底层技术），因为不需要冲突管理：该索引唯一地标识列表中的条目。一旦分配了列表（即O（𝑛）），获取和设置的相关操作都是O（1）。
如果node不符合这个条件，并且node不能被Map到这样一个小的无符号整数（injective mapping的运行时间为O（1）），那么列表的选择就逐渐消失了。node不能再用作索引。当然，您仍然可以将node（作为值）* 追加到动态列表中，但这样in操作的复杂度就会降低到O（𝑛）。这不是你想要的
在这种情况下，使用set是正确的选择。例如，如果您使用OOP方法，则node将是某个Node类的示例，具有其键、标签和邻居的属性。除非有办法将这些node对象Map到小的无符号整数，否则它们不能用作列表索引，而set将是一个逻辑选择。
关于集合上运算的复杂性：在实际情况中，你可以假设获取和设置的摊销时间复杂度为O（1）。冲突会使复杂性降低到O（𝑛）are rare的情况。

抛出大O值很有趣，也很容易。但是在某些时候，有必要坐下来编写一些代码，这样您就可以对实际的实现进行时序测试。

代码，用于比较使用向量和集合跟踪访问过的顶点的C++实现。

#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include "cRunWatch.h"

const int vertex_count =  1000000;
const int visited_count =  100000;

std::vector<bool> vVisited( vertex_count,false);
std::set<int> setVisited;

int randomVertex()
{
     raven::set::cRunWatch aWatcher("randomVertex");
    return rand()%(vertex_count-1);
}

int useVector()
{
    raven::set::cRunWatch aWatcher("useVector");

    // Visit some vertices;
    for( int k = 0; k < visited_count; k ++ )
    {
        vVisited[ randomVertex() ] = true;
    }

    // check if some vertices have been visited
    int total_visits_found = 0;
    for( int k = 0; k < visited_count; k ++ )
        if( vVisited[randomVertex()] )
            total_visits_found++;

    return total_visits_found;
}

int useSet()
{
    raven::set::cRunWatch aWatcher("useSet");

    // Visit some vertices;
    for( int k = 0; k < visited_count; k ++ )
    {
        setVisited.insert( randomVertex() );
    }

    // check if some vertices have been visited
    int total_visits_found = 0;
    for( int k = 0; k < visited_count; k ++ )
         if( setVisited.count(randomVertex() ) )
            total_visits_found++;

    return total_visits_found;
}
main()
{
    raven::set::cRunWatch::Start();

     /* initialize random seed: */
  srand (time(NULL));

    useVector();
    useSet();

    raven::set::cRunWatch::Report();

    return 0;
}

字符串

结果：

raven::set::cRunWatch code timing profile
Calls           Mean (secs)     Total           Scope
       1        0.154407        0.154407        useSet
       1        0.0599845       0.0599845       useVector
  400000        3.1321e-08      0.0125284       randomVertex

型
注：在使用不同随机种子的多次运行中，这些结果一致

结论：

向量实作比使用集合快约三倍。