否则计算连接组件的数量O(| V | | E |),并检查| V | - | E | =连接组件的数量 - 1 .
备注:拥有多个连接组件是算法的反例 .
0
"Increment i everytime we decide not to visit a vertex because
it has already been visited."
我不清楚你在这里要做什么 .
而不是这个,怎么样:
执行DFS并计算后边缘数 .
A back edge is an edge that is from a node to itself (selfloop) or one of its
ancestor in the tree produced by DFS.
如果后边缘的数量== 1,那么其他的不是独轮车 .
To count number of back edges, follow this algorithm.
To detect a back edge, we can keep track of vertices currently in recursion stack of
function for DFS traversal. If we reach a vertex that is already in the recursion stack,
then there is a cycle in the tree. The edge that connects current vertex to the
vertex in the recursion stack is back edge
2 回答
您的图表是否由单个连接组件组成?
在这种情况下,只需计算顶点和边并检查| V | - | E | = 0
否则计算连接组件的数量O(| V | | E |),并检查| V | - | E | =连接组件的数量 - 1 .
备注:拥有多个连接组件是算法的反例 .
我不清楚你在这里要做什么 .
而不是这个,怎么样:
执行DFS并计算后边缘数 .
如果后边缘的数量== 1,那么其他的不是独轮车 .