无向图上顶点和边的变化

我使用visual studio c,提升 .

可以说我有无向图 . 每隔t秒,我需要检查它是否发生了变化(顶点\边缘被移除\添加) .

时间复杂性非常重要 .

这是构建图形的示例:

typedef adjacency_matrix<undirectedS> UGraph;
    UGraph G(9);
    add_edge(1, 2, G);
    add_edge(2, 5, G);
    add_edge(5, 1, G);
    add_edge(3, 6, G);
    add_edge(3, 4, G);
    add_edge(7, 8, G);

因为我使用 adjacency_matrixadd_edge()remove_edge()add_vertex()remove_vertex() 的时间复杂度为O(1) .

我想通过返回值使用 add_edge() 来检查该边是否已经存在:

retVal = add_edge(1, 2, G);
if(already exist)
 //do something
else
 //do something else

retVal = add_vertex(1,G);
if(already exist)
 //do something
else
 //do something else

但是根据我的理解,如果我将边缘添加到现有边缘(在无向图中),它将并行添加到现有边缘 .

那么,有没有一种方法(我的方式或其他方式),检查两个无向图之间的变化(顶点和边缘)?

谢谢 .

回答(1)

2 years ago

在做了一些阅读之后,这就是我发现的:

检查边缘是否存在 -

graph_traits<UGraph>::edge_descriptor e;   //UGraph is the undirected graph
bool found = false;

boost::tie(e, found) = edge(1, 2, G); //found = true
boost::tie(e, found) = edge(1, 3, G); //found = false
boost::tie(e, found) = edge(2, 1, G); //found = true

另一种方法:

found = edge(1, 2, G).second; //found = true
found = edge(1, 3, G).second; //found = false

检查顶点是否存在 -

我没有找到任何内置函数,但可以在 adjacency_matrix 找到特定的顶点