Talk:Graphs-TADM2E

Users are not allowed to modify this page. why?

TADM2E 5.4

Go back to the edge_classification function given: There are 4 cases; TREE, BACK, CROSS, FORWARD

In BFS, TREE must be the first type you should expect, since, for any given node, when you reach its first layer of brethren, they constitute the first children of it.

BACK edges are impossible in undirected BFS since if there was actually a connection, it'd be discovered and processed before you went on with another node. This is true for every edge that a node is connected to. Therefore BACK edges are not present in undirected BFS.

FORWARD and CROSS edges are similar in definition, that is they are processed but their entry times are adverse. In undirected BFS, only one of them is possible, and that is the CROSS edge.

FORWARD edges are impossible since if there was a connection, it'd count as a TREE edge because it'd be the first time that the other node's met by your search. On the other hand, if the case of a strongly connected set of nodes, one BFS branch would discover the other first, so the second one would count that edge as a cross edge since its entry time would be always earlier.