DFS after remove some edge

Question

I have a graph with one source vertex and a list of the edges, where in each iteration one edge from the list is going to be removed from the graph.

For each vertex i have to print the number of iterations after it lost its connection to the source vertex- there will be no path between the vertex and the source.

My idea is to run DFS algorithm from the source vertex in each iteration and increment the value of the vertexes, which have the connection with the source vertex- there is a path between the vertex and the source vertex.

I'm sure there is a better idea than run the dfs algorithm from the source vertex in each iteration. But I don't know how to resolve the problem in better, faster way.

Answer 1

Since you have the whole edge list in advance, you can process it backwards, connecting the graph instead of disconnecting it.

In pseudo-code:

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);
    }
}

This algorithm achieves linear time, since each vertex is only involved in a single BFS or DFS, before it gets connected to the source.