删除一些边缘后的 DFS

Question

我有一个图，其中有一个源顶点和一个边列表，在每次迭代中，列表中的一条边将从图中删除。

对于每个顶点，我必须在它失去与源顶点的连接后打印迭代次数 - 顶点和源之间将没有路径。

我的想法是运行DFS算法每次迭代都从源顶点开始递增顶点的值，这些顶点与源顶点有联系——顶点和源之间有一条路径顶点.

我确信有比运行每次迭代中从源顶点的 dfs 算法更好的主意。但我不知道如何更好、更快地解决问题。

Answer 1

它有助于倒转时间，因此我们正在考虑一条一条地添加边缘并确定何时实现与源的连接。在每一步之后执行遍历的想法是一个很好的想法。要使总成本降低到线性，您需要进行以下优化和摊销分析。优化是将访问的顶点集合从一个遍历保存到另一个遍历，并将该集合视为一个"supervertex"，在遍历时删除集合内的边。每次遍历的成本与因此删除的边数成正比，因此摊销线性运行时间。

Answer 2

因为你事先有了整个边列表，你可以反向处理它，连接图而不是断开它。

在伪代码中：

GIVEN:
edges = list of edges
outputMap = new empty map from vertex to iteration number
S = source vertex

//first remove all the edges in the list
for (int i=0;i<edges.size();i++) {
   removeEdge(edges[i]);
}

//find vertices that are never disconnected
//use DFS or BFS
foreach vertex reachable from S
{
   outputMap[vertex] = -1;
}

//walk through the edges backward, reconnecting
//the graph
for (int i=edges.size()-1; i>=0; i--)
{
    Vertex v1 = edges[i].v1;
    Vertex v2 = edges[i].v2;
    Vertex newlyConnected = null;

    //this is for an undirected graph
    //for a directed graph, you only test one way
    //is a new vertex being connected to the source?
    if (outputMap.containsKey(v1) && !outputMap.containsKey(v2))
        newlyConnected = v2;
    else if (outputMap.containsKey(v2) && !outputMap.containsKey(v1))
        newlyConnected = v1;

    if (newlyConnected != null)
    {
        //BFS or DFS again
        foreach vertex reachable from newlyConnected
        {
            //It's easy to calculate the desired remove iteration number
            //from our add iteration number
            outputMap[vertex] = edges.size()-i;
        }
    }
    addEdge(v1,v2);
}

//generate output
foreach entry in outputMap
{
    if (entry.value >=0)
    {
       print("vertex "+entry.key+" disconnects in iteration "+entry.value);
    }
}

该算法实现了线性时间，因为每个顶点在连接到源之前仅涉及单个 BFS 或 DFS。

删除一些边缘后的 DFS

DFS after remove some edge

algorithm

graph-theory

depth-first-search

vertex

edge-list