Graph Search Algorithms

 

Searching the graph means systematically following the edges of the graph, so as to visit the vertices. It helps us in discovering the structure of the graph.

 

You are being introduced to two great algorithms of graph search. These algorithms make a lot of work possible in linear time:

 

1) Breadth First Search

2) Depth First Search

 

Contributor's Info

Created:
0Comment
Representation of Graphs

Representation of Graphs

 

We can represent any type of graph, directed, undirected, weighted, unweighted, simple, etc  using any of the below methods:

  • Adjacency list
  • Adjacency matrix

We will use the below directed and undirected graphs respectively as our reference and represent them through list and matrix.

Fig 1:     

Fig 2:      

Adjacency List

Follow the steps and match your answer with my answer.

Step 1: choose any graph, whichever you like from the above two given ones

Step 2: create an array named Adj with size as the number of vertices of your chosen graph

Step 3: this array will have indices as the vertices name, let us say, I chose fig 1, then my indices are 1, 2, 3, 4, 5. this array will look as below

Fig 3:       

Step 4: this array you created is an array of pointers. don't store any value. instead, you will be storing addresses in step 5

Step 5: create a node with two fields, value and next(address).

Step 6:

now, this is a very simple step, very very simple, just pay heed carefully. in fig 1, vertex 1 is connected to vertex 2 and vertex 5.

so create two nodes, store value 2 in one node and value 5 in other.

these nodes will look like below

Fig 4:     

Now, Adj[1] will connect to these two newly created nodes. (You can connect 2 first or 5 first, your wish)

This step will look something like:

Fig 5:   

So that was it.

Now complete your adjacency list.

You can match your adjacency list with the below fig 6 corresponding to fig 1 and fig 7 corresponding to fig 2

Fig 6:        

Fig 7:          

Congrats :)

Adjacency Matrix

Follow the steps and match your answer with my answer.

Step 1: choose any graph, whichever you like

Step 2: create a 2-d array named Adj with size as the (number of vertices x number of vertices) of your chosen graph, I chose Fig 1

Step 3: this array will look like this

Fig 8:    

Step 4: use the following definition for storing the values in the adjacency matrix

Adj[i][j]={ 0 or ∞  when edge ij do not belong to the graph, 1 when edge ij do belong to graph }

depending on the problem, the absence of an edge is represented by 0 or ∞

Step 5: match your adjacency matrix with below fig 9 corresponding to fig 1 and fig 10 corresponding to fig 2

Fig 9:

Fig 10:

Congrats once again :)

 

Analysis of Space

 

i) Adjacency List

Can you analyze how much space an adjacency list will be using? Look carefully.

 

First, you need an array of pointers of size=number of vertices in graph. So you need O(V) space for this....(actually, O(v) has to be multiplied by size of a pointer, but we are doing asymptotic analysis, so we will ignore that part for now)

 

Now, this is a very simple step, how many nodes you need in adjacency list representation of Fig 1? You need eight nodes. How many edges you have? You have 4 edges. See a pattern?  You are required to have '2 x number of edges' extra nodes. So you need O(2E) space, which is aysmptotically equal to O(E)

 

A second observation, how many nodes you need in adjacency list representation of Fig 2? You need eight nodes. How many edges you have? You have 4 edges. See a pattern again?  You are required to have 'number of edges' extra nodes. So you need O(E) space.

 

Hence total space needed for fig 1=O(V+2E)=O(V+E)

And total space needed for fig 2=O(V+E)

 

To be noted, adjacency listrepresentation has always a need of O(V+E) space irrespective of graph being directed/undirected/weighted/unweighted, etc

 

ii)Adjacency Matrix

This is easier than adjacency list. You have a 2-d square matrix of V*V elements. Space needed? O(V2).

 

To be noted, adjacency matrix representation has always a need of O(V2) space irrespective of graph being directed/undirected/weighted/unweighted, etc

 

Some useful terminologies of graphs

  • Transpose of a graph: Transpose of a graph G=(V,E) is GT=(V,ET) such that, GT is G with all its edges reversed. For example, (a,b) is an edge in a directed graph, then its transpose will have now (b,a)
  • Handshaking Lemma:

i) The sum of degrees of all the vertices in an undirected graph equals twice the number of edges.

ii) The sum of indegrees of all the vertices in a directed graph equals the number of edges.

     The sum of outdegrees of all the vertices in a directed graph equals the number of edges.

 

 

Explanation for undirected graph: Each edge is incident on two vertices. Therefore each edge is counted twice

 

 

Contributor's Info

Created:
0Comment
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