# Graph Traversal Properties

# More Tricks with DFS and BFS

Hello, and welcome to competitive programming. Today we’ll cover a few more things you can do using BFS and DFS that will turn out to be helpful.

## Objectives

You will see algorithms that will help you check if a graph is bipartite, find cut edges and cut points, find cycles, and find strongly connected components.

## Bipartite Checking

A graph is bipartite if it has two subgraphs such that every single edge connects a node from one subgraph to the other. Another way to say this is to say that the graph is 2-colorable; every vertex has neighbors of the opposite color, and no two neighbors share the same color.

Once you have the code for a traversal, it’s easy to modify it to check for bipartiteness. Use two colors, 0 and 1, and start the root with color 1. Then, for each node, set the neighbors to the opposite color. If a neighbor already has a color set, it should be the opposite of the current node, or else you have a non-bipartite graph.

Here’s an example. Let’s start with node A and color it.

(next)

We then check all it’s neighbors and color them the opposite color.

(next)

This colors d,f, and g. Suppose we are using BFS here, so let’s take our next node as f. From f, we check it’s children and color b.

(next)

Next we visit d, which colors c, and so forth.

If there were an edge between g and f, you can see that the algorithm would detect that the graph is not bipartite.

## Checking for Cycles

So far we have had two states in our graphs: visited and unvisited. We can add a third state, explored, to indicate that we have seen the node, but have not yet returned back from visiting its children.

When you see a node for the first time, you change its state from unvisted to explored. Next you check the neighbors. If the neighbor is unvisited, it means the current node is the parent. If the neighbor is already visited, then you have either a forward edge or a cross edge. If the neighbor is marked explored, the edge goes backwards and it means you have a cycle.

Once you are done with all the neighbors, you set the current node state to visited.

This relies on recursion, so you will need to use DFS for this.

## Finding Cut Nodes and Edges

Consider this graph.

I have annotated each of the nodes with two numbers. The superscript number is
called the dfs number; it tells you the order in which the DFS algorithm visited
the node. The subscript number is called `dfs_low`

, it contains the lowest dfs
number reachable during the DFS itself.

When we enter a node for the first time, we set `dfs_num`

to be the next number
up, and `dfs_low`

to be the same. As we traverse, we may end up updating the
entry for `dfs_low`

.

In this graph, we start with A, then B, then C. From C we will eventually take
the edge back to A, and so A, B, and C will have `dfs_low`

of 0.

When we go to D, we would set both `dfs_num`

and `dfs_low`

to 3. As we continue
traversing, we take the edge from e to d, and that sets `def_low`

of those three
nodes to 3.

You may want to pause this for a bit to be sure you see where all these numbers came from, and then resume when you are ready.

There are three things you can do with this.

The first is that you can see what nodes belong to a cycle. They will all have the
same `dfs_low`

number. Here, `a`

, `b`

, and `c`

belong to a cycle, as well as `d`

,
`e`

, and `f`

.

The second is that you can identify cut nodes, also known as articulation nodes. An articulation node is one where, if you delete it, then the graph becomes disconnected.

There are two such nodes here; c and d.

Here’s how you can tell by looking at `dfs_num`

and `dfs_low`

: if you have a vertex `u`

and a neighbor `v`

, and `dfs_low`

of `v`

is greater than or equal to `dfs_num`

of `u`

, then
`u`

is an articulation node. So, for instance, the `dfs_low`

of `d`

is 3, which is
greater than the `dfs_num`

of `c`

. This means the only way to reach `d`

is through `c`

,
If there were another path to `d`

, then `d`

’s `dfs_low`

would be smaller.

Similarly, the `dfs_low`

of `e`

and `f`

are 3, which is equal to the `dfs_num`

of `d`

,
so `d`

is an articulation point.

The third thing you can do is identify cut edges. It is similar, but the equation
is now a strict inequality: if `dfs_low[v]`

is strictly greater than `dfs_num[u]`

then the edge `u-v`

is a bridge. There is only one instance of that in this graph,
the edge `c-d`

.

## Strongly connected components.

Finally, if the graph is directed, we can use the same technique to determine strongly
connected components. When `dfs_low`

is equal to `dfs_num`

for a node, then that node
is the root of a strongly connected component. All the other members of that component
will share the same `dfs_low`

.

Well, that’s a lot for one video. My advice is to make up a graph or two where
you know what the properties are, and then try these algorithms on them by hand.
The code for this is fairly simple, once you have a working DFS; you just update the
`dfs_num`

and `dfs_low`

arrays as you go.+