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

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

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

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

- 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.**

- 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**.

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

- 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**a**t**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.

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

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**.

**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.

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

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

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

- The next min value in the graph is
**3**. - Mark Edge(
**R,S)**.(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)

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

**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.

- Initially,put
**∞**followed by**null**and separated by comma at all**vertices**of graph.(Fig 2) -
**∞**is the weight and**null**is the parent

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

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

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

- Look for
**adjacent**neighbors of S. **P,R,W**are the adjacent vertices.- Replace value at
**P**by 1**3**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)

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

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

- The next
**minimum**value from edges of**T,S,W,R**is**5**. **Mark 5**and**P**.- Add
**P**to the set.(Fig 9)

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

**Mark**2 and**vertex Q**.**Add Q**to the set.(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**

** **

**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.

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

- Push A to the stack.(Fig 3)

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

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

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

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

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

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

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

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

- 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**.

**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.

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

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

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

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

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 v_{j}represents vertices. - a
_{ij }is**1**if v_{ i }and v_{j}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**.

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

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

The graph is shown in Fig 5 and matrix is shown in 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.

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

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.

**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 edges**–**Distinct 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**.

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)}

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.

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.

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).

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).

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.

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