3.2 Graph Connectivity and Graph Traversal

This section aims at answering the question of if there is a path from a node s to another node t, where s and t are node in a graph G=(V,E). The problem is called “determining s-t connectivity”. Although it can be pretty easy to answer this problem for small graphs, it become more painful for reasonably sized graph. That's why we need a more elegant and efficient way to solve the problem in case we have a fairly big graph. Breadth-First Search and Depth-First algorithms are the most efficient algorithms commonly used to solve this problem.