EX.

NO:8 GRAPHS

10.02.21

AIM:

To understand the concept of graphs

1. To implement topological sort

PROGRAM:

#include <iostream>

#include <list>

#include <stack>

using namespace std;

class Graph {

int V;

list<int>* adj;

void topologicalSortUtil(int v, bool visited[], stack<int>& Stack);

public:

Graph(int V);

void addEdge(int v, int w);

void topologicalSort();

};

Graph::Graph(int V)

this->V = V;

adj = new list<int>[V];

void Graph::addEdge(int v, int w)

adj[v].push_back(w);

T.PRABAVATHI(MTECH)
20MA32
}

void Graph::topologicalSortUtil(int v, bool visited[], stack<int>& Stack)

visited[v] = true;

list<int>::iterator i;

for (i = adj[v].begin(); i != adj[v].end(); ++i)

if (!visited[*i])

topologicalSortUtil(*i, visited, Stack);

Stack.push(v);

void Graph::topologicalSort()

stack<int> Stack;

bool* visited = new bool[V];

for (int i = 0; i < V; i++)

visited[i] = false;

for (int i = 0; i < V; i++)

if (visited[i] == false)

topologicalSortUtil(i, visited, Stack);

while (Stack.empty() == false) {

cout << Stack.top() << " ";

Stack.pop();

int main()

T.PRABAVATHI(MTECH)
20MA32
 Graph g(6);

g.addEdge(5, 2);

g.addEdge(5, 0);

g.addEdge(4, 0);

g.addEdge(4, 1);

g.addEdge(2, 3);

g.addEdge(3, 1);

cout << "Following is a Topological Sort of the given graph n";

g.topologicalSort();

return 0;

2. To implement Dijkstra’s algorithm

#include <limits.h>

#include <stdio.h>

#define V 9

int minDistance(int dist[], bool sptSet[])

// Initialize min value

int min = INT_MAX, min_index;

T.PRABAVATHI(MTECH)
20MA32
 for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min)

min = dist[v], min_index = v;

return min_index;

// A utility function to print the constructed distance array

void printSolution(int dist[])

printf("Vertex \t\t Distance from Source\n");

for (int i = 0; i < V; i++)

printf("%d \t\t %d\n", i, dist[i]);

// Function that implements Dijkstra's single source shortest path algorithm

// for a graph represented using adjacency matrix representation

void dijkstra(int graph[V][V], int src)

int dist[V]; // The output array. dist[i] will hold the shortest

// distance from src to i

bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest

// path tree or shortest distance from src to i is finalized

// Initialize all distances as INFINITE and stpSet[] as false

T.PRABAVATHI(MTECH)
20MA32
for (int i = 0; i < V; i++)

dist[i] = INT_MAX, sptSet[i] = false;

// Distance of source vertex from itself is always 0

dist[src] = 0;

// Find shortest path for all vertices

for (int count = 0; count < V - 1; count++) {

// Pick the minimum distance vertex from the set of vertices not

// yet processed. u is always equal to src in the first iteration.

int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed

sptSet[u] = true;

// Update dist value of the adjacent vertices of the picked vertex.

for (int v = 0; v < V; v++)

// Update dist[v] only if is not in sptSet, there is an edge from

// u to v, and total weight of path from src to v through u is

// smaller than current value of dist[v]

if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX

&& dist[u] + graph[u][v] < dist[v])

dist[v] = dist[u] + graph[u][v];

// print the constructed distance array

T.PRABAVATHI(MTECH)
20MA32
 printSolution(dist);

// driver program to test above function

int main()

/* Let us create the example graph discussed above */

int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, { 0, 8, 0, 7,

dijkstra(graph, 0);

return 0;

T.PRABAVATHI(MTECH)
20MA32