Since every edge can be deleted once, the time complexity is O(V+E). If the graph contains cycle, this algorithm does not work.
June 22, 2007
Exercises 22.4-4
Disprove. Let G=(V,E), V={1,2,3,4}, E={<1,3>,<3,2>,<2,1>,<2,4>,<4,3>}. Start with 2 or 4 have different bad edges.
Exercises 22.4-3
Suppose that G has fewer than |V| edges, otherwise G must contain cycle. And we can use the DFS to check whether G has back edge or not. If there is no back edge, then G contains no cycle.
Exercises 22.4-2
Start with s, all the nodes which are adjacent to s have path 1. For a node v, if there more than one incoming edges, then the path from s to v is the summation of all incoming edges’ incident vertices’ paths. Finally, we can find the paths from s to t.
