Computer Science

Big Omega(Ω) Notation

http://install4install.com

Ω Notation provides the asymptotic lower bound on the function. A function needs to satisfy some conditions in order to be in Ω notation.Ω(g(n)) is the best case running time  of function g(n) within a constant factor.

Ω(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0}.It is used to bound the best case running time of an algorithm.g(n) is an asymptotic lower bound for f(n).

Screen Shot 2014-07-28 at 3.45.31 PM

 

Example 1

  • Prove that if  f(n) = 15n3 + n2 + 4, then f(n) belongs to Ω(n3 ) for all n.
  • For omega notation,c*g(n) should be less than f(n).
  • Here f(n) = 15n3 + n2 + 1
  • g(n) = n3
  • Let c=15
    •  15  n3 <=  15n3 + n2 + 1
    • n=1 
  • f(n) belongs to Ω class.
  • Ω is the lower bound.

Example 2

  • Show that 2n +7 is Ω(n) .
  • f(n) = 2n + 7
  • g(n) = 2n
  • c * g(n) <= f(n)
    • c*2n <=2n+7
    • Let c=2
    • 4n<=2n+7
    • 2n<=7
    • n<=7/2
  • Thus for c=2 and  n0= 7/2 f(n) belongs to Ω(n).

 

 


Short URL: http://tinyit.cc/49f498
By Cusp2207 on March 4, 2016 | Algorithms, Computer Science | A comment?
Tags:

Dijkstra’s algorithm

Dijkstra’s algorithm is way of finding shortest path from a source vertex to sink in a given connected and weighted graph.It is somewhat similar to Prim’s algorithm.It works for directed as well as undirected graphs.

  • Source vertex is chosen and marked.
  • Mark distances at all vertices as infinity and at source vertex as 0.
  • Update the distances of adjacent vertices from infinity by given distances on the graph .
  • We look for minimum distance value from source vertex to adjacent vertices.
  • The minimum distance is chosen and next vertex is marked.
  • Look for the adjacent vertices of marked vertex.
  • Replace the distance if it is less than the mentioned value at the vertices.
  • Keep on following the same procedure until shortest path to sink is obtained.

 

Example

Consider a weighted and undirected graph as shown in Fig 1

 

Screen Shot 2014-08-11 at 1.37.58 PM

Fig 1 : A Graph

 

  • Choose a source vertex.In Fig 2 ,a is chosen as the source vertex.
  • Mark all the distances at vertices as infinity initially and distance of source vertex as 0
Screen Shot 2014-08-11 at 1.42.33 PM

Fig 2: Mark infinity at all vertices and 0 at the source.

 

  • Look for neighbors of source vertex a.(Fig 3).
  • b and i are the adjacent vertices.
  • Update the distance at b from infinity to 4 and at i to 8.
  • Find the minimum distance from a.
  • 4 is smaller than 8 so b is the next marked vertex.
Screen Shot 2014-08-11 at 1.44.47 PM

Fig 3:Update b ,i ,mark vertex b and Edge(a,b)

 

  • Look for the neighbors of b.
  • c and i are the adjacent vertices.
  • Update value at c from infinity to 12(4+8) as distance from source to c is 12.(Fig 4)
  • Distance from a to i through b is 15(11+4)  and a to i directly is 8.So 8 is not updated.
  • Look for next min distance  to a vertex and do not count already marked vertices and edges.
  • The distance at c is 12 and at i is 8,so i  is marked.
Screen Shot 2014-08-11 at 1.48.52 PM

Fig 4 : Update c to 12 and mark vertex i

 

  • Look for neighbors of i .
  • Update distance at h to 15(8+7) and at g to 9.
  • Distance from source a to b is 4 and a to b through i is 19 so it is not updated.
  • Look for next minimum distance from marked vertices.
  • 12,15,9 are the respective distances from marked vertices.
  • Mark vertex g and Edge(i,g) as 9 is the minimum distance from source a to g through i.
Screen Shot 2014-08-11 at 1.52.02 PM

Fig 5 : Mark g

 

  • Look for neighbors of g.
  • The distance at h from a through i  is 15 and from a through  i and g is again 15 so it is not updated(Fig 6).
  • The distance from a to f through i and g is 11.So update it by 11.
Screen Shot 2014-08-11 at 1.59.22 PM

Fig 6 : Update distance at f to 11

  • Look for the next minimum distance(Fig 7).
  • 12,15,11 are the distances from marked vertices.
  • Mark f and Edge(g,f) as distance is minimum.
Screen Shot 2014-08-11 at 2.01.26 PM

Fig 7 : Mark f

  • Neighbors of f are c,d,e.
  • Distance at c is not required to be updated.
  • Update distance at d to 25(11+14) and at e to 21(11+10)(Fig 8).
  • Look for minimum distance.
  • 12,15,19,21 are the distances available for consideration.
  • Mark vertex c as 12 is minimum.
Screen Shot 2014-08-11 at 2.02.43 PM

Fig 8 : Mark c

 

  • Distance of neighbors of c is not required to be updated.
  • Mark d and then e.(Fig 9)
Screen Shot 2014-08-11 at 2.06.17 PM

Fig 9 : Mark d and e.

 

The following table gives the details of dijkstra’s algorithm applied on Fig 1.The shortest path from a to e is {a,b,i,g,f,c,d,e} with minimum cost of 21.

Screen Shot 2014-08-11 at 4.35.16 PM

Fig 10


Short URL: http://tinyit.cc/eff02d
By Cusp2207 on August 12, 2014 | Algorithms, Computer Science | A comment?
Tags:

Big O Notation

 

  • It gives rate of growth of step count function(f(n)) in terms of simple function(g(n)) and defines the asymptotic upper bound on function(Fig 1).
  • To simplify the estimation for running time,constants and lower order terms are ignored.
  • The function needs to satisfy following conditions in order to be in Big-O class.Given functions f(n) and g(n),we say f(n) is  O(g(n)) if and if
    • f(n) < c * g(n)  for all n > n0
    • where c  and n0 are positive constants.
  • The function nis does not belong  to O(n) rather it belongs to O( n2 ) as it fails to satisfy the inequality f(n)<=cg(n).n2  cannot be less than n in any case as c is constant.
  •  O(..) is worst case (upper bound) notation for an algorithm’s complexity .
Fig 1: Big O Notation

Fig 1: Big O Notation

 

Example 1

  • Consider T(n)= 3n+2
  • g(n) = n
  • f(n) = 3n+2
  • We need to find first value of c where answer comes positive.Let c=1
  • f(n)<=c * g(n)
  • 3n+2 <= c *n
  • 3n+2 <= 1*n
  • The answer comes in negative,so we cant choose c=1.
  • Let c=2
  • 3n+2 <= 2n The answer again comes in negative,so we cant choose c=2.
  • c=3
  • 3n+2<=3n,can’t choose c=3
  • c=4
  • 3n+2<=4n
  • n>=2
  • n0=2 and c=3.This is the point where f(n) and g(n) meets.
  • Hence f(n)<=c*g(n) and thus belongs to big-O class.
  • Highest power of n is 1.
  • So f(n) belongs to O(n).

Example 2

  • Consider  T(n) = 2n2 + 4
  • g(n)=n
  • f(n) = 2n2 + 4
  •  2n2 + 4<=c *n
  • The inequality is false for c=1 and c=2.
  • c=3

2n2 + 4<=3 *n

4<=n

n=2 and n=-2,negative value is neglected.

  • n>=2,n0=2 ,c=3
  • Thus f(n) belongs to O(n) .

Example 3

  • T(n) = 3n3+20n2+ 5
  • 3n3+20n2+ 5 <=c * n
  • Is true for c=4 and n= 21
  • Thus 3n3+20n2+ 5 belongs to O(n3).

Example 4

  • T(n) = 3  log n +5
  • g(n) = log n
  • f(n) = 3 log n +5
  • f(n) <= c *g(n),c>0 and  n > n0
  • 3 log n + 5 <=c * log n
  • c =8 and n= 2
  • Thus 3n3+20n2+ 5 belongs to O(n3

Complexities of algorithms

The various big 0 complexities are given in Fig 2 and Fig 3.

Screen Shot 2014-07-25 at 6.27.09 PM

Fig 2: Complexities of sorting algorithms

Screen Shot 2014-09-11 at 12.56.46 PM

Fig 3 : Complexities of sorting algorithms

 

 

 


Short URL: http://tinyit.cc/e988e7
By Cusp2207 on July 26, 2014 | Algorithms, Computer Science | A comment?
Tags:

Time and Space Complexity

Before defining the actual term complexity, let us discuss about few real life scenarios.Take an example of railway reservation counter.People go there to book their tickets.The time to book tickets will depend on  how many service windows are available, queue size and time taken by each representative.A person will either go in a lane which is very short or will stand in queue where representative is very fast.Take another example of sitting plan of 40 students.The first thing to be considered is the no. of chairs needed and second thing is their order of sitting.If they sit roll.no wise then it will be easy for teacher to take attendance and time required will be lesser.Thus every process in the real world depends on how much time it takes to execute and how much space it consumes.Complexity is defined as the running time to execute a process and it depends on space as well as time.

It is of two types:

  • Space Complexity
  • Time Complexity

Basic Operation

Basic operation means the main operation that will be required to solve particular problem.For example the basic operation in searching is comparison.The complexity depends on the basic operation.

The focus to determine the cost is done on running time i.e time complexity and it depends on the following factors

  • Size of Input Data
  • Hardware
  • Operating System
  • Programming Language used

 

Space Complexity

The amount of computer memory required to solve the given problem of particular size is called as space complexity.The space complexity depends on two components

  •  Fixed Part – It is needed for instruction space i.e byte code.variable space,constants space etc.
  •  Variable Part – Instance of input  and output data.
  • Space(S) = Fixed Part + Variable Part

Example 1

Algorithm sum(x,y)

{

return x+y;

}

Two computer words will be required to store variable x and y so ,

Space Complexity (S)= 2.

Example 2

Algorithm sum( a[], n)

{

sum =0;

for(i=0;i<=n;i++)

{

sum = sum + a[i];

return sum;

}

Space complexity is calculated as follows

  • One computer word is required to store n.
  • n space is required to store array a[].
  • One space  for variable sum and one for i is required.
  • Total Space(S) =1 +n +1 +1=n+3

Time Complexity

The time required to analyze the given problem of particular size is known as the time complexity.It depends on two components

  • Fixed Part – Compile time
  • Variable Part – Run time dependent on problem instance.Run time is considered usually and compile time is ignored.

 

Ways to measure time complexity

  • Use a stop watch and  time is obtained in seconds or milliseconds.
  • Step Count - Count no of program steps.
    • Comments are not evaluated so they are not considered as program step.
    • In while loop steps are equal to the number of times loop gets executed.
    • In for loop,steps are equal to number of times an expression is checked for condition.
    • A single expression is considered as a single step.Example a+f+r+w+w/q-d-f is one step.
  • Rate of Growth(Asymptotic Notations)

 

Example of step count

Algorithm sum( a[], 5)

{

sum =0;

for(i=0;i<=5;i++)

{

sum = sum + a[i];

}

return sum;

}

 

Screen Shot 2014-07-24 at 4.29.43 PM

Fig 1 : Step Count

Step count is a difficult approach if we need to compare results.For e.g.If we used two techniques to solve one problem and T(1) is the running time of first technique and T(2) is the running time of second technique.Say T(1) =( n+1 )and T(2) is (n2 + 1).We cannot decide which one is the better solution,so for comparisons ‘Rate of growth‘  i.e. asymptotic notations of time space complexity functions are much convenient to use.

 

Asymptotic Notations

These notations gives the rate of growth.Instead of dealing with exact expressions we deal with asymptotic behavior.Asymptotic means to approach a value or curve arbitrarily closely.Focus is on the exponential behavior of equation.If we have expression like T(n)=3n3 +5 and T(n)=7 n3 +10n2+5 we will consider on highest power i.e n3.The analysis will not really change as these both equations are similar to n3.But on contrary we need to separate our results if analysis are like T(n) = 3n+5 and T(n)=10n2+5 as highest powers are different.The three asymptotic notations are:

Cases in complexity

  • Best Case
  • Average Case
  • Worst Case

Best Case

It is the minimum time required to solve the given problem of particular size.For e.g.in linear search if element is found at first location then it will be the best case scenario and complexity will be O(1) as the running time is minimum.

Average Case

It is average cost and time required for a given problem of particular size.For e.g. in linear search if there are n elements and item is found at n/2 location,then it will be a average case scenario and complexity will be O(n/2).

Worst Case

The maximum time required to solve a given problem of particular size.For e.g in linear search the worst case will either be item is present at last location or it is not present.The complexity will be O(n).


Short URL: http://tinyit.cc/f9484
By Cusp2207 on July 25, 2014 | Algorithms, Computer Science | A comment?
Tags:

Pop operation in Stack

POP Operation

In this  operation topmost element is deleted from the stack.Before deleting check if TOP = NULL.If yes,it means that stack is empty and no deletion can be done.If an attempt to delete element is made in this case the UNDERFLOW message will be printed on screen.If no,then element is deleted then value of TOP is decremented by 1.

For example

  • We want to delete/pop 100 from this stack(Fig 9).
  • TOP = 4
  • TOP is not equal to null.
  • 100 is popped out/deleted.
  • TOP variable gets decremented to 3.

 

Screen Shot 2014-04-08 at 5.17.45 PM

Fig 9 : Pop Operation in Stack

Program 2

#include<stdio.h>

int main()
{
	int max;
	int stack[10];
	int num,val,i,temp;
	int top = -1;
	//printf("Enter the maximum size of stack");
	scanf("%d",&max);
	//printf("Enter the no of elements in stack");
	scanf("%d",&num);
	//printf("Enter the elements of stack");
	for(i=0;i<num;i++)
	{
		scanf("%d\n",&stack[i]);
		top++;
	}
	temp =top;
	if(top == -1)
	{
		printf("Underflow");
	}
	else
	{
		top =top -1;
		printf("The stack after pop operation is \n");
		for(i=0;i<temp;i++)
		{
		 printf("%d\n",stack[i]);
		top++;
	}
	}
	return 0;
}

Run
 Illustration of Program 2

  • Refer Program 1 for working of for loop and consider the same values.
  • top = 4
  • temp = top i.e temp = 4
  • if( top ==-1) i.e if no element is present in the stack then Underflow message will be printed on screen as no element is present to pop out.
  • top = top -1 =4-1=3.
  • for(i=0;i<temp;i++) - i would iterate till it is less than temp(4).
  • Elements of stack after pop operation is printed.

Short URL: http://tinyit.cc/dd0e98

Push operation in Stack

Push Operation

In this operation,the element is inserted at the top of stack(Fig 4).In order to insert element we need to check whether TOP = MAX-1.If  yes,then insertion  is not possible.If  element is still  tried for insertion , OVERFLOW message will be printed on screen as the stack do not have extra space to handle new element.If space is present and element is inserted,then the value of top will be incremented by 1 .

For example

  • Say we want to insert/push 800 in the following stack(Fig 4).
  • TOP = 4(index starts from 0)
  • MAX= 13
  • The value of TOP is 4 and MAX-1 is 13-1=12.TOP and MAX are not equal,thus element 800 can be pushed into the stack.
  • After insertion value of TOP gets incremented t0 5.
Screen Shot 2014-04-08 at 5.01.32 PM

Fig 5 : Push Operation in stack

Program 1

#include<stdio.h>
int main()
{
	int stack[10];
	int max;
	int num;
	int top = -1;
	int i;
	int item;
	//printf("Enter the maximum size of stack");
	scanf("%d",&max);
	//printf("Enter the no of elements in stack");
	scanf("%d",&num);
        //printf("Enter the elements of stack");
	for(i=0;i<num;i++)//Fig 7
	{
		scanf("%d\n",&stack[i]);
		top++;
	}

	if(top == max -1)//Fig 8
	{
		printf("Overflow");
	}
	else
	{
		//printf("Enter the item you want to insert\n");
		scanf("%d",&item);
		top = top + 1;//Fig 6
		stack[top] = item;
		printf("The stack after push operation is \n");
		for(i=0;i<=num;i++)
	{
	 printf("%d\n",stack[i]);
		top++;
	}
	}

	return 0;
}

Run

 Illustration of Program 1

  • Integer array of stack with size 10 is defined.
  • max is the maximum capacity of stack(Say 10).
  • num is the actual number of elements in stack(Say 5).
  • Variable top is initialized to -1.
  • i is used in for loop and item is the element we want to push in stack.
  • for loop(Fig 7) and scanf are used to read the values of stack.
Screen Shot 2014-04-09 at 1.11.26 PM

Fig 6 : Push Operation

 

Screen Shot 2014-04-09 at 1.03.37 PM

Fig 7 : Working of for loop

Screen Shot 2014-04-09 at 1.03.57 PM

Fig 8 : Working of if statement

 

 


Short URL: http://tinyit.cc/8c08e2

Binary Search

Binary Search

The binary search technique works only on sorted array.It works by comparing the input element to the middle element of array.The comparison determines whether the element is less than.greater than or equal to middle element.Subsequent steps to be followed are written and explained by the following program.

Program

#include <stdio.h>

int main()
{
	int val[10] = {10,20,30,40,50,55,68,77,89,90};//Fig 3
	int beg = 0;   //first index of array
	int end = 9;  //end(last index of array)  = n-1 where n is the size of array and is 10 in this case.
	int mid = (beg+end)/2; // finds middle index of array.
	int i;
	int element;
	//printf("enter the element you want search for");
	scanf("%d",&element);
	for(i=0;i<10;i++) //Fig 4
	{
	if(val[mid] == element)	{
		break;
	}
	else if(val[mid] < element) {
	beg = mid +1;
	mid = (beg +end)/2;
	}
	else{
	end =mid -1;
		mid = (beg +end)/2;
	}
	}
	printf("Location of element is %d",mid);
	return 0;
}

Run

Illustration
Fig 3:An Array

Fig 3:An Array

  • val[10] of int type is initialized with values 10,20,30,40,50,55,68,77,89,90.
  • beg variable of int type denotes the first index of array i.e. 0
  • end variable of int type denotes the last index of array .It is equal to (n-1),where n is the size of array.Here it is 10 so end=10-1=9
  • mid index is calculated by adding beg plus end and the dividing the result by 2.
  • element variable of int type is the data item which needs to be searched for in array and is entered by user using scanf.
  • Say we want to search for 68 .
  • The following  figure explains the working of for loop to find 68.
Screen Shot 2014-03-19 at 4.43.35 PM

Fig 4 : Explanation of Binary Search Program


Short URL: http://tinyit.cc/89edd

Kruskal’s Algorithm

Kruskal’s algorithm is a greedy technique  used to find minimum spanning tree from the graph.It works on edges rather than on vertices in connected weighted graph.MST is obtained by finding global optimal choice.

Technique

  • Mark the minimum weight edge in the graph and mark the respective vertices.
  • Now,mark the next minimum value in the graph.
  • If there are two or more edges with same weight then select any edge at one time and then select others one by one.
  • We need to mark edges according to the increasing weight of edges of different vertices.
  • Do not mark any edge on the graph which makes a cycle.
  • Keep on repeating the process till MST is obtained.

Example

Consider connected weighted graph in Fig 1.

Screen Shot 2014-07-18 at 12.25.40 PM

Fig 1 : A Graph

 

  • The minimum edge weight on the graph is 1.Edge(Q,R) and Edge (S,W) have same weight i.e 1.
  • Choose any edge between them.
  • Say we mark Edge(Q,R).(Fig 2)
  • Mark vertices Q and R also.
Screen Shot 2014-07-18 at 12.27.33 PM

Fig 2

  • Now,mark Edge(S,W) with weight 1.
  • Mark vertices S and W also.(Fig 3)
Screen Shot 2014-07-18 at 12.29.54 PM

Fig 3

 

  • Next min weight edge is 2.
  • Mark Edge(Q,P) and vertex P.(Fig 4)
Screen Shot 2014-07-18 at 12.55.52 PM

Fig 4

 

  • The next min value in the graph is 3.
  • Mark Edge(R,S).(Fig 5)
Screen Shot 2014-07-18 at 12.34.01 PM

Fig 5

 

  • The next min value is 4.
  • Choose any edge between Edge(Q,T) or Edge(S,T).
  • Say we mark Edge(S,T) with weight 4.
  • The next value to be marked is 4 but if we will mark Edge(Q,T) a cycle SRQTS will be formed.
  • So,do not mark this edge.
  • We do  not mark Edge(P,R) with weight 5,Edge(T,W) with weight 6,Edge(P,S) with weight 13 for the same reason.(Cycle formation).
  • Now,mark Edge(W,X) with weight 14 and mark vertex X.(Fig 6)
Screen Shot 2014-07-18 at 12.35.15 PM

Fig 6

 

Minimum spanning tree is obtained as shown in Fig 7 and cost of minimum spanning tree is obtained by adding weights of all edges i.e 2+1+3+4+1+14=25

Screen Shot 2014-07-18 at 12.36.55 PM

Fig 7


Short URL: http://tinyit.cc/91e90b

Prim’s algorithm

Prim’s algorithm is a greedy algorithm as it  finds the global optimum answer from collecting locally optimum choices.It finds the minimum spanning tree and works for weighted,connected and undirected graph.Minimum spanning tree is a graph is edge weighted graph whose weight is smaller than any other spanning tree.A minimum spanning tree is obtained by combining all local optimal choices to a global one.

Technique

  • Put   as the weight at all vertices of the graph.
  • Write null as the parent of each vertex.
  • Pick any vertex from the graph.
  • Mark it and replace the distance from  ∞  to 0.
  • Look for adjacent vertices of marked vertex.
  • Replace   by given weights from the marked vertex to other vertices.
  • Replace parent null by marked vertex name.
  • Choose minimum weight edge from the marked vertex.
  • Mark edge and another vertex .
  • Look for the adjacent vertices.
  • If edge weight is smaller then replace the value as well by the parent.
  • Now,look for all  edges from previous and newly marked vertex.
  • Choose the unvisited  vertex which is at minimum edge weight  from marked vertices.(Do not look again at  marked vertices).
  • Repeat the process till optimum solution is reached.
  • Minimum spanning tree is obtained as a result.

 

Example

 

Consider graph in Fig 1.

Screen Shot 2014-07-16 at 5.53.32 PM

Fig 1 : A weighted graph

 

  • Initially,put   followed by null and separated by comma at all vertices of graph.(Fig 2)
  •    is the weight and null is the parent
Screen Shot 2014-07-16 at 5.57.22 PM

Fig 2

 

  • Choose any vertex from the graph.
  • Say T is chosen.
  • Mark T and replace weight  by 0.(Fig 3)
  • Add T to the set i.e resulting sequence.
Screen Shot 2014-07-16 at 5.59.11 PM

Fig 3

 

  • Look for adjacent vertices of T.
  • R,S,W are the adjacent vertices.
  • Replace weights of R,S,W by 12,4,6 respectively  they are the distances from T.
  • Replace parent of all adjacent vertices by T.(Fig 4)
Screen Shot 2014-07-16 at 6.01.50 PM

Fig 4

 

  • Choose the  edge from T which has minimum weight.
  • Edge(T,S) is the shortest i.e 4(compared to 12 and 6).
  • So mark the edge as well the vertex S.(Fig 5).
  • Add S to the set.
Screen Shot 2014-07-16 at 6.04.18 PM

Fig 5

 

  • Look for adjacent neighbors of S.
  • P,R,W are the adjacent vertices.
  • Replace value at P by 13 and parent by S, as 13 is the edge weight from S to P.
  • Compare the edge weight betweenEdge(S, R )and  Edge(T, R).
  • S to R is 3 and T to R is 12.3 is smaller than 12.
  • So,replace 12 by  3 and T by S.
  • Compare weights between  Edge (S , W) and Edge (T ,W).
  • S to W is 1 and T to W is 6.
  • 1 is smaller so replace 6,T by 1,S.(Fig 6)
Screen Shot 2014-07-16 at 6.07.02 PM

Fig 6

 

  • Look for minimum edge  from T and S respectively.
  • 1 is minimum value(Edge(S,W) ).
  • Mark edge(S,W) ,vertex W and add them to the set.(Fig 7)
Screen Shot 2014-07-16 at 6.10.49 PM

Fig 7

 

  • Do not look for visited vertices again.
  • Look for edges of T,S,W.
  • 3 is minimum edge value.
  • Mark edge and vertex R.
  • Add R to the set.
  • Look for unmarked adjacent vertices of R.
  • P is the  unmarked vertex adjacent to R.
  • Replace 13 by 5 and S by R as 5 is smaller than 13.(Fig 8)
Screen Shot 2014-07-16 at 6.13.52 PM

Fig 8

 

  • The next minimum value from edges of T,S,W,R is 5.
  • Mark 5 and P.
  • Add P to the set.(Fig 9)
Screen Shot 2014-07-16 at 6.15.24 PM

Fig 9

  • Replace value at Q by 2 and parent by P.(Fig 10)
Screen Shot 2014-07-16 at 6.16.20 PM

Fig 10

  • Mark 2 and vertex Q.
  • Add Q to the set.(Fig 11)
Screen Shot 2014-07-16 at 6.17.26 PM

Fig 11

Minimum spanning tree is obtained and shown in Fig 12 and cost of minimum spanning tree is obtained by adding weights of all edges i.e.

2+5+3+4+1 = 15

Screen Shot 2014-07-16 at 6.21.26 PM

Fig 12

 

 

 


Short URL: http://tinyit.cc/ed088
By Cusp2207 on July 17, 2014 | Algorithms, Computer Science | A comment?
Tags:

Depth First Search in Graphs

DFS technique is used to traverse graphs.Any vertex is chosen as the starting vertex .Element is pushed into stack.One adjacent vertex is randomly picked from adjacent vertices.It is marked and pushed it into stack.If adjacent unvisited neighbors are present then same process is followed otherwise element is popped off from the stack.Now,again one element is picked as the unvisited adjacent  element and marked.Same process if followed till all the vertices are visited.

Example

Consider graph in Fig 1.We need to perform DFS on it.

Screen Shot 2014-07-15 at 5.09.35 PM

Fig 1 : A Graph

 

  • Pick any random vertex.Say A.
  • Visit A and mark it.(Fig 2)
  • Result Sequence–> A
Screen Shot 2014-07-16 at 1.26.21 PM

Fig 2 : Mark A

  • Push A to the stack.(Fig 3)
Screen Shot 2014-07-16 at 2.10.30 PM

Fig 3 : Push A

 

 

 

 

 

 

 

 

 

 

 

  • Find the neighbors of A.
  • E,B,D are neighbors of A.
  • Pick random vertex.Say B.
  • Mark B.(Fig 4)
  • Push B to the stack.(Fig 5)
  • Result Sequence –> AB
1

Fig 4 : Mark B

 

Screen Shot 2014-07-16 at 2.20.52 PM

Fig 5 : Push B

 

  • Look for adjacent unvisited neighbors of B.
  • C is the neighbor.
  • Visit C and mark it.(Fig 6)
  • Push C to the stack.(Fig 7)
  • Result Sequence –> ABC
Screen Shot 2014-07-16 at 2.23.45 PM

Fig 6 : Mark C

Screen Shot 2014-07-16 at 2.24.25 PM

Fig 7 : Push C

 

  • Look for neighbors of C.
  • E and D are neighbors.
  • Say we mark D.(Fig 8)
  • Push D to the stack.(Fig 9)
  • Result Sequence –> ABCD
Screen Shot 2014-07-16 at 2.28.08 PM

Fig 8 : Mark D

Screen Shot 2014-07-16 at 2.29.06 PM

Fig 9 : Push D

 

  • Look for adjacent unvisited vertices of D.
  • There are no adjacent unvisited vertices.
  • Pop D and look for adjacent vertices of C.
  • E is the adjacent unvisited vertex.
  • Mark E.(Fig 10)
  • Push E to the stack.(Fig 11)

 

Screen Shot 2014-07-16 at 2.32.47 PM

Fig 10 : Mark E

Screen Shot 2014-07-16 at 2.33.24 PM

Fig 11 : Push E

 

  • Look for adjacent unvisited vertices of E.
  • G and F are the vertices.
  • Say G is chosen.
  • Visit G and mark it.(Fig 12)
  • Push G to the stack.(Fig 13)
Screen Shot 2014-07-16 at 2.35.42 PM

Fig 12 : Mark G

Screen Shot 2014-07-16 at 2.37.05 PM

Fig 13 : Push G

  • Mark F and add to the stack(Fig 14,15)
Screen Shot 2014-07-16 at 2.38.32 PM

Fig 14 : Mark F

 

Screen Shot 2014-07-16 at 2.41.21 PM

Fig 15 : Push F

 

  • No other unvisited adjacent element of F is present.
  • So,POP F.
  • Same is the case with other vertices.
  • So Pop all vertices one by one.
Screen Shot 2014-07-16 at 2.37.05 PM

Fig 16 : Pop F

Screen Shot 2014-07-16 at 2.33.24 PM

Fig 17 : Pop G

Screen Shot 2014-07-16 at 2.24.25 PM

Fig 18 : Pop C

Screen Shot 2014-07-16 at 2.20.52 PM

Fig 19 : Pop C

Screen Shot 2014-07-16 at 3.31.31 PM

Fig 20 : Pop B

Screen Shot 2014-07-16 at 3.31.58 PM

Fig 21 : Pop A

 

 

 

 

 

 

 

 

 

 


Short URL: http://tinyit.cc/d9f0cd
By Cusp2207 on July 16, 2014 | Computer Science | A comment?
Tags: