我有一个包含一个源顶点和一个边列表的图,其中在每次迭代中,列表中的一条边将从图中删除。
对于每个顶点,我必须打印它失去与源顶点的连接后的迭代次数 - 顶点和源之间将没有路径。
我的想法是在每次迭代中从源顶点运行DFS算法,并增加与源顶点有连接的顶点的值 - 顶点和源顶点之间有一条路径。
我确信有一个比在每次迭代中从源顶点运行 dfs 算法更好的想法。但我不知道如何更好更快地解决问题。
最佳答案
由于您预先拥有整个边列表,因此您可以向后处理它,连接图而不是断开连接。
在伪代码中:
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。
关于algorithm - 删除一些边后的DFS,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33584614/