A notation that is used for representing the connection between the pairs of objects is known as a Graph. The graph consists of:
Graphs are of two types −
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:
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
Pseudocode for graph coloring
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 -
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.
The minimum spanning tree is −
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.
The minimum spanning tree of the above graph is −
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.
Parallel Algorithm Related Tutorials
|Data Structure & Algorithms Tutorial|
Parallel Algorithm Related Practice Tests
|Data Structure & Algorithms Practice Tests|
All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd
Wisdomjobs.com is one of the best job search sites in India.