# graphs

## 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

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

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.

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.

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.

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.

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.

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.

Fig 8 : Mark c

• Distance of neighbors of c is not required to be updated.
• Mark d and then e.(Fig 9)

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.

Fig 10

Short URL: http://tinyit.cc/eff02d
August 12, 2014 |
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.

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.

Fig 2

• Now,mark Edge(S,W) with weight 1.
• Mark vertices S and W also.(Fig 3)

Fig 3

• Next min weight edge is 2.
• Mark Edge(Q,P) and vertex P.(Fig 4)

Fig 4

• The next min value in the graph is 3.
• Mark Edge(R,S).(Fig 5)

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)

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

Fig 7

Short URL: http://tinyit.cc/91e90b
July 18, 2014 |
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.

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

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.

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)

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.

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)

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)

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)

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)

Fig 9

• Replace value at Q by 2 and parent by P.(Fig 10)

Fig 10

• Mark 2 and vertex Q.
• Add Q to the set.(Fig 11)

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

Fig 12

Short URL: http://tinyit.cc/ed088
July 17, 2014 |
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.

Fig 1 : A Graph

• Pick any random vertex.Say A.
• Visit A and mark it.(Fig 2)
• Result Sequence–> A

Fig 2 : Mark A

• Push A to the stack.(Fig 3)

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

Fig 4 : Mark B

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

Fig 6 : Mark C

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

Fig 8 : Mark D

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)

Fig 10 : Mark E

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)

Fig 12 : Mark G

Fig 13 : Push G

• Mark F and add to the stack(Fig 14,15)

Fig 14 : Mark F

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.

Fig 16 : Pop F

Fig 17 : Pop G

Fig 18 : Pop C

Fig 19 : Pop C

Fig 20 : Pop B

Fig 21 : Pop A

Short URL: http://tinyit.cc/d9f0cd
July 16, 2014 | Computer Science
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

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.

Fig 2 : Mark A

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.

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.
• Fig 4 : Mark E

• Look for any other vertex connected to A.
• No other vertex is connected to A.
• Now,dequeue B.
•  Find neighbor vertices  connected to B.
• Visit C and mark it.(Fig 5)
• Result –> ABDEC
• Add C to the queue.

Fig 5 : Mark C

• Look for next unvisited element connected to B.
• No other unvisited element is connected to B.
• Dequeue D.
• Look for another unvisited vertices connected to D.
• No other unvisited vertex is connected to D.
• Dequeue E.
• Look for unvisited neighbors of E.
• Visit F and mark it.(Fig 6)
• Result –> ABDECF
• Add F to the queue.

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.

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.

• 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 2 : Adjacency Matrix of Fig 1

### Directed Graph

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

Fig 3 : An Undirected Graph

Fig 4 : Adjacency matrix of Fig 3

### Weighted Graph

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

Fig 5 : A Weighted Graph

Fig 6 : Adjacency matrix of Fig 6

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.

Fig 7 : A Graph

Fig 8 : Adjacency list of Fig 7

• 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
May 14, 2014 |
Tags:

## 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 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

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

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

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

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

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

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

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
May 8, 2014 |
Tags: