22.4.2.2. Classifying Non-Tree Edges

So, in any graph if we explore BFS, the edges that BFS actually uses will form a tree and this is called a BFS tree. Now, what happens about the remaining edges will these are called non tree edges, what you can check very easily is that any non tree edge will combine with the tree edges already there to form a cycle.

When we perform a Breadth First Search (BFS) on a graph, the edges we explore and use to connect vertices create what is called a BFS tree. This tree structure includes only those edges that were necessary to connect all nodes. Any edges that we did not explore are referred to as 'non-tree edges.' These non-tree edges are important because they can tell us something about the structure of the graph. Specifically, whenever we discover a non-tree edge during our search, it indicates that a cycle exists in the graph. A cycle means that we can loop back to a previous vertex without needing to explore additional edges.

Imagine you are navigating through a city using a map, where the streets represent edges and intersections represent vertices. The roads you take to reach your destination form a route, or 'tree.' If you encounter a street that leads back to an intersection you’ve already visited without needing to explore new streets, that street represents a non-tree edge, indicating you can circle back, akin to finding a cycle in the graph.

So, having a cycle is to equivalent to finding a non tree edge while doing BFS, what is a non tree edge is just an edge will we come to explore i comma j and find the j is already be mark visited.

When performing BFS, if we discover an edge that connects two vertices where one vertex has already been visited, we label this as a non-tree edge. This non-tree edge signifies that there is an alternate route back to a previously visited vertex, effectively creating a cycle. In simpler terms, finding this edge confirms that we can return to a node we have already seen, highlighting a loop in the graph's structure.

Think of a maze where every path you take branches off toward different rooms (vertices). If you find a door (an edge) that connects you back to a room you've already been to, that door represents a non-tree edge. This can lead you back into previously explored areas, revealing that the maze is not a simple path but instead has loops and circles, much like finding cycles in your graph.

So, let us do the same thing, but DFS and let us compute the pre and post numbers. So, we sorted DFS at vertex 1 and we mark it is counter as 0. So, we enter vertex 0, vertex 1 at step 0, so this is the pre number of vertex 0.

In a similar manner to BFS, we can also use Depth First Search (DFS) to identify non-tree edges. With DFS, we maintain a record of the 'pre' and 'post' numbers for each node. The 'pre' number indicates when we first visit a node, and the 'post' number indicates when we finish exploring that node. These numbers help us classify the edges into tree edges and non-tree edges. If we find edges that connect nodes with particular pre and post values, we can classify these edges as either forward, backward, or cross edges, which are essential for understanding cycles in directed graphs.

Imagine you're exploring a library. Each book represents a node. When you pull a book off the shelf to read it, you mark it as 'in progress' (pre-number). Once you finish reading, you mark it as 'completed' (post-number). If you find a book that refers back to one you’ve already read, that reference forms a cycle in your exploration, similar to how non-tree edges reveal cycles in DFS.

Now, it is easy to argue that a cross edge will only go from right to left. In other words, it only go from higher number to lower number, because if you wanted draw an edge like this for instance, then this would mean, but there was an edge from 2 to 4.

In directed graphs, edges are classified into three categories: tree edges, back edges, and cross edges. Tree edges are those that are part of the search tree. Back edges lead from a node to one of its ancestors in the DFS tree. Cross edges connect two vertices that are neither ancestors nor descendants. Understanding these classifications helps identify potential cycles in directed graphs, where only back edges can create cycles since they connect nodes in a manner that revisits ancestors.

Think of a directed tour in a city where one-way streets represent edges. If you can drive from one point to another (tree edge), drive back to an earlier point without retracing your steps (back edge), or find a new route that connects unrelated places without following the tour you’ve mapped out (cross edge), you’re navigating a network of directions much like analyzing a directed graph for edges.

--