Graph Traversal¶
We will cover two fundamental graph algorithms. depthfirst search & breadthfirst search.
BFS vs DFS
Both algorithms are given starting node in the graph and they visit all nodes that can be reached from the starting node. The difference in algorithms is the order in which they visit the nodes.
Depthfirst search($\text{DFS}$)¶
Depthfirst search always follows a single path in the graph as long as it find new nodes. After this, it returns to previous nodes and begin to explore other parts of the graph.
The algorithm keeps track of visited nodes, so that it processes each node only once
Implementation¶
Using adjacency lists in an array
maintain an array visited[N]
1 2 3 4 5 6 7 8 9 10 11 

Breadthfirst search($\text{BFS}$)¶
Breadthfirst search visits the nodes in increasing order of their distance from the starting node.
Thus, we can calculate the distance from the starting node to all other nodes using $BFS$.
Implementation¶
Typical implementation is based on a queue that contains nodes.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 

Applications¶
You can use any of both to check properties of graph
but in practice, depthfirst search is a better choice, because of ease of implementation
1. Connectivity check¶
A graph is connected if there is a path between any two nodes of the graph
Implementation¶
 Connected Graph: If a search did not visit all the nodes, we can conclude that the graph is not connected
 Find all components of Graph: iterating through the nodes and always starting a new depthfirst search if the current node does not belong to any component yet
2. Finding cycles¶
Implementation¶

Way1: A graph contains a cycle if during a graph traversal, we find a node whose neighbor (other than the previous node in the current path) has already been visited

Way2(math): if a component contains c nodes and no cycle, it must contain exactly c1 edges. if there are c or more edges, the component surely contains a cycle
3. Bipartiteness check¶
A graph is bipartite if its nodes can be colored using two colors so that there are no adjacent nodes with the same color
Implementation¶
The idea is to color the starting node blue, all its neighbors red, all their neighbors blue, and so on. If at some point of the search we notice that two adjacent nodes have the same color, this means that the graph is not bipartite. Otherwise, the graph is bipartite.
Why it works?
This algorithm always works, because when there are only two colors available, the color of the starting node in a component determines the colors of all other nodes in the component
NPhard
Note that in the general case, it is difficult to find out if the nodes in a graph can be colored using $k$ colors so that no adjacent nodes have the same color. Even when $k=3$, no efficient algorithm is known but the problem is NPhard