Graphs in computer science and its traversal algorithms

• For example, one common data structure is the list or array, which is an ordered sequence of values. Here’s a list of numbers: 0, 1, 1, 2, 3, 5, 8, 13. The concept of the list isn’t particular to one language, and it’s also used outside of programming in everyday life — wish lists, shopping lists, and so on.

Algorithms are recipes for getting things done. They are not the same as data structures. Algorithms are usually “better” if they work faster or more efficiently (using less time, memory, or both).

Diving into graphs

A graph is a system in which there are potentially multiple ways to get from an arbitrary point, A, to another arbitrary point, B.

A graph is normally defined as a pair of sets (V,E). V is a set of arbitrary objects called vertices or nodes, and E is a set of pairs of vertices, which we call edges or (more rarely) arcs. In an undirected graph, the edges are unordered pairs, or just sets of two vertices. I usually write u v instead of {u,v} to denote the undirected edge between u and v.

In a directed graph, the edges are ordered pairs of vertices. I will use u → vinstead of (u,v) to denote the directed edge from u to v and vice versa for all edges in this article.

Graphs can also be undirected or directed, cyclic or acyclic (mostly directed), or weighted.

Traversing a graph

To visit each node or vertex which is a connected component, tree-based algorithms are used. You can do this easily by iterating through all the vertices of the graph, performing the algorithm on each vertex that is still unvisited when examined.

Two algorithms are generally used for the traversal of a graph: Depth first search (DFS) and Breadth first search (BFS).

Depth first search (DFS) algorithm

Depth-first Search (DFS) is an algorithm for searching a graph or tree data structure. The algorithm starts at the root (top) node of a tree and goes as far as it can down a given branch (path), and then backtracks until it finds an unexplored path, and then explores it. The algorithm does this until the entire graph has been explored.

Many problems in computer science can be thought of in terms of graphs. For example, analyzing networks, mapping routes, scheduling, and finding spanning trees are graph problems. To analyze these problems, graph search algorithms like depth-first search are useful. –Source

The simplest pseudo-code would be:

Depth-first search is a common way that many people naturally use when solving problems like mazes.

First, we select a path in the maze (for the sake of this example, let’s choose a path according to some rule we lay out ahead of time) and we follow it until we hit a dead end or reach the end of the maze. If a given path doesn’t work, we backtrack and take an alternative path from a past junction, and try that path.

To turn this into a graph traversal algorithm, we basically replace “child” with “neighbor”. But to prevent infinite loops, we only want to visit each vertex once. Just like in BFS, we can use marks to keep track of the vertices that have already been visited, so we don’t visit them again. Also, just like in BFS, we can use this search to build a spanning tree with certain useful properties.

`dfs(vertex v){visit(v);for each neighbor w of vif w is unvisited{dfs(w);add edge vw to tree T}}`

Here’s the Python implementation using recursion: