graphs

Dijkstra’s algorithm

http://install4install.com

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:

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
By Cusp2207 on July 18, 2014 | Algorithms, Computer Science | A comment?
Tags:

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:

Breadth First Search in Graphs

Breadth First Search is a technique to visit all the nodes of graph in a well-defined way.This technique can be applied  to  directed,undirected,weighted or unweighted  graph.Queues are used as a data structure to store elements.

  • BFS traverses all the nodes and edges of graph.
  • BFS in graph with m vertices and n edges takes O(n+m) time.

Example

Say we have a graph as shown in  Fig 1

Screen Shot 2014-07-15 at 5.09.35 PM

Fig 1 : A Graph

 

  • Start from any vertex say A.(Fig 2)
  • Visit and mark A.
  • Look for neighbors of A.
  • Result list –> A
  • Find all the vertices connected to A.E,B,D are connected to A .
  • Pick any random neighbor of A.Say B.
Screen Shot 2014-07-16 at 1.26.21 PM

Fig 2 : Mark A

1

Fig 2 : Mark B

 

  • Visit B and mark it.(Fig 2)
  • Add B to the queue.
  • Result –> AB
  • Look for next vertex which is connected to A.
  • Say  D is chosen.
  • Result –>ABD
  • Visit D and mark it.(Fig 3)
  • Add D to the queue.
Screen Shot 2014-07-15 at 5.27.56 PM

Fig 3 : Mark D

  • Look for any another vertex connected  to A.
  • E is connected to A.(Fig 4)
  • Visit E and mark it.
  • Result –>ABDE
  • Add E to the queue.
  • Screen Shot 2014-07-15 at 5.30.31 PM

    Fig 4 : Mark E

  • Look for any other vertex connected to A.
  • No other vertex is connected to A.
  • Now,dequeue B.
  • Screen Shot 2014-07-15 at 5.35.13 PM
  •  Find neighbor vertices  connected to B.
  • Visit C and mark it.(Fig 5)
  • Result –> ABDEC
  • Add C to the queue.
Screen Shot 2014-07-15 at 5.39.08 PM

Fig 5 : Mark C

  • Look for next unvisited element connected to B.
  • No other unvisited element is connected to B.
  • Dequeue D.
  • Screen Shot 2014-07-15 at 5.42.49 PM
  • Look for another unvisited vertices connected to D.
  • No other unvisited vertex is connected to D.
  • Dequeue E.
  • Screen Shot 2014-07-15 at 5.44.40 PM
  • Look for unvisited neighbors of E.
  • Visit F and mark it.(Fig 6)
  • Result –> ABDECF
  • Add F to the queue.
Screen Shot 2014-07-15 at 6.07.19 PM

Fig 6 : Mark F

 

  • Look for another vertex connected to E.
  • G is connected to E.
  • Visit G and mark it.(Fig 7)
  • Result –> ABDECFG
  • Add G to the queue.
Screen Shot 2014-07-15 at 6.08.57 PM

Fig 8 : Mark G

 

  • There are no unvisited neighbors of C,F, and G.
  • Dequeue C,F and G one by one.

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

Representation of Graphs

Graphs can be represented by

  • Adjacency Matrix by Sequential Representation
  • Linked Representation by using an adjacency list that stores neighbors of a node using linked list.

Adjacency Matrix

  • It represents which nodes are adjacent to each other i.e. which nodes have edge connecting between them.
  • Rows and Columns are labeled by graph vertices.
  • a is the adjacency matrix,i represents row, j represents column,v i and vj represents vertices.
  • aij is 1 if  v i and vj are adjacent to each other and 0 if they are not.
  • Adjacency Matrix is also known as Bit matrix or Boolean Matrix since it contains only o’s and 1’s.

 

Undirected Graph

The graph is shown in Fig 1 and matrix is shown in Fig 2.

Fig 1 : An Undirected Graph

Fig 1 : An Undirected Graph

Screen Shot 2014-05-13 at 2.31.29 PM

Fig 2 : Adjacency Matrix of Fig 1

 

Directed Graph

The graph is shown in Fig 3 and matrix is shown in Fig 4.

Screen Shot 2014-05-13 at 12.58.35 PM

Fig 3 : An Undirected Graph

Screen Shot 2014-05-13 at 2.29.56 PM

Fig 4 : Adjacency matrix of Fig 3

 

 

Weighted Graph

The graph is shown in Fig 5 and matrix is shown in Fig 6.

 

Screen Shot 2014-05-13 at 2.37.22 PM

Fig 5 : A Weighted Graph

Screen Shot 2014-05-13 at 2.39.24 PM

Fig 6 : Adjacency matrix of Fig 6

 

 

Adjacency List

It is an another way to represent graphs in computer memory.It is a linked representation in which every node is linked to its own list that contains he names of all other nodes which are adjacent to itself.The graph is shown in Fig 7 and list is shown in Fig 8.

Screen Shot 2014-05-09 at 4.28.14 PM

Fig 7 : A Graph

Screen Shot 2014-05-13 at 3.55.37 PM

Fig 8 : Adjacency list of Fig 7

 

Advantages of Adjacency List

  • It clearly shows the adjacent nodes of a particular node.
  • Adding new nodes in the list is easy as compared to adding nodes in the adjacency matrix.

Short URL: http://tinyit.cc/9edc88

Graphs

A graph is a collections of vertices/nodes and edges(arcs).It is like a tree structure with a difference that it does not have any parent-child relationship between nodes.Instead,any complex relationships are possible between the nodes.A Graph G(Fig 1) is defined as an ordered set (V,E),where V(G) is the set of vertices and E(G) represents the edges that connect the vertices together.

Fig 2 shows a graph with V(G) = {A,B,C,D,E,F}

E(G) = {(A,B),(A,C),(B,D),(C,D),(C,F),(D,E)}

There are 6 nodes and 6 edges in this Graph.

Fig 1 : A Graph

Fig 1 : A Graph

Screen Shot 2014-05-07 at 3.18.23 PM

Fig 2 : A Graph

 

Terms associated with Graph

  • Adjacent Nodes –  For every edge, E = (U, V) that connects nodes U and V; the nodes U and V are the end-points and are said to be the adjacent nodes.In Fig 2,A and B are adjacent nodes.
  • Degree – Degree of a node a is the total number of edges associated with the particular node.For e.g. ,degree of vertex A  in Fig 2 is 2.
  • Path – The route/way followed by edges from one node to another node.
  • Cycle – A closed simple path with length 3 or more is known as cycle.For e.g. P = {A,B,D,E,F,D} forms a cycle in Fig 3.
  • Multiple edgesDistinct edges which connect the same end points/vertex are known as multiple edges.E = (A,C) and E’ = (D,C) are multiple edges in Fig 2.
  • Loop – An edge that has identical end points is called as Loop.P = {A,B,D,C,A} forms a loop in Fig 2.
  • Size of Graph – It is the total number of edges in the graph.Size of graph in Fig 2 is 6.

Types of Graphs

Directed Graph

Screen Shot 2014-05-07 at 5.14.44 PM

Fig 3 : A Directed Graph

In a directed graph,edges have an orientation and  form an ordered pair (Fig 3). If there is an edge from A to B, then there is a path from A to B but not from B to A. The edge (A, B) is said to initiate from node A (also known as initial node) and terminate at node B (terminal node).Fig 3 is a directed graph with directed edges  {(A,B),(B,D),(D,E),(E,F),(F,D)}

 

Undirected Graph

Screen Shot 2014-05-08 at 2.49.21 PM

Fig 4 : Undirected Graph

A graph is called as undirected if the edges do not have any orientation.The edge can be traversed from one point to another and vice versa.Traversal can be done from A to B and B to A in Fig 4 and same is applicable for other nodes also.

Regular Graph

Fig 5 : A Regular Graph

Fig 5 : A Regular Graph

A regular graph is a graph where each vertex Â has the same number of neighbors, i.e., every vertex has the same degree . In Fig 5.degree of every vertex is 2.

Connected Graph

Screen Shot 2014-05-08 at 3.10.39 PM

Fig 6 : A Connected Graph

A graph is said to be connected if there is no isolated node and there exists a path between any of the two nodes i.e there will be at least one edge emerging from any of the vertices  in  graph(Fig 6).

 

Complete Graph

Screen Shot 2014-05-08 at 3.13.58 PM

Fig 7 : A Complete Graph

A graph G is said to be a complete, if there is always a  path from one node to another i.e if all the nodes are fully connected(Fig 7).

Weighted Graph

Screen Shot 2014-05-08 at 3.21.58 PM

Fig 8 ; A Weighted Graph

A graph is said to be weighted if every edge has some data/value  associated with it.It is denoted by w(e) and is a positive value referring to  the cost of traversing the edge.Weight of the graph as shown in Fig 8 , w(e) is 29.Cost of traversing edge A to B is 2,B to C is 5,C to D is 6,D to E is 9,E to A is 7.

 

Multi-Graph

Screen Shot 2014-05-08 at 3.27.48 PM

Fig 9 : Multi-Graph

 

A graph in which vertex  have  multiple edges  and /or  loops is called a multi-graph(Fig 9).


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