Basics of Graphs
Published: 2021-01-19 09:18:07

<!-- wp:image {"id":2387,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/graph.jpeg?w=1024" alt="" class="wp-image-2387"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p>I took this course, <a href="https://www.coursera.org/learn/algorithms-on-graphs/home/welcome" target="_blank" rel="noreferrer noopener">Algorithms on Graphs</a> by University of California San Diego &amp; National Research University Higher School of Economics. It had wonderful explanations of basics of graphs.</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><strong><em>Q.What is a Graph?</em></strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><strong>A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.</strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>&nbsp;A graph data structure (V, E) consists of:</p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>A <strong>collection of vertices (V)</strong> or nodes.</li><li>A <strong>collection of edges (E)</strong> or paths.</li></ol>
<!-- /wp:list -->

<!-- wp:image {"id":2331,"width":522,"height":377,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large is-resized"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/image-3.png?w=483" alt="" class="wp-image-2331" width="522" height="377"/></figure>
<!-- /wp:image -->

<!-- wp:image {"id":2329,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/image-2.png?w=616" alt="" class="wp-image-2329"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong><em>Use cases for Graph data structure:</em></strong></p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>use a graph to find out whether two places on a road-map are connected and what is the shortest distance between them</li><li>simulating electrical circuits to find out current flows and voltage drops at various points in the circuit.&nbsp;</li><li>algorithms used in social media applications</li></ol>
<!-- /wp:list -->

<!-- wp:image {"width":664,"height":445,"sizeSlug":"large","className":"is-style-default"} -->
<figure class="wp-block-image size-large is-resized is-style-default"><img src="http://programmerprodigycode.files.wordpress.com/2020/10/25d97-iu.jpg" alt="" width="664" height="445"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><em><strong>Graph Terminology</strong> <strong>Used</strong>:</em></p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li><strong>Path: </strong>It is the sequence of vertices in which each pair of successive vertices is connected by an edge.</li><li><strong>Cycle: </strong>It is a path that starts and ends on the same vertex.</li><li><strong>Simple Path: </strong>It is a path that does not cross itself that is, no vertex is repeated (except the first and the last). Also, simple paths do not contain cycles.</li><li><strong>Length of a Path: </strong>It is the number of edges in the path. Sometimes it’s the sum of weights of the edges also in case of weighted graphs.</li><li><strong>Degree of a Vertex: </strong>It is the number of edges that are incident to the vertex.</li><li><strong>Indegree of a Vertex: </strong> The indegree&nbsp; of a vertex is the number of edges for which it is head i.e. the numbers edges coming to it.&nbsp;</li><li><strong>Outdegree of a vertex</strong>:  The out degree of a vertex is the number of edges for which it is the tail i.e. the number of edges going out of it.&nbsp;<strong>A node whose outdegree is 0 is called a sink node.</strong></li><li><strong>Adjacent vertices: </strong>If (V<sub>i</sub>, V<sub>j</sub>) is an edge in G, then we say that V<sub>i</sub> and V<sub>j</sub>&nbsp; are adjacent and the edge (V<sub>i</sub>, V<sub>j</sub>) is <em>incident</em> on V<sub>i</sub> and V<sub>j</sub>.</li></ol>
<!-- /wp:list -->

<!-- wp:heading {"textAlign":"center","level":4} -->
<h4 class="has-text-align-center"><strong><em>different types of graphs</em></strong>:</h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p><strong>1. Undirected Graph: </strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>A graph is an undirected graph if the pairs of vertices that make up the edges are unordered pairs.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>i.e. an edge(V<sub>i</sub>, V<sub>j</sub> ) is the same as (V<sub>j</sub>, V<sub>i</sub>).&nbsp; The graph G<sub>1</sub> shown above is an undirected graph.&nbsp; </p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><strong>2.Directed Graph: </strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>In a directed graph, each edge is represented by a pair of ordered vertices. </p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>i.e. an edge has a specific direction.&nbsp;In such a case, edge (V<sub>i</sub>, V<sub>j</sub>) ≠ (V<sub>j</sub>, V<sub>i</sub>)</p>
<!-- /wp:paragraph -->

<!-- wp:image {"width":584,"height":289,"sizeSlug":"large"} -->
<figure class="wp-block-image size-large is-resized"><img src="https://external-content.duckduckgo.com/iu/?u=http%3A%2F%2Fwww.differencebetween.com%2Fwp-content%2Fuploads%2F2011%2F05%2FDifferenceBetween_Directed_UnDirected_Graphs1.jpg&amp;f=1&amp;nofb=1" alt="" width="584" height="289"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>3.Complete Graph: </strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>If an undirected graph has n vertices, the maximum number of edges it can have is nC<sub>2</sub> = n (n-1) / 2. If an undirected graph G has ‘n’ vertices and nC<sub>2</sub> edges, it is called a complete graph.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>&nbsp;If the graph G is directed and has n vertices, G is complete if it has n(n-1) edges.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:image {"width":492,"height":418,"sizeSlug":"large"} -->
<figure class="wp-block-image size-large is-resized"><img src="https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Ftse2.mm.bing.net%2Fth%3Fid%3DOIP.AJjsIYY_t_4icrXNjlUI9wHaGT%26pid%3DApi&amp;f=1" alt="" width="492" height="418"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>4</strong>.<strong>Multigraph: </strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>A multigraph is a graph in which the set of edges may have multiple occurrences of the same edge.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:image {"width":513,"height":336,"sizeSlug":"large","className":"is-style-default"} -->
<figure class="wp-block-image size-large is-resized is-style-default"><img src="https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Fwww.researchgate.net%2Fprofile%2FOded_Lachish%2Fpublication%2F220788909%2Ffigure%2Fdownload%2Ffig1%2FAS%3A668940938248204%401536499356625%2FMultigraph-and-its-underlying-graph-Lemma-1-If-there-is-an-algorithm-to-compute-the.png&amp;f=1&amp;nofb=1" alt="" width="513" height="336"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong><em>5.Cycle in graph?</em></strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><strong>Cycle: </strong>A cycle is a path whose first and last vertices are the same. For example, nodes abcd are cyclic.</p>
<!-- /wp:paragraph -->

<!-- wp:image {"align":"center","id":3225,"width":396,"height":169,"sizeSlug":"large","linkDestination":"none"} -->
<div class="wp-block-image"><figure class="aligncenter size-large is-resized"><img src="https://programmerprodigycode.files.wordpress.com/2020/12/image-49.png?w=480" alt="" class="wp-image-3225" width="396" height="169"/></figure></div>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>Acyclic</strong>: A graph with no cycles is called an <strong>acyclic</strong> graph. A directed acyclic graph is called <strong><em>dag</em></strong>.&nbsp;For example, in second example there is no cycle</p>
<!-- /wp:paragraph -->

<!-- wp:image {"sizeSlug":"large"} -->
<figure class="wp-block-image size-large"><img src="http://programmerprodigycode.files.wordpress.com/2020/10/72cb9-iu.jpg" alt=""/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>6.Connected Graph:</strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>Two vertices V<sub>i</sub> and V<sub>j</sub> are said to be connected if there is a path in G from V<sub>i</sub> to V<sub>j</sub>.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>1.<strong><em>Strongly Connected Graph</em></strong><em>: </em>A directed graph G is said to be strongly connected if for every pair of distinct vertices V<sub>i</sub>, V<sub>j</sub>, there is a directed path from V<sub>i</sub> to V<sub>j</sub> and also from<br>V<sub>j</sub> to V<sub>i</sub>.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>2.<strong><em>Weakly Connected Graph</em></strong> : A directed graph G is said to be weakly connected there exists at least one set of distinct vertices V<sub>i</sub>, V<sub>j</sub>, such that there is a directed path from V<sub>i</sub> to V<sub>j</sub> but no path&nbsp; from V<sub>j</sub> to V<sub>i</sub>.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:image {"width":421,"height":257,"sizeSlug":"large"} -->
<figure class="wp-block-image size-large is-resized"><img src="https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Fmichaellevet.files.wordpress.com%2F2015%2F01%2Fconnected_graphs.jpg%3Fw%3D604&amp;f=1&amp;nofb=1" alt="" width="421" height="257"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>7.Subgraph:</strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>A subgraph of G is a graph G ′such that&nbsp;, V(G′) ⊆ V(G) and E(G′) ⊆ E(G)</p>
<!-- /wp:paragraph -->

<!-- wp:image {"sizeSlug":"large"} -->
<figure class="wp-block-image size-large"><img src="https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Fimage.slidesharecdn.com%2Fvignan-130911102520-phpapp01%2F95%2Fgraph-theory-21-638.jpg%3Fcb%3D1378895377&amp;f=1&amp;nofb=1" alt=""/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>8.Weighted Graph or Network: </strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>A number (weight) may be associated with each edge of a graph.&nbsp; Such a graph is called a weighted graph or a network.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><strong><em>Example&nbsp; </em></strong>The number may represent the distance, cost, etc.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:image {"sizeSlug":"large"} -->
<figure class="wp-block-image size-large"><img src="https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Fi1.wp.com%2Falgorithms.tutorialhorizon.com%2Ffiles%2F2018%2F03%2FWeighted-Graph.png%3Fssl%3D1&amp;f=1&amp;nofb=1" alt=""/></figure>
<!-- /wp:image -->

<!-- wp:heading {"textAlign":"center"} -->
<h2 class="has-text-align-center"><strong><em>Ways to Represent graphs:</em></strong></h2>
<!-- /wp:heading -->

<!-- wp:image {"id":3223,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large"><img src="https://programmerprodigycode.files.wordpress.com/2020/12/image-48.png?w=642" alt="" class="wp-image-3223"/></figure>
<!-- /wp:image -->

<!-- wp:heading {"level":4} -->
<h4>A.Edge List:</h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>To list an edge, we have an array of two vertex numbers containing the vertex numbers of the vertices that the edges are incident on.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><strong>Consider the following graph example,</strong></p>
<!-- /wp:paragraph -->

<!-- wp:image {"align":"center","id":3229,"sizeSlug":"large","linkDestination":"none"} -->
<div class="wp-block-image"><figure class="aligncenter size-large"><img src="https://programmerprodigycode.files.wordpress.com/2020/12/image-51.png?w=325" alt="" class="wp-image-3229"/></figure></div>
<!-- /wp:image -->

<!-- wp:heading {"level":4} -->
<h4><strong><em>B. Adjacency Matrix:</em></strong></h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>The adjacency matrix A of a graph G is a two dimensional array of n × n elements where n is the numbers of vertices.&nbsp; The entries of A are defined as&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>A[i][j]&nbsp;&nbsp;&nbsp; = 1, if there exist an edge between vertices i and j in G.</li><li>A[i][j]&nbsp;&nbsp;&nbsp; = 0, if no edge exists between i and j.&nbsp;</li></ol>
<!-- /wp:list -->

<!-- wp:list -->
<ul><li><strong>Undirected graph</strong>: The degree of vertex i is the number of 1’s in its row (or the sum of row i )</li></ul>
<!-- /wp:list -->

<!-- wp:image {"width":598,"height":341,"sizeSlug":"large"} -->
<figure class="wp-block-image size-large is-resized"><img src="http://programmerprodigycode.files.wordpress.com/2020/10/18991-iu.jpg" alt="" width="598" height="341"/></figure>
<!-- /wp:image -->

<!-- wp:list -->
<ul><li><strong>Directed graph</strong><ol><li>(Indegree)<em>&nbsp;&nbsp;&nbsp; : </em>Total number of 1’s in column i.</li><li>(Outdegree) : Number of 1’s in row i.</li></ol></li></ul>
<!-- /wp:list -->

<!-- wp:image {"width":620,"height":353,"sizeSlug":"large"} -->
<figure class="wp-block-image size-large is-resized"><img src="http://programmerprodigycode.files.wordpress.com/2020/10/dd96e-iu.jpg" alt="" width="620" height="353"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>Code to implement Adjacency Matrix,</strong></p>
<!-- /wp:paragraph -->

<!-- wp:syntaxhighlighter/code {"language":"cpp"} -->
<pre class="wp-block-syntaxhighlighter-code">#include &lt;iostream>
#include &lt;cstdlib>

using namespace std;

class Graph
{
protected:
    int value;
    int **graphm;

public:
    Graph(int value)
    {
        this->value = value;
        graphm = new int*[value];
        int k, j;
        for (k = 0; k &lt; value; k++)
        {
            graphm[k] = new int[value];
            for (j = 0; j &lt; value; j++)
            {
                graphm[k][j] = 0;
            }
        }
    }

    void newEdge(int head, int end)
    {
        if (head > value || end > value || head &lt; 0 || end &lt; 0)
        {
            cout &lt;&lt; "Invalid edge!\n";
        }
        else
        {
            graphm[head - 1][end - 1] = 1;
            graphm[end - 1][head - 1] = 1;
        }
    }

    void display()
    {
        int i, p;

        for (i = 0; i &lt; value; i++)
        {
            cout&lt;&lt;i+1&lt;&lt;"Row: \t";
            for (p = 0; p &lt; value; p++)
            {
                cout &lt;&lt;p+1&lt;&lt;"Column:" &lt;&lt; graphm[i][p] &lt;&lt; "   ";
            }
            cout &lt;&lt; endl;
        }
    }

};

int main()
{
    int vertex, numberOfEdges, i, head, end;
    cout &lt;&lt; "Enter number of nodes: ";
    cin >> vertex;
    numberOfEdges = vertex * (vertex - 1);
    Graph g1(vertex);
    for (int i = 0; i &lt; numberOfEdges; i++)
    {
        cout &lt;&lt; "Enter edge ex.1 2 (-1 -1 to exit): \n";
        cin >> head >> end;
        if ((head == -1) &amp;&amp; (end == -1))
        {
            break;
        }
        g1.newEdge(head, end);
    }
    cout&lt;&lt;"\n";
    g1.display();
    cout &lt;&lt; endl;
    return 0;
}</pre>
<!-- /wp:syntaxhighlighter/code -->

<!-- wp:paragraph -->
<p><strong>Consider the following graph example,</strong></p>
<!-- /wp:paragraph -->

<!-- wp:image {"align":"center","id":3226,"width":261,"height":224,"sizeSlug":"large","linkDestination":"none"} -->
<div class="wp-block-image"><figure class="aligncenter size-large is-resized"><img src="https://programmerprodigycode.files.wordpress.com/2020/12/image-50.png?w=282" alt="" class="wp-image-3226" width="261" height="224"/></figure></div>
<!-- /wp:image -->

<!-- wp:image {"id":3231,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large"><img src="https://programmerprodigycode.files.wordpress.com/2020/12/image-52.png?w=720" alt="" class="wp-image-3231"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph {"align":"center"} -->
<p class="has-text-align-center"><strong>It uses arrays and hence is memory inefficient.&nbsp;</strong></p>
<!-- /wp:paragraph -->

<!-- wp:heading {"level":4} -->
<h4><strong><em>C.ADJACENCY LIST</em></strong>:</h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p id="3791">An adjacency list represents a graph as an array of linked lists.</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p id="0f16">The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex.</p>
<!-- /wp:paragraph -->

<!-- wp:image {"sizeSlug":"large"} -->
<figure class="wp-block-image size-large"><img src="http://programmerprodigycode.files.wordpress.com/2020/10/58cb6-iu.jpg" alt=""/></figure>
<!-- /wp:image -->

<!-- wp:list {"ordered":true} -->
<ol><li>From the adjacency list we can calculate the outdegree of any vertex i. The total number of nodes in list ‘i’ is its outdegree.&nbsp;</li><li>To obtain the indegree, we can construct an inverse adjacency list. The inverse adjacency list.&nbsp;</li></ol>
<!-- /wp:list -->

<!-- wp:syntaxhighlighter/code -->
<pre class="wp-block-syntaxhighlighter-code">#include &lt;iostream>
#include &lt;cstdlib>
#include &lt;list>
#include &lt;vector>

using namespace std;

int main()
{
	int vertices, edges, v1, v2, weight;
	
	cout&lt;&lt;"Enter the Number of Vertices -\n";
    cin>>vertices;
	
    edges = vertices * (vertices - 1);

	vector&lt; list&lt; pair&lt;int, int> > > adjacencyList(vertices + 1);
	
    cout &lt;&lt;"Enter edges ex.V1 V2 W (-1 -1 -1 to exit): \n";

	
	for (int i = 0; i &lt; edges; ++i) {
        cin>>v1>>v2>>weight;
        if ((v1 == -1) &amp;&amp; (v2 == -1) &amp;&amp; (weight ==-1))
        {
            break;
        }
		// Adding Edges to the Graph
		adjacencyList[v1].push_back(make_pair(v2, weight));
		adjacencyList[v2].push_back(make_pair(v1, weight));
	}
	
	cout&lt;&lt;"\nThe Adjacency List-\n";
	// Printing Adjacency List
	for (int i = 1; i &lt; adjacencyList.size(); ++i) {
        cout&lt;&lt;"AdjacencyList at "&lt;&lt; i&lt;&lt;"\t";
		
		list&lt; pair&lt;int, int> >::iterator itr = adjacencyList[i].begin();
		
		while (itr != adjacencyList[i].end()) {
			cout&lt;&lt;" -> "&lt;&lt;(*itr).first&lt;&lt;"("&lt;&lt;(*itr).second&lt;&lt;")";
			++itr;
		}
		cout&lt;&lt;"\n";
	}
	
	return 0;
}</pre>
<!-- /wp:syntaxhighlighter/code -->

<!-- wp:paragraph -->
<p><strong>Let us consider this example,</strong></p>
<!-- /wp:paragraph -->

<!-- wp:image {"id":3232,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large"><img src="https://programmerprodigycode.files.wordpress.com/2020/12/image-53.png?w=635" alt="" class="wp-image-3232"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>For more information,</strong></p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li><a rel="noreferrer noopener" href="https://runestone.academy/runestone/books/published/cppds/Graphs/AnAdjacencyMatrix.html" target="_blank">https://runestone.academy/runestone/books/published/cppds/Graphs/AnAdjacencyMatrix.html</a></li><li><a href="https://medium.com/the-programming-club-iit-indore/graphs-and-trees-using-c-stl-322e5779eef9" target="_blank" rel="noreferrer noopener">https://medium.com/the-programming-club-iit-indore/graphs-and-trees-using-c-stl-322e5779eef9</a></li></ol>
<!-- /wp:list -->

<!-- wp:heading {"textAlign":"center"} -->
<h2 class="has-text-align-center"><strong>GRAPH TRAVERSALS</strong>:</h2>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p><strong><em>1.DEPTH FIRST SEARCH:</em></strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>Starting from vertex ‘v’, we follow a path in the graph as deeply as we can go marking the vertices in the path as ‘visited’.&nbsp; When there are no adjacent vertices that are not visited, we proceed backwards (back track) to a vertex in the path which has an ‘unvisited’ adjacent vertex and proceed from this vertex.&nbsp; The process continues till all vertices have been visited.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:image {"sizeSlug":"large"} -->
<figure class="wp-block-image size-large"><img src="https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Fhe-s3.s3.amazonaws.com%2Fmedia%2Fuploads%2F4b2bba0.jpg&amp;f=1&amp;nofb=1" alt=""/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>Algorithm: Depth-first search (Graph G, Souce_Vertex S)</strong></p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>Create a stack <strong>STK</strong> to store the vertices.</li><li>Push the source vertex <strong>S</strong> in the stack ‘STK’.</li><li>While the stack <strong>STK</strong> is not empty</li><li>Pop the vertex <strong>U</strong> from the top of the stack. i.e Vertex <strong>U</strong> = STK.top(), STK.pop()</li><li>If the vertex <strong>U</strong> is not visited</li><li>Explore the vertex <strong>U</strong> and mark <strong>U</strong> as visited.</li><li>For every vertex <strong>V</strong> adjacent to vertex <strong>U</strong></li><li>Push the vertex <strong>V</strong> in the stack STK</li></ol>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p>The function for implementing it would be,</p>
<!-- /wp:paragraph -->

<!-- wp:syntaxhighlighter/code -->
<pre class="wp-block-syntaxhighlighter-code">void Graph::depth_first_search(int start_vertex){

    int current_v = start_vertex;
    this->discovered[current_v] = true;
    EdgeNode *p = this->edges[current_v];
    process_vertex_early(current_v);

    while(p != NULL){
        int neighbor_v = p->key;
        if(!this->discovered[neighbor_v]){
            //this->discovered[neighbor_v] = true;
            this->parent[neighbor_v] = current_v;
            process_edge(current_v, neighbor_v);
            depth_first_search(neighbor_v);
        }
        //2nd case is needed because 1st case isn't enough to visit all edges (because 1st case sets all neighbors
        //to discovered which excludes some visits to edges later)
        else if(((!this->processed[neighbor_v]) &amp;&amp; (this->parent[current_v] != neighbor_v)) || (this->directed)){
            process_edge(current_v, neighbor_v);
        }
        p = p->next;
    }
    this->processed[current_v] = true;
}
</pre>
<!-- /wp:syntaxhighlighter/code -->

<!-- wp:image {"id":2335,"width":594,"height":446,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large is-resized"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/image-5.png?w=538" alt="" class="wp-image-2335" width="594" height="446"/><figcaption><strong><em>DFS of this graph is&nbsp; V<sub>1</sub> V<sub>2</sub> V<sub>5</sub> V<sub>3</sub> V<sub>6</sub> V<sub>4</sub></em></strong></figcaption></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>We can implement DFS using various other data structures for storing graph and for searching in it.</strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><strong>Applications of DFS:</strong></p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>Minimum Spanning Tree</li><li>Topological sorting</li><li>To solve puzzle/maze which has one solution</li></ol>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p><strong>For more information,</strong></p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li><a rel="noreferrer noopener" href="https://brilliant.org/wiki/depth-first-search-dfs/" target="_blank">https://brilliant.org/wiki/depth-first-search-dfs/</a></li><li><a href="https://algotree.org/algorithms/tree_graph_traversal/depth_first_search/" target="_blank" rel="noreferrer noopener">https://algotree.org/algorithms/tree_graph_traversal/depth_first_search/</a></li></ol>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p><strong><em>2.BREADTH FIRST SEARCH:</em></strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>BFS is an algorithm for traversing an unweighted Graph or a Tree. BFS starts with the root node and explores each adjacent node before exploring node(s) at the next level.<br>BFS makes use of the adjacency list data structure to explore the nodes adjacent to the visited (current) node.</p>
<!-- /wp:paragraph -->

<!-- wp:image {"sizeSlug":"large"} -->
<figure class="wp-block-image size-large"><img src="https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Fimage.slidesharecdn.com%2Funiformedtreesearching-131220150928-phpapp01%2F95%2Funiformed-tree-searching-12-638.jpg%3Fcb%3D1387552768&amp;f=1&amp;nofb=1" alt=""/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>Algorithm: Breadth-first search (Graph G, Souce_Vertex S)</strong></p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>Create a queue <strong>Q</strong> to store the vertices.</li><li>Push the source vertex <strong>S</strong> in the queue <strong>Q</strong>.</li><li>Mark <strong>S</strong> as visited.</li><li>While the queue <strong>Q</strong> is not empty</li><li>Remove vertex <strong>U</strong> from the front of the queue. i.e Vertex <strong>U</strong> = <strong>Q</strong>.front(), <strong>Q</strong>.pop()</li><li>For every vertex <strong>V</strong> adjacent to the vertex <strong>U</strong></li><li>If the vertex <strong>V</strong> is not visited</li><li>Explore the vertex <strong>V</strong> and mark <strong>V</strong> as visited.</li><li>Push the vertex <strong>V</strong> in the queue <strong>Q</strong>.</li></ol>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p>The function for implementing it would be,</p>
<!-- /wp:paragraph -->

<!-- wp:syntaxhighlighter/code -->
<pre class="wp-block-syntaxhighlighter-code">void Graph::breadth_first_search(int start_vertex){

    initialize_search();
    queue&lt;int> q;//queue of vertices still left to visit
    int current_v;  //current vertex
    EdgeNode *p; //temporary pointer

    q.push(start_vertex);
    this->discovered[start_vertex] = true;

    while(!q.empty()){
        current_v = q.front();
        q.pop();
        process_vertex_early(current_v);
        p = this->edges[current_v];
        while(p != NULL){
            int neighbor_v = p->key;
            if(!this->discovered[neighbor_v]){
                //add to Q and set to discovered
                q.push(neighbor_v);
                this->discovered[neighbor_v] = true;
                this->parent[neighbor_v] = current_v;
            }
            if(!this->processed[neighbor_v] || this->directed){
                process_edge(current_v, neighbor_v);
            }
            p = p->next;
        }
        this->processed[current_v] = true;
    }
    initialize_search();
}
</pre>
<!-- /wp:syntaxhighlighter/code -->

<!-- wp:image {"id":2337,"width":609,"height":486,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large is-resized"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/image-6.png?w=509" alt="" class="wp-image-2337" width="609" height="486"/><figcaption><strong><em>BFS of this graph is&nbsp; V<sub>1</sub> V<sub>2</sub> V<sub>3</sub> V<sub>4</sub> V<sub>5</sub> V<sub>6</sub></em></strong></figcaption></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>We can implement BFS using various other data structures for storing graph and for searching in it.</strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><strong>Application of BFS :</strong></p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>Minimum Spanning Tree or shortest path</li><li>Peer to peer networking</li><li>Crawler for search engine</li><li>Social network websites - to find people with a given distance k from a person using BFS till k levels.</li></ol>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p><strong>For more information,</strong></p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li><a rel="noreferrer noopener" href="https://algotree.org/algorithms/tree_graph_traversal/breadth_first_search/" target="_blank">https://algotree.org/algorithms/tree_graph_traversal/breadth_first_search/</a></li><li><a href="https://brilliant.org/wiki/breadth-first-search-bfs/" target="_blank" rel="noreferrer noopener">https://brilliant.org/wiki/breadth-first-search-bfs/</a></li></ol>
<!-- /wp:list -->

<!-- wp:paragraph {"align":"center"} -->
<p class="has-text-align-center"><strong> Difference between DFS and BFS</strong></p>
<!-- /wp:paragraph -->

<!-- wp:image {"sizeSlug":"large"} -->
<figure class="wp-block-image size-large"><img src="http://programmerprodigycode.files.wordpress.com/2020/10/c56ec-iu.jpg" alt=""/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>For more information,</strong></p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li><a rel="noreferrer noopener" href="https://stackoverflow.com/questions/687731/breadth-first-vs-depth-first" target="_blank">https://stackoverflow.com/questions/687731/breadth-first-vs-depth-first</a></li><li><a href="https://visualgo.net/en/mst?slide=1" target="_blank" rel="noreferrer noopener">https://visualgo.net/en/mst?slide=1</a></li></ol>
<!-- /wp:list -->

<!-- wp:nextpage -->
<!--nextpage-->
<!-- /wp:nextpage -->

<!-- wp:heading {"textAlign":"center"} -->
<h2 class="has-text-align-center"><strong><em>SPANNING TREE</em></strong>:</h2>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>If G is a graph containing n vertices, then the minimum number of edges needed to connect the n vertices = n-1.&nbsp; All connected graphs with n-1 edges are trees. These are called spanning trees.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><strong>Definition of Spanning Tree</strong>: Let G = (V, E) be an undirected connected graph. A subgraph t = (V, E′) of G is a spanning tree of G iff&nbsp; t is a tree.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>A <strong>minimum spanning tree</strong> is a spanning tree with the lowest number of edges.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:image {"sizeSlug":"large","className":"is-style-default"} -->
<figure class="wp-block-image size-large is-style-default"><img src="https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Fimage.slidesharecdn.com%2Fvignan-130911102520-phpapp01%2F95%2Fgraph-theory-45-638.jpg%3Fcb%3D1378895377&amp;f=1&amp;nofb=1" alt=""/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>MINIMUM COST SPANNING TREE:</strong> The spanning tree having the minimum sum of weights of edges is called minimum cost spanning tree.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>These weights may represent the lengths, distances, cost, etc.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>Such trees are widely used in practical applications such as network of road lines between cities, etc.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:image {"sizeSlug":"large"} -->
<figure class="wp-block-image size-large"><img src="https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Fimage.slidesharecdn.com%2Fvignan-130911102520-phpapp01%2F95%2Fgraph-theory-47-638.jpg%3Fcb%3D1378895377&amp;f=1&amp;nofb=1" alt=""/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>For example.</strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph {"align":"center"} -->
<p class="has-text-align-center"><img src="https://lh3.googleusercontent.com/bUDccv3WoIeEZUUUQTznI3X6UvDzSQgROoI1wKyuo-bJY8rWLl-7z8zlVSfdqNUlAOUjuoUmGX0l5lNBzwRSmudouO9z6QX6toJ1WKidumN_6VecmJD3yok3GdYXPVgYoe0VXHF2" width="405" height="309"></p>
<!-- /wp:paragraph -->

<!-- wp:heading {"textAlign":"center"} -->
<h2 class="has-text-align-center"><strong><em>Algorithms to find minimum spanning tree</em></strong>:</h2>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p><em><strong>1. PRIM’S ALGORITHM</strong>:</em></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>A few key points to remember about Prim algorithm,</p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>Prim’s algorithm&nbsp;is a&nbsp;<strong>greedy</strong> algorithm.</li><li>It finds a&nbsp;minimum spanning tree&nbsp;for a&nbsp;weighted <strong>undirected</strong> graph.</li><li>This means it finds a<strong> subset of the&nbsp;edges&nbsp;that forms a&nbsp;tree&nbsp;that includes every&nbsp;vertex, where the total weight of all the&nbsp;edges&nbsp;in the tree is minimized</strong>.</li><li>The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.</li></ol>
<!-- /wp:list -->

<!-- wp:image {"sizeSlug":"large"} -->
<figure class="wp-block-image size-large"><img src="https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Fi.stack.imgur.com%2FKofyW.gif&amp;f=1&amp;nofb=1" alt=""/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>Let's consider this graph, </strong></p>
<!-- /wp:paragraph -->

<!-- wp:image {"id":2341,"width":551,"height":416,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large is-resized"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/image-7.png?w=446" alt="" class="wp-image-2341" width="551" height="416"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>All the steps to find Minimum spanning tree using prim's  algorithm, </strong></p>
<!-- /wp:paragraph -->

<!-- wp:image {"id":2342,"width":696,"height":588,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large is-resized"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/image-8.png?w=698" alt="" class="wp-image-2342" width="696" height="588"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>The end result of minimum spanning tree should look like,</strong></p>
<!-- /wp:paragraph -->

<!-- wp:image {"id":2344,"width":437,"height":343,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large is-resized"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/image-9.png?w=353" alt="" class="wp-image-2344" width="437" height="343"/></figure>
<!-- /wp:image -->

<!-- wp:syntaxhighlighter/code {"language":"cpp"} -->
<pre class="wp-block-syntaxhighlighter-code">void find_MST(int V)  
    {  
        int parent[V], key[V];
        bool visited[V];

        // Initialize all the arrays 
        for (int i = 0; i&lt; V; i++) { 
            key[i] = 999;    // 99 represents an Infinite value
            visited[i] = false;
            parent[i]=-1;
        }    

        key[0] = 0;  // Include first vertex in MST by setting its key vaue to 0.  
        parent[0] = -1; // First node is always root of MST  

        // The MST will have maximum V-1 vertices  
        for (int x = 0; x &lt; V - 1; x++) 
        {  
            // Finding the minimum key vertex from the 
            //set of vertices not yet included in MST  
            int u = min_Key(key, visited,V);  

            visited[u] = true;  // Add the minimum key vertex to the MST  

            // Update key and parent arrays
            for (int v = 0; v &lt; V; v++)  
            {
                // cost[u][v] is non zero only for adjacent vertices of u  
                // visited[v] is false for vertices not yet included in MST  
                // key[] gets updated only if cost[u][v] is smaller than key[v]  
                if (cost[u][v]!=0 &amp;&amp; visited[v] == false &amp;&amp; cost[u][v] &lt; key[v])
                {  
                    parent[v] = u;
                    key[v] = cost[u][v];  
                }        
            }
        }

        // print the final MST  
    	print_MST(parent,V);  
    }  
</pre>
<!-- /wp:syntaxhighlighter/code -->

<!-- wp:paragraph -->
<p><strong><em>2.KRUSKAL’S ALGORITHM</em></strong>:</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>A few key points to remember about Kruskal algorithm,</p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>Kruskal’s algorithm for finding t<strong>he Minimum Spanning Tree(MST), which finds an edge of the least possible weight that connects any two trees in the forest</strong></li><li>It is a&nbsp;<strong>greedy</strong> algorithm.</li><li>It<strong> finds a subset of the&nbsp;edges&nbsp;that forms a tree that includes every&nbsp;vertex</strong>, where the total weight of all the edges in the tree is minimized.</li><li>If the graph is not connected, then it finds a&nbsp;minimum spanning forest&nbsp;(a minimum spanning tree for each&nbsp;connected component).</li><li>Number of edges in MST: V-1 (V – no of vertices in Graph).</li></ol>
<!-- /wp:list -->

<!-- wp:image {"sizeSlug":"large"} -->
<figure class="wp-block-image size-large"><img src="https://external-content.duckduckgo.com/iu/?u=http%3A%2F%2Fwww.thestudentroom.co.uk%2Fattachment.php%3Fattachmentid%3D23571%26stc%3D1%26d%3D1148396387&amp;f=1&amp;nofb=1" alt=""/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>Let's consider this graph,</strong></p>
<!-- /wp:paragraph -->

<!-- wp:image {"id":2349,"width":389,"height":312,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large is-resized"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/image-11.png?w=355" alt="" class="wp-image-2349" width="389" height="312"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>All the steps to find Minimum spanning tree using kruskal's algorithm,</strong></p>
<!-- /wp:paragraph -->

<!-- wp:image {"id":2348,"width":565,"height":422,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large is-resized"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/image-10.png?w=517" alt="" class="wp-image-2348" width="565" height="422"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>The end result of minimum spanning tree should look like,</strong></p>
<!-- /wp:paragraph -->

<!-- wp:image {"id":2351,"width":414,"height":331,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large is-resized"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/image-12.png?w=335" alt="" class="wp-image-2351" width="414" height="331"/></figure>
<!-- /wp:image -->

<!-- wp:syntaxhighlighter/code -->
<pre class="wp-block-syntaxhighlighter-code">void kruskalMST(int V) 
    { 
    	int mincost = 0; // Cost of min MST. 

    	// Initialize sets of disjoint sets. 
    	for (int i = 0; i &lt; V; i++) 
    		parent[i] = i; 

    	// Include minimum weight edges one by one 
    	int edge_count = 0; 
    	while (edge_count &lt; V - 1) { 
    		int min = __INT_MAX__, a = -1, b = -1; 
    		for (int i = 0; i &lt; V; i++) { 
    			for (int j = 0; j &lt; V; j++) { 
    				if (find(i) != find(j) &amp;&amp; cost[i][j] &lt; min) { 
    					min = cost[i][j]; 
    					a = i; 
    					b = j; 
    				} 
    			} 
    		} 

    		union1(a, b); 
    		// printf("Edge %d:(%d, %d) cost:%d \n",edge_count++, a, b, min); 
            cout&lt;&lt;"Edge"&lt;&lt;edge_count++&lt;&lt;"("&lt;&lt;a&lt;&lt;","&lt;&lt;b&lt;&lt;")"&lt;&lt;"\t cost:"&lt;&lt;min&lt;&lt;"\n";
    		mincost += min; 
    	} 
    	cout&lt;&lt;"\n Minimum cost="&lt;&lt;mincost&lt;&lt;"\n"; 
    } 
</pre>
<!-- /wp:syntaxhighlighter/code -->

<!-- wp:paragraph {"align":"center"} -->
<p class="has-text-align-center"><strong>Difference between Kruskal's and Prim's Algorithm </strong></p>
<!-- /wp:paragraph -->

<!-- wp:image {"align":"left","id":2355,"width":885,"height":350,"sizeSlug":"large","linkDestination":"none"} -->
<div class="wp-block-image"><figure class="alignleft size-large is-resized"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/image-13.png?w=768" alt="" class="wp-image-2355" width="885" height="350"/></figure></div>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong><em>Applications of finding minimum spanning tree:</em></strong></p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>Network design</li><li>Traveling salesman problem</li></ol>
<!-- /wp:list -->

<!-- wp:nextpage -->
<!--nextpage-->
<!-- /wp:nextpage -->

<!-- wp:heading {"textAlign":"center","level":3} -->
<h3 class="has-text-align-center"><em>SHORTEST PATH</em></h3>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p><em>A person wishing to travel from city A to city B could require the following information.&nbsp;&nbsp;</em></p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>Is there a path from A to B?</li><li>If there is more than one path from A to B, which is the shortest?</li></ol>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p><strong>DIJKSTRA IS A “SINGLE SOURCE ALL DESTINATIONS” ALGORITHM</strong></p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>Dijkstra’s algorithm finds the shortest path in a <strong>weighted graph</strong> containing only positive edge weights from a single source. </li><li>It uses a priority based dictionary or a queue to select a node / vertex nearest to the source that has not been edge relaxed.</li><li>Since Dijkstra’s algorithm cannot handle negative edge weights, <a href="https://algotree.org/algorithms/single_source_shortest_path/bellman_ford_shortest_path/"><strong>Bellman-Ford</strong></a> algorithm is used for finding the shortest path in a graph containing negative edge weights</li></ol>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p><strong>Algorithm: Dijkstra’s Shortest Path&nbsp;</strong></p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>Start with the empty Shortest Path Tree (SPT).</li><li>Maintain a set SPT[] to keep track to vertices included in SPT.</li><li>Assign a distance value to all the vertices, (say distance []) and initialize all the distances with +∞ (Infinity) except the source vertex. This will be used to keep track of the distance of vertices from the source vertex. The distance of source vertex to source vertex will be 0.</li><li>Repeat the following steps until all vertices are processed.<ol><li>Pick the vertex <strong><em>u</em></strong> which is not in <strong><em>SPT[]</em></strong> and has minimum distance. Here we will loop through the vertices and find the vertex with minimum distance.</li><li>Add vertex <strong><em>u</em></strong> to <strong><em>SPT[].</em></strong></li><li>Loop over all the adjacent vertices </li><li>For adjacent vertex v, if v is not in SPT[] and distance[v] &gt; distance[u] + edge u-v<strong><em> weight </em></strong>then update <strong><em>distance[v] = distance[u] + edge u-v weight</em></strong></li></ol></li></ol>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p>Let's consider the graph,</p>
<!-- /wp:paragraph -->

<!-- wp:image {"id":2358,"width":620,"height":287,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large is-resized"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/image-14.png?w=534" alt="" class="wp-image-2358" width="620" height="287"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p>Then Dijkstra algorithm using a matrix results,</p>
<!-- /wp:paragraph -->

<!-- wp:image {"id":2360,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/image-15.png?w=852" alt="" class="wp-image-2360"/></figure>
<!-- /wp:image -->

<!-- wp:syntaxhighlighter/code -->
<pre class="wp-block-syntaxhighlighter-code">void dijkstra(int graph[10][10], int src, int V) 
{ 
	int dist[V];
	bool sptSet[V]; 
	for (int i = 0; i &lt; V; i++) 
		dist[i] = INT_MAX, sptSet[i] = false; 
	dist[src] = 0; 
	for (int count = 0; count &lt; V-1; count++) 
	{ 
	int u = minDistance(dist, sptSet, V); 
	sptSet[u] = true;  
	for (int v = 0; v &lt; V; v++) 
		if (!sptSet[v] &amp;&amp; graph[u][v] &amp;&amp; dist[u] != INT_MAX 
									&amp;&amp; dist[u]+graph[u][v] &lt; dist[v]) 
			dist[v] = dist[u] + graph[u][v]; 
	} 
	printSolution(dist, V); 
} </pre>
<!-- /wp:syntaxhighlighter/code -->

<!-- wp:heading {"level":5} -->
<h5>2.Limitation of Dijkstra algorithm:</h5>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p id="block-a939e9b1-3f42-4a37-b2e1-a65c2eb15d6b">Dijkstra’s algorithm relies on the fact that the shortest path from s to t goes only through vertices that are closer to s. This is no longer the case for graphs with negative edges, One of the use cases of this is currency cycle with a negative cycle.</p>
<!-- /wp:paragraph -->

<!-- wp:image {"align":"center","id":3220,"sizeSlug":"large","linkDestination":"none"} -->
<div class="wp-block-image"><figure class="aligncenter size-large"><img src="https://programmerprodigycode.files.wordpress.com/2020/12/image-47.png?w=157" alt="" class="wp-image-3220"/></figure></div>
<!-- /wp:image -->

<!-- wp:heading {"level":4} -->
<h4>3.Bellman-Ford Algorithm:</h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>Bellman-Ford algorithm finds the shortest path (in terms of distance/cost) from a single source in a directed, weighted graph containing positive and negative edge weights.</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>Algorithm for Bellman Ford,</p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>Initialize the distance from the source node S to all other nodes as infinite (999999999) and to itself as 0.</li><li>For every node in the graph do</li><li>For every edge E in the EdgeList do</li><li>Node_u = E.first, Node_v = E.second</li><li>Weight_u_v = EdgeWeight ( Node_u, Node_v )</li><li>If ( Distance [v] &gt; Distance [u] + Weight_u_v )</li><li>Distance [v] = Distance [u] + Weight_u_v</li></ol>
<!-- /wp:list -->

<!-- wp:image {"sizeSlug":"large"} -->
<figure class="wp-block-image size-large"><img src="https://external-content.duckduckgo.com/iu/?u=http%3A%2F%2Fpeople.inf.elte.hu%2Fhytruongson%2FBellman-Ford%2F10-bellmanford.jpg&amp;f=1&amp;nofb=1" alt=""/></figure>
<!-- /wp:image -->

<!-- wp:paragraph {"align":"center"} -->
<p class="has-text-align-center"><strong>In a graph with only positive edge weights, Dijkstra’s algorithm with a priority queue / set implementation runs faster in O ((E+V) log V) than Bellman-Ford O (E.V).</strong></p>
<!-- /wp:paragraph -->

<!-- wp:heading {"level":5} -->
<h5><br></h5>
<!-- /wp:heading -->

<!-- wp:heading {"textAlign":"center","level":3} -->
<h3 class="has-text-align-center"><em>TOPOLOGICAL SORT</em>:</h3>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p><strong><em>AOV network:</em></strong><em>&nbsp;&nbsp;&nbsp; </em>A directed graph in which the vertices represent activities or tasks and the edges represent the precedence is called an AOV network. There should be no cycles in an AOV network i.e there should be atleast one activity which does not have a predecessor(start activity).&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><strong>Topological sort: </strong>If we have an AOV network, then we would like to find out whether the project is feasible or not and if it is feasible, then in what order should the activities be performed so that the project can be completed<strong>. The process of converting a set of precedences represented by an AOV network into a linear list in which no later activity precedes an earlier one is called Topological Sorting. </strong>This method identifies the order of the activities.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:image {"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large"><img src="https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Fi.imgur.com%2FQ3MA6dZ.png&amp;f=1&amp;nofb=1" alt=""/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>Let us consider this graph,</strong></p>
<!-- /wp:paragraph -->

<!-- wp:image {"id":2366,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/image-17.png?w=569" alt="" class="wp-image-2366"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>All the steps to perform for topological sort,</strong></p>
<!-- /wp:paragraph -->

<!-- wp:image {"id":2369,"sizeSlug":"large","linkDestination":"none"} -->
<figure class="wp-block-image size-large"><img src="https://programmerprodigycode.files.wordpress.com/2020/10/image-19.png?w=831" alt="" class="wp-image-2369"/></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p><strong>The topological order is :V<sub>1</sub>, V<sub>3</sub>, V<sub>2</sub>, V<sub>4</sub>, V<sub>5</sub></strong></p>
<!-- /wp:paragraph -->

<!-- wp:syntaxhighlighter/code -->
<pre class="wp-block-syntaxhighlighter-code">topologicalSort() 
{ 
	stack&lt;int> Stack; 

	// Mark all the vertices as not visited 
	bool* visited = new bool[V]; 
	for (int i = 0; i &lt; V; i++) 
		visited[i] = false; 

	// Call the recursive helper function to store Topological 
	// Sort starting from all vertices one by one 
	for (int i = 0; i &lt; V; i++) 
		if (visited[i] == false) 
			topologicalSortUtil(i, visited, Stack); 

	// Print contents of stack 
	while (Stack.empty() == false) { 
		cout &lt;&lt; Stack.top() &lt;&lt; " "; 
		Stack.pop(); 
	} 
} </pre>
<!-- /wp:syntaxhighlighter/code -->

<!-- wp:paragraph -->
<p><strong>Applications of Topological sort:</strong></p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>Scheduling jobs from given dependencies among Jobs. F</li><li>Instruction Scheduling</li><li>Determining the order of compilation tasks to perform in makefiles, data serializations and resolving symbol dependencies in linkers.</li></ol>
<!-- /wp:list -->

<!-- wp:heading {"level":3} -->
<h3><strong><em>References</em></strong></h3>
<!-- /wp:heading -->

<!-- wp:list {"ordered":true} -->
<ol><li><a href="https://cseweb.ucsd.edu/~dakane/">Research papers of Daniel Kane</a></li><li><a href="https://www.cs.princeton.edu/~rs/AlgsDS07/11UndirectedGraphs.pdf">Research papers from Princeton</a></li><li><a href="https://courses.cs.washington.edu/courses/cse326/03wi/">Research papers from the University of Washington</a></li><li>Reference from <a href="https://algotree.org/algorithms/">AlgoTree</a>, <a href="https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs">Khan Academy</a> and Stackoverflow</li><li><a href="https://github.com/kakabisht/Data-structures">GitHub repository</a> for code</li></ol>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p>GitHub repository for code, <a rel="noreferrer noopener" href="https://github.com/kakabisht/Data-structures" target="_blank">https://github.com/kakabisht/Data-structures</a></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph {"align":"center"} -->
<p class="has-text-align-center"><strong>I have used a lot of images from a lot of sources, and i don't own images used. I just found them online, and used them to explain concepts. As, images are far better for understanding concepts.</strong></p>
<!-- /wp:paragraph -->