Main menu

Media Coverage

<div class="small-4 columns">media 1</div>

<div class="small-4 columns">media 2</div>

<div class="small-4 columns">media 3</div>

Reach to Us

Basic Terms Related to Graph

GRAPH ALGORITHMS | What is graph algorithm? | Two types of graphs | Graph algorithms | Minimum spanning Tree | Prims Algorithm | Kruskal’s Algorithm | Graph coloring

CONTENTS

List of topics that we cover in this article:

  • What is graph algorithm?
  • Two types of graphs
  • Graph algorithms
  • Minimum spanning Tree
  • Prims Algorithm
  • Kruskal’s Algorithm
  • Graph coloring.
  • Conclusion.

GRAPH ALGORITHMS

  • What is graph algorithm?

Graph is defined as a data structure which consists of nodes and edges. Edges are used to connect two nodes. Sometimes we may also call nodes as vertices and edges as arcs.

            Vertices are represented with V and edges are represented as E

  • Where v= {1, 2, 3, 4 5} and E= {12, 25, 54, 43, 13, 23, 24}
  • We use graphs in our daily life. Consider a node as a person which contains information about person’s id, name, address. It means that here node is like a structure.
  • Two types of graphs:
  • Directed graph
  • Undirected graph
  • Directed graph:

Directed graph is a graph in which nodes will have a direction.

  • Undirected graph:

Undirected graph is a graph defined as edges won’t have direction.

  • Minimum spanning tree:

Minimum spanning tree is defined as whole sum of weight of all edges should be less when be compared all other possible spanning tree of a graph is called as minimum spanning tree.

  •  

The cost of a spanning tree should be less than all other possible spanning trees is known as minimum spanning tree.

now let’s see remaining possible spanning trees:

Now select the cost of spanning tree which is less compared to all other spanning trees.

 

To calculate the minimum spanning tree, we must use methods

  • Prims algorithm
  • Kruskal’s algorithm
  • Prims algorithm:

Prims algorithm is a greedy algorithm used to find the minimum spanning tree. Prims algorithm firstly selects node and then find the edge with minimum weight.

  • Procedure for prims algorithm:
  • First select undirected weighted graph.
  • Select a vertex
  • Choose a shortest edge from vertex and join it
  • Choose a nearest vertex that should not be in solution.
  •  Choose a nearest edge and select one at random from multiple choices.

After applying prims algorithm, the spanning tree is:

  • Kruskal’s algorithm:

Kruskal’s is one of the most popular algorithms used to find the minimum spanning tree uses different logic compared to prims. Kruskal’s find the low weighted edge firstly and after high weighted edge keep on adding with low edges by simply eliminating that creates a loop.

  • Procedure for Kruskal’s algorithm:
  • Select a minimum weighted edge e1.
  • Next select another minimum weighted edge that should be connected to e1.
  • Choosing a next minimum weighted edge that should not be create any cycles.
  • Repeat this process until you have a minimum spanning tree.

The minimum spanning tree is:

  • Graph coloring:

Graph coloring is a method of giving color to the vertices and the two adjacent vertices should not have the same color.

  • Vertex coloring
  • Edge coloring
  • Face coloring
  • Chromatic number:

Chromatic number is a number that tells how many numbers of colors are needed for a graph.

Example: chromatic number for the following graph is 3.

  • Assign a some random color to the vertex that same color should not be assigned to adjacent vertices.

 

  • Conclusion:

These algorithms are used to solve different kind of complex problems. The goal of every algorithm is same but the functionality or logic is different. Graphs are used in real time like connecting people in social media and one more example is using google maps for finding routes.

Contributor's Info

Created:
0Comment