/**********************************************************************/

/*Program: To show operations in graph*/

/*Purpose:Program to show breadth first search in graph*/

/*Date :05-01-2005*/

/*Time:12:40*/

/**********************************************************************/

#include

#include

#define SIZE 10

#define FALSE 0

#define TRUE 1

typedef int adj_mat[SIZE][SIZE];

int front=1,rear=1;

int q[SIZE];

typedef struct graph_t{

int nodes;

int *visited;

adj_mat mat;

}graph;

/**************Function Declaration Begin**********/

void BFS(graph *);

void add_queue(int[],int);

int delete_queue();

/**************Function Declaration End**********/

void main()

{

graph G;

clrscr();

printf(“\n\t\t Program shows Breath First Search in a graph”);

printf(“\n\t\t Enter number of nodes in the graph:”);

scanf(“%d”,&G.nodes);

BFS(&G);

getch();

}

/********** breadth first searching **********/

/********** Function Definition begins **********/

void BFS( graph *G )

{

int k,i,j;

for(k=1;k<=G->nodes;k++)

G->visited[k] = FALSE;

for(i=1;i<=G->nodes;i++)

{

for(j=1;j<=G->nodes;j++)

{

printf(“\n Enter data of vertex %d for(%d,%d):”,i,i,j);

printf(“\n Enter 1 for adjacent vertex and 0 otehrwise”);

scanf(“%d”,&G->mat[i][j]);

}

}

for(k=1;k<=G->nodes;k++)

{

if ( !G->visited[k] )

{

add_queue(q,k);

do

{

k= delete_queue(q);

G->visited[k] = TRUE;

for(j=1;j<=G->nodes;j++)

{

if(G->mat[k][j] == 0)

continue;

if (!G->visited[j])

{

G->visited[j] = TRUE;

add_queue(q, j);

}

}

}while(front!=rear);

}

}

printf(“\n Adjacency matrix of a graph is:\n”);

for(i=1;i<=G->nodes;i++)

{

for(k=1;k<=G->nodes;k++)

{

printf(“%d\t”,G->mat[i][k]);

}

printf(“\n”);

}

i=0;

printf(“\n Traversal of a given graph is\n”);

while(inodes)

{

printf(“%d\t”,q[++i]);

}

}

/********** Function Definition ends **********/

/********** inserting element in queue **********/

/********** Function Definition begins **********/

void enqueue(int q[], int k)

{

q[rear] = k;

rear++;

}

/********** Function Definition ends **********/

/********** deleting element from queue **********/

/********** Function Definition begins **********/

int dequeue(int q[])

{

int data;

data = q[front];

front++;

if(front==SIZE)

{

front=1;

rear=1;

}

return(data);

}

/**********************************************************************/

/*Program:To show operations in graph*/

/*Purpose:Program to show depth first search in graph*/

/*Date:06-01-2005*/

/*Time:07:10*/

/**********************************************************************/

#include

#include

#define SIZE 10

#define FALSE 0

#define TRUE 1

typedef int adj_mat[SIZE][SIZE];

typedef struct graph_t{

int nodes[SIZE];

int n;

int *visited;

adj_mat mat;

}graph;

/**************Function Declaration Begin**********/

void DFS(graph *);

void visit(graph *,int);

/**************Function Declaration End**********/

static int find=0;

void main()

{

graph G;

//clrscr();

printf(“\n\t\t Program shows the traversal of graph using Depth First Search”);

printf(“\n\t\t Enter number of nodes in the graph:”);

scanf(“%d”,&G.n);

DFS(&G);

getch();

}

/********** depth first searching **********/

/********** Function Definition begins **********/

void DFS( graph *G )

{

int k,i,j;

for(k=1;k<=G->n;k++)

G->visited[k] = FALSE;

for(i=1;i<=G->n;i++)

{

for(j=1;j<=G->n;j++)

{

printf(“\n Enter data of vertex %d for(%d,%d):\n”,i,i,j);

printf(“\n Enter 1 for adjacent vertex and 0 for otherwise:”);

scanf(“%d”,&G->mat[i][j]);

}

}

for(k=1;k<=G->n;k++)

{

if ( !G->visited[k] )

visit(G, k);

}

printf(“\n Adjacency matrix of the grpah is \n”);

for(i=1;i<=G->n;i++)

{

for(k=1;k<=G->n;k++)

{

printf(“%d\t”,G->mat[i][k]);

}

printf(“\n”);

}

i=0;

printf(“\n Traversal of a given graph is \n”);

while(in)

{

printf(“%d\t”,G->nodes[++i]);

}

}

/********** Function Definition ends **********/

/********** visiting graph **********/

/********** Function Definition begins **********/

void visit( graph *G, int k )

{

int j;

G->visited[k] = TRUE;

G->nodes[++find] = k;

for(j=1;j<=G->n;j++)

{

if(G->mat[k][j] == 1)

{

if (!G->visited[j])

visit( G, j );

}

}

}

/********** Function Definition ends **********/

/**********************************************************************/

/*Program:To show Dijkstra’s Algorithm*/

/*Purpose:Program to compute shortest path in graph*/

/*Date:07-01-2005*/

/*Time:17:10*/

/**********************************************************************/

#include

#include

#include

#define INF INT_MAX

#define v 10

#define F 0

#define T 1

typedef int adj_mat[v][v];

typedef structgraph_tag

{

int nodes;

int path[v];

int dist[v];

int visited[v];

adj_mat cost;

}graph;

/**************Function Declaration Begin**********/

void dijkstra(graph *);

/**************Function Declaration End**********/

void main()

{

graph G;

clrscr();

printf(“\n\t\t Dijkstras Algorithm:”);

printf(“\n\t\t This program finds the shortest path of a directed graph\n”);

printf(“\n\t\t Enter number of vertices required in the graph:\n”);

scanf(“%d”,&G.nodes);

dijkstra(&G);

getch();

}

/********** dijkstras technique for shortest path **********/

/********** Function Definition begins **********/

void dijkstra(graph *G)

{

int i,j,k=0,x,y,p,min;

for(i=0;inodes;i++)

{

for(j=0;jnodes;j++)

{

printf(“\n\t\t Enter cost for visiting vertex %d to vertex %d:\n”,i,j);

scanf(“%d”,&G->cost[i][j]);

}

}

printf(“\n\t\t Cost Adjacency matrix of a graph is: \n”);

for(i=0;inodes;i++)

{

for(j=0;jnodes;j++)

{

printf(“%3d\t”,G->cost[i][j]);

}

printf(“\n”);

}

printf(“The shortest path of the graph is :\n”);

G->visited[0]=T;

G->dist[0]=0;

G->path[0] = 0;

printf(“%d\n”,G->path[0]);

k++;

for(y=1;ynodes;y++)

{

G->visited[y] = F;

G->dist[y] = G->cost[0][y];

}

for(i=1;inodes;i++)

{

min = INF;

for(x=1;xnodes;x++)

{

if(!G->visited[x])

if(G->dist[x]

{

y = x;

min = G->dist[x];

}

}

G->visited[y] = T;

for(x=1;xnodes;x++)

if(!G->visited[x])

if(min + G->cost[y][x]dist[x])

G->dist[x] = min + G->cost[y][x];

G->path[k] = y;

for(p=0;p<=k;++p)

printf(“%d\t”,G->path[p]);

k++;

printf(“\n”);

}

}

/**********************************************************************/

/*Program:To show Prims Algorithm*/

/*Purpose:Program to compute mimimum spanning tree of graph*/

/*Date:08-01-2005*/

/*Time:12:20*/

/**********************************************************************/

#include

#include

#include

#define INF INT_MAX

#define v 10

#define FALSE 0

#define TRUE 1

typedef structtree_tag

{

int nodes;

int path[v];

int tree[v][v];

int chosen[v];

int adj_mat[v][v];

}tree;

/**************Function Declaration Begin**********/

void prims(tree *);

/**************Function Declaration End**********/

void main()

{

tree T;

clrscr();

printf(“\n\t\t Prims Minimum Spanning Tree Algorithm:”);

printf(“\n\t\t Program obtains the minimum spanning tree of a undirected graph \n”);

printf(“\n\t\t Enter number of edges required in the graph:\n”);

scanf(“%d”,&T.nodes);

prims(&T);

getch();

}

/********** prims technique for minimum spanning tree **********/

/********** Function Definition begins **********/

void prims(tree *T)

{

int i,j,k=0,x,y,min,len;

for(i=0;inodes;i++)

{

for(j=0;jnodes;j++)

{

printf(“\n\t\t Enter weight for visiting edge %d to edge %d:”,i,j);

scanf(“%d”,&T->adj_mat[i][j]);

}

}

printf(“\n\t\t Cost adjacency matrix of graph is:\n”);

for(i=0;inodes;i++)

{

for(j=0;jnodes;j++)

{

printf(“%3d\t”,T->adj_mat[i][j]);

}

printf(“\n”);

}

for(i=0;inodes;i++)

{

T->chosen[i] = FALSE;

}

for(i=0;inodes;i++)

{

for(j=0;jnodes;j++)

{

T->tree[i][j]=0;

}

}

T->chosen[0]=TRUE;

T->path[0]=0;

len = 1;

while(len<=T->nodes)

{

min = INF;

for(i=0;inodes;i++)

{

if(T->chosen[i]==TRUE)

{

for(j=0;jnodes;j++)

{

if(T->chosen[j]==FALSE)

{

if(T->adj_mat[i][j]

{

min = T->adj_mat[i][j];

y = i;

x = j;

}

}

}

}

}

T->tree[y][x] = 1;

T->chosen[x] = TRUE;

T->path[++k] = x;

len++;

}

printf(“\n\t\t Minimum Spanning Tree Adjacency matrix :\n”);

for(i=0;inodes;i++)

{

for(j=0;jnodes;j++)

{

printf(“%3d\t”,T->tree[i][j]);

}

printf(“\n”);

}

printf(“\n\t\t The minimum spanning tree path of the prim’s algorithm is:”);

for(i=0;i

printf(“%d\t”,T->path[i]);

printf(“\n”);

}

/********** Function Definition ends **********/