A graph is simply a set of points together with a set of lines connecting various points. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another. According to wikipedia: In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. Graph algorithms solve problems related to graph theory.

I implemented BFS,DFS, minimum spanning tree, Dijkstra’s and Floyd’s algorithms.

Breadth-First Search(BFS).

BFS begins at the root node and explores all the neighbouring nodes. Then for each of those nearest nodes, it explores their unexplored neighbour nodes, and so on, until it finds the goal.

The following figure illustrates the order in which the nodes are expanded.

The code of this program is available at: https://bitbucket.org/vidyakv/graph-algorithms-in-c/changeset/d00d940c1a8d#chg-bfs2.c

Depth-First Search(DFS)

Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.

The following figure illustrates the order in which the nodes are expanded.

The code of this program is available at: https://bitbucket.org/vidyakv/graph-algorithms-in-c/changeset/d00d940c1a8d#chg-dfs_path.c

Minimum Spanning Tree

A spanning tree of an undirected graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees. A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree.

The following figure illustrates the minimum spanning tree of a planar graph. Each edge is labeled with its weight, which here is roughly proportional to its length.

The code of this program is available at: https://bitbucket.org/vidyakv/graph-algorithms-in-c/changeset/d00d940c1a8d#chg-min_span_tree.c

Dijkstra’s algorithm

It is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms. For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined.

The code of this program is available at: https://bitbucket.org/vidyakv/graph-algorithms-in-c/changeset/d00d940c1a8d#chg-dijkstra.c

Floyd-Warshall algorithm

It is a graph analysis algorithm for finding shortest paths in a weighted graph (with positive or negative edge weights). A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between *all* pairs of vertices though it does not return details of the paths themselves. The algorithm is an example of dynamic programming.

The code of this program is available at: https://bitbucket.org/vidyakv/graph-algorithms-in-c/changeset/0772753fa848#chg-floyd1.c

Note: The images used in this post is taken from wikipedia.