Graph Algorithm - Parallel Algorithm

What is a graph algorithm?

A notation that is used for representing the connection between the pairs of objects is known as a Graph. The graph consists of:

• Vertices – Vertices, also known as nodes are interconnected objects in a graph.
• Edges – The links that connect the vertices are edges.

Graphs are of two types −

• Directed graph – Edges have directions in a directed graph in the sense that edges go from one vertex to another.
• Undirected graph – Edges do not have any directions in an undirected graph.

How colouring is assigned in Graphs?

Colours are assigned to the vertices of the graph such that no two vertices have the same colour. Some of the problems related to Graph colouring are:

• Vertex coloring – The vertices of the graph are coloured in such a way that same colour is not shared by no two adjacent vertices.
• Edge Coloring – The colour is assigned to each of the edge such that same colour is not done to no two adjacent edges.
• Face coloring − It assigns a color to each face or region of a planar graph so that no two faces that share a common boundary have the same color.

Chromatic Number

To colour a graph, the minimum number of colour required is known as Chromatic number. For instance, for the below graph, the chromatic number is 3.

Timetables, mobile radio frequency assignments, Suduku, register allocation and maps are prepared by using the concept of graph colouring.

Steps for graph coloring

• The initial value for each processor in the n-dimensional array is set to 1.
• A particular colour is assigned to the vertex by determining whether that colour is already assigned to the adjacent vertices or not.
• Set the initial value of each processor in the n-dimensional array to 1.
• When same colour is detected by the processor in adjacent vertices, the value of the array is set to 0.
• After making n2 comparisons, if any element of the array is 1, then it is a valid coloring.

Pseudocode for graph coloring

Minimal Spanning Tree

For a spanning tree, the sum of weight of edges is less than all the possible spanning tree of the graph, is known as minimal spanning tree or minimum cost spanning tree. A weighted connected graph is depicted below:

The possible spanning trees out of the above graph are as follows:

Figure (d) is the minimum spanning tree among all the spanning trees. For the problems related to salesman travelling, electronic circuit design and network design and efficient routing algorithms designing, the concept of minimum cost spanning tree is applicable.

The minimum cost-spanning tree is implemented by using the following methods -

• Prim’s Algorithm
• Kruskal’s Algorithm

Prim's Algorithm

The minimum spanning tree for a weighted undirected graph is identified by using the Prim’s algorithm. First a vertex is selected and an edge with the lowest weight incident is identified.

Steps of Prim’s Algorithm

• Select any vertex, say v1 of Graph G.
• Select an edge, say e1 of G such that e1 = v1 v2 and v1 ≠ v2 and e1has minimum weight among the edges incident on v1 in graph G.
• Following step 2, select the minimum weighted edge incident on v2.
• Continue this till n–1 edges have been chosen. Here n is the number of vertices.

The minimum spanning tree is −

Kruskal's Algorithm

The minimum spanning tree with a connected weighted graph is found by adding the increasing cost arcs at each and every step. An edge of the least possible weight that connects any two trees is identified by this minimum-spanning-tree algorithm.

Steps of Kruskal’s Algorithm

• Select an edge of minimum weight; say e1 of Graph G and e1 is not a loop.
• Select the next minimum weighted edge connected to e1.
• Continue this till n–1 edges have been chosen. Here n is the number of vertices.

The minimum spanning tree of the above graph is −

Shortest Path Algorithm

A method that finds the least cost path from the source node to the destination node is Path algorithm. Moore’s algorithm is also known as Breadth First Search Algorithm.

Moore’s algorithm

• Label the source vertex, S and label it i and set i=0.
• Find all unlabeled vertices adjacent to the vertex labeled i. If no vertices are connected to the vertex, S, then vertex, D, is not connected to S. If there are vertices connected to S, label them i+1.
• If D is labeled, then go to step 4, else go to step 2 to increase i=i+1.
• Once the length of the shortest path is found, stop.