Monthly Archives: September 2011

Implementation of some graph algorithms in C

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.

Advertisements

Graph colouring using PyGame

In graphtheory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called “colors” to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring.  

In my program, I implemented the graph coloring in Python. The colouring code is given below:

The PyGame library is used here to visualize the graph colouring in Python. Pygame is a cross-platform set of Python modules designed for writing video games. It includes computer graphics and sound libraries designed to be used with the Python programming language.

The complete code of this program is available in my bitbucket account. Here is the link: https://bitbucket.org/vidyakv/graph-colouring-using-pygame/changeset/0698b8122965#chg-graph3.py

The WordPress.com Blog

The latest news on WordPress.com and the WordPress community.