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).

But here in this article, it’s all about looking into non-linear data structures: graphs

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

Visualizing DFS traversal

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 v
if w is unvisited
{
dfs(w);
add edge vw to tree T
}
}

Here’s the Python implementation using recursion:

This was a basic overview of how DFS works. If you want to dive deeper, there is some great stuff available all over the internet and also on Medium.

Breadth first search (BFS) algorithm

It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array. For simplicity, it is assumed that all vertices are reachable from the starting vertex.

What we do in a BFS is a simple step-by-step process:

  1. Start from a vertex S. Let this vertex be at what is called…. “Level 0”.
  2. Find all the other vertices that are immediately accessible from this starting vertex S, that is they are only a single edge away (the adjacent vertices).
  3. Mark these adjacent vertices to be at “Level 1”.
  4. You might be coming back to the same vertex due to a loop or a ring in the graph. If this happens, your BFS will take time. So, you will go only to those vertices who do not have their “Level” set to some value.
  5. Mark which is the parent vertex of the current vertex you’re at, i.e., the vertex from which you accessed the current vertex. Do this for all the vertices at Level 1.
  6. Now, find all those vertices that are a single edge away from all the vertices which are at “Level 1”. These new set of vertices will be at “Level 2”.
  7. Repeat this process until you run out of graph.

See this — https://www.programiz.com/dsa/graph-bfs

Python Implementation Using Queue

read original article here