search

emory-courses / dsa-java

Data Structures and Algorithms in Java
https://emory.gitbook.io/dsa-java/
42 stars 55 forks source link

[QZ9] Can an augmenting path contain cycle? #222

Closed bianshuyang closed 2 years ago

bianshuyang commented 2 years ago

I get these as augmenting path, are all of them valid? Or I should not include cycles? [5 <- 3 : 2.000000, 3 <- 1 : 3.000000, 1 <- 0 : 4.000000] [5 <- 3 : 2.000000, 3 <- 2 : 2.000000, 2 <- 0 : 2.000000] [5 <- 3 : 2.000000, 3 <- 2 : 2.000000, 2 <- 3 : 1.000000, 3 <- 1 : 3.000000, 1 <- 0 : 4.000000] [5 <- 4 : 4.000000, 4 <- 2 : 3.000000, 2 <- 0 : 2.000000] [5 <- 4 : 4.000000, 4 <- 2 : 3.000000, 2 <- 3 : 1.000000, 3 <- 1 : 3.000000, 1 <- 0 : 4.000000]

Graph is: int s = 0, t = 5; Graph graph = new Graph(6); graph.setDirectedEdge(s, 1, 4); graph.setDirectedEdge(s, 2, 2); graph.setDirectedEdge(1, 3, 3); graph.setDirectedEdge(2, 3, 2); graph.setDirectedEdge(2, 4, 3); graph.setDirectedEdge(3, 2, 1); graph.setDirectedEdge(3, t, 2); graph.setDirectedEdge(4, t, 4);

bianshuyang commented 2 years ago

Using containCycle algorithm ,2->3 & then 3->2 is not considered as a cycle.