Graphs traversals. BFS and DFS, Topological Sort, and new graph phenomena.

Yusif Ibrahimov

9 min readOct 15, 2020

Outline:

Some New Terminologies
Euler, Hamiltonian, and Bipartite graphs
Breadth-First Search
Depth-First Search

Some New Terminologies

The null Graph does not contain any edge. There is no connection between the vertices.

2.The possible smallest graph is the trivial graph which contains only one vertex.

3.If you have access from one node to all nodes, it is a connected graph.

4.A graph in which there does not exist any path between at least one pair of vertices is called a disconnected graph.

4.If all nodes of the graph have the same degree, we can call it a regular graph. If all of them have the k degrees- it is called the “k-regular graph“.

5.Complete Graph-There should be a connection between all nodes. This means that the number of edges is maximum.

6.If the degrees of all the nodes are equal to the 2, then it is a cycle graph.

Euler, Hamiltonian, and Bipartite graphs

1.A Eulerian Path visits every edge exactly once.

The necessary conditions are:

Firstly, all the vertices with degree >0 should be in the same component (connected).
Secondly, only two edges must have an odd degree and all the remaining edges should have even degrees.

A Eulerian circuit is a Eulerian path in the graph that starts and ends at the same vertex. The necessary conditions are:

Firstly, all the vertices with degree >0 should be in the same component (connected).
Secondly, all edges must have an even degree.

The eulerian graph is a graph that has a Eulerian circuit

2. Hamiltonian path (or traceable path) is a path in a graph that visits each vertex exactly once

A Hamiltonian cycle is a Hamiltonian path that is a cycle

A Hamiltonian graph is a graph that has a Hamiltonian circuit

3. A bipartite graph is a graph where-

Vertices can be divided into two sets X and Y.
The vertices of set X only join with the vertices of set Y.
None of the vertices belonging to the same set join each other.

Breadth-First Search — BFS traversal

Traversing the graph means that visiting all vertices of the graph without repetition!. BFS Traversing visiting all the nodes level by level. We know that tree is an acyclic graph, therefore, let’s start from the BFS traversing of a tree.

Suppose we have the following binary tree

We want to apply for the BFS traversing. As we said before, the BFS traversing technique helps us to visit all the nodes but level by level. In this case, if we start from the node A, this is level 0 Then go to level 1 -> then it will be B and C, then forward to the level 2-> D E F G, level 3 -> H, I, L, M, N, O. This is simply what is a BFS like in the following image

Conclusion: The BFS traversing result: A B C D E F G H I L M N O ( look at the numbers just above each node)

But what about the Graph? How to apply the same logic to a graph?. In the graph, BFS also does the same job, again level by level. Look at the following graph.

If we apply the same logic to this graph, we should get A (level0) -> B C (level 1) -> D E (level 2) -> F (level 3), the answer is A, B, C, D, E, F. Look the following image

The numbers above the nodes are demonstrating the visiting (printing ) order of the nodes. Answer: A B C D E F (true)

BFS Algorithm. How to achieve the BFS traversing?

Step1: Choose the starting point, and append it to the queue ( FIFO logic), and mark it as visited.

As you see, it is visited and we marked it as red, also we append it to the Queue. For the next case ( and all cases after that), we check if the queue exists( is there an element), we see yes. Then, Deque it( pop the first one) and add to the list of the visit. And look for the unvisited adjacents, add them to the queue and continue.

In this case, If we dequeue our Queue, we will get A. print A. The adjacents (unvisited) of the A are B and C. Then we must add them to the Queue.

As you see, we dequeued the A and chose its all adjacent nodes, and added them to the queue.

In the next step again we check the existence of the queue and deque the Queue. We get a B. print B. And mark it as visited (red). Choose all the adjacents(unvisited) of B and add them to the queue(of course if not visited).

As you can see from the image, we marked B as visited (red) and D as its adjacent(blue). We added D to the queue and removed the B (dequeued).

In the next step, Again check the existence of the queue, and deque it. We must get C now, print C, and mark it as the visited. Choose all the adjacents (unvisited) of the C ( only D) and add them to the queue(if not visited)

We marked C visited, and removed from the queue(deque), then the adjacent of C (D) added to the queue.

For the next step, check the existence of the queue and deque it. We get D. print(D) (unvisited), and mark it as visited, and choose its adjacents (unvisited) ( F) and add to the queue.

We removed D (dequeued), added to the line of the visited and F added to the queue.

Again we must check the existence of the queue (yes) the deque. We got E. print E,(unvisited), mark it as visited, and choose its adjacent (F) and add it to the queue.

Check the existence of the queue(yes) and deque it. We got F, print F, make it visited, and choose its adjacents. But F does not have unvisited adjacent. so we just continue.

Now, we see that there is not an element in our queue ( it does not exist), so we stop here. The result is: A B C D E F

Python implementation:

Depth-First Search — DFS traversal

Depth First Search (DFS) algorithm traverses a graph in a depth ward motion. At this time, we visit the nodes ‘deeply’ not level by level. Here is an example of the DFS traversing.

This was the application of the DFS to tree, the detailed diagram for the DFS could be the following:

Look to the numbers, and the path for DFS will be A B D E F G C H I J M N L.

Well, but how to apply the DFS to the graph, not just the tree. The same thing, we will go on deeply not level by level. Let’s look at the graph that we used for BFS.

Now, if we apply the DFS we will obtain:

Now we see that the path is A B D F G C (or A C E F D B does not matter). If it was BFD it would be A B C D E F.

DFS Algorithm. How to achieve the DFS traversing?

Step1: Choose the starting point and push it to Stack( LIFO logic and you will feel why).

Be sensitive to the positions of the stack that where we add and where we pop. This is the complete logic of LIFO.

Then if our stack exists, we pop it. We got A. print it Makes it visited. Take all the adjacents(B, C) unvisited adjacents to the stack and visited list.

Be careful, we can remove the last added element of the stack, if the image is confusing for you to remember that, A removed before the adding of the B and C. At that moment, A was the last element of the queue, that’s why we removed (pop) it.

Now again, check the existence of the stack. Pop it. and we get C. print it. At that time we get C (the last one is C). Make it visited and choose all the unvisited adjacents(E) and push them to the stack.

Now again, check the existence of the stack. Pop it. we got E. print E. At that time we get E(the last one is E). Make it visited and choose all the unvisited adjacents(F) and push them to the stack.

Now again, check the existence of the stack. Pop it. We got F. print it At that time we get F(the last one is F). Make it visited and choose all the unvisited adjacents(D) and push them to the stack.

Now again, check the existence of the stack. Pop it We got D. print it. At that time we get D(the last one is D). Make it visited and choose all the unvisited adjacents(B) and push them to the stack.

Now again, check the existence of the stack. Pop it. We got B. print it. At that time we get B(the last one is B). Make it visited and choose all the unvisited adjacents(None) continue…

Be careful, our stack is not empty yet, we have still B. take this B, it is already visited, no need to make it visited, and there’s not the unvisited adjacent.