#include \"graph.h\" #include <stdlib.h> #include <stdio.h> #include <limits.h>
ID: 3541074 • Letter: #
Question
#include "graph.h"
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include "cirListDeque.h"
void createGraph1(Graph* g)
{
Vertex* firstVert;
Vertex* secondVert;
int i;
srand(3);
g->numVertices = 3;
setupVertices(g);
g->numEdges = 3;
for(i = 0; i < g->numEdges; ++i)
{
firstVert = &g->vertexSet[i];
secondVert = &g->vertexSet[(i+1) % g->numVertices];
setupEdge(g, firstVert, secondVert);
}
}
void createGraph2(Graph* g)
{
Vertex* firstVert;
Vertex* secondVert;
int i;
srand(57);
g->numVertices = 8;
setupVertices(g);
g->numEdges = 10;
for(i = 0; i < g->numEdges; ++i)
{
firstVert = &g->vertexSet[rand() % g->numVertices];
secondVert = firstVert;
while(firstVert == secondVert || isAdjacent(firstVert, secondVert))
secondVert = &g->vertexSet[rand() % g->numVertices];
setupEdge(g, firstVert, secondVert);
}
}
void createGraph3(Graph* g)
{
Vertex* firstVert;
Vertex* secondVert;
int i;
srand(33);
g->numVertices = 26;
setupVertices(g);
g->numEdges = 10;
for(i = 0; i < g->numEdges; ++i)
{
firstVert = &g->vertexSet[rand() % g->numVertices];
secondVert = firstVert;
while(firstVert == secondVert || isAdjacent(firstVert, secondVert))
secondVert = &g->vertexSet[rand() % g->numVertices];
setupEdge(g, firstVert, secondVert);
}
}
void createGraph4(Graph* g)
{
Vertex* firstVert;
Vertex* secondVert;
int i;
srand(9875);
g->numVertices = 26;
setupVertices(g);
g->numEdges = 100;
for(i = 0; i < g->numEdges; ++i)
{
firstVert = &g->vertexSet[rand() % g->numVertices];
secondVert = firstVert;
while(firstVert == secondVert || isAdjacent(firstVert, secondVert))
secondVert = &g->vertexSet[rand() % g->numVertices];
setupEdge(g, firstVert, secondVert);
}
}
void createGraph5(Graph* g)
{
int i, j;
srand(9875);
g->numVertices = 20;
setupVertices(g);
g->numEdges = 400;
for(i = 0; i < g->numVertices; ++i)
for(j = i + 1; j < g->numVertices; ++j)
setupEdge(g, &g->vertexSet[i], &g->vertexSet[j]);
}
/* Initializes all information for the vertices in the graph
* param: g Graph whose vertices will be initialized
* pre: numVertices has been initialized
*/
void setupVertices(Graph* g)
{
int i;
g->vertexSet = (Vertex*) malloc(g->numVertices * sizeof(Vertex));
for(i = 0; i < g->numVertices; ++i)
{
g->vertexSet[i].label = 'A' + i;
g->vertexSet[i].isVisited = 0;
g->vertexSet[i].neighbors = (Vertex**)malloc(sizeof(Vertex*));
g->vertexSet[i].numNeighbors = 0;
}
}
/* Creates all the links necessary to form an edge between the two argument vertices.
* param: g Graph in which the vertices reside
* param: first Vertex from which the edge will originate
* param: second Vertex at which the edge terminates
* post: all links necessary to form an edge between first and second have been completed.
*/
void setupEdge(Graph* g, Vertex* first, Vertex* second)
{
first->numNeighbors++;
second->numNeighbors++;
first->neighbors = (Vertex**)realloc(first->neighbors, first->numNeighbors * sizeof(Vertex*));
second->neighbors = (Vertex**)realloc(second->neighbors, second->numNeighbors * sizeof(Vertex*));
first->neighbors[first->numNeighbors - 1] = second;
second->neighbors[second->numNeighbors - 1] = first;
}
/* This function prints the graph
* param: g Graph to print
*/
void printGraph(Graph* g)
{
int i, j;
Vertex* currVert;
printf("***** This graph has %d Vertices and %d Edges ", g->numVertices, g->numEdges);
/* print the vertex set */
for(i = 0; i < g->numVertices; ++i)
{
currVert = &g->vertexSet[i];
printf("%c: ", currVert->label);
for(j = 0; j < currVert->numNeighbors - 1; ++j)
printf("%c, ", currVert->neighbors[j]->label);
if(currVert->numNeighbors > 0)
printf("%c ", currVert->neighbors[j]->label);
else printf(" ");
}
}
/* This function can be used to determine if two vertices are adjacent
* param: firstVert Vertex to check neighbors from
* param: secondVert Vertex to check neighbors to
* ret: boolean (encoded as int) indicating whether or not the vertices
* are adjacent (an edge exists between them)
*/
int isAdjacent(Vertex* firstVert, Vertex* secondVert)
{
int i;
for(i = 0; i < firstVert->numNeighbors; ++i)
if( firstVert->neighbors[i] == secondVert)
return 1;
return 0;
}
/* This function clears all the search flags in the graph
* param: g Graph to have its flags cleared
* post: All vertices in the graph should have their search flags turned off
*/
void clearVisited(Graph* g)
{
int i;
for(i = 0; i < g->numVertices; ++i)
g->vertexSet[i].isVisited = 0;
}
/* these two functions provide a recursive version of the depth first search.
* feel free to use this to check your answers
* param: g Graph to perform the search in
* param: source Vertex to originate the search from
* param: destination Vertex to stop the search from (if it is found)
* ret: boolean indicating whether or not a path exists
*/
int DFSRecursiveHelper(Graph* g, Vertex* currVert, Vertex* destination)
{
int i;
currVert->isVisited = 1;
if(currVert == destination)
return 1;
for(i = 0; i < currVert->numNeighbors; ++i)
if(!currVert->neighbors[i]->isVisited)
if(DFSRecursiveHelper(g, currVert->neighbors[i], destination))
return 1;
return 0;
}
int DFSRecursive(Graph* g, Vertex* source, Vertex* destination)
{
clearVisited(g);
return DFSRecursiveHelper(g, source, destination);
}
/* This function should return a boolean (encoded as an int) indicating
* whether or not a path exists between the argument vertices.
* param: g Graph to perform the search in
* param: source Vertex to originate the search from
* param: destination Vertex to stop the search from (if it is found)
* ret: boolean indicating whether or not a path exists
*/
int DFS(Graph* g, Vertex* source, Vertex* destination)
{
/* FIXME you will write this */
return 0;
}
/* This function should return a boolean (encoded as an int) indicating
* whether or not a path exists between the argument vertices.
* param: g Graph to perform the search in
* param: source Vertex to originate the search from
* param: destination Vertex to stop the search from (if it is found)
* ret: boolean indicating whether or not a path exists
*/
int BFS(Graph* g, Vertex* source, Vertex* destination)
{
/* FIXME you will write this */
return 0;
}
Explanation / Answer
#include<stdio.h>
int q[ 20 ], top = -1, front = -1, rear = -1, a[ 20 ][ 20 ], vis[ 20 ], stack[ 20 ];
int delete();
void add ( int item );
void bfs( int s, int n );
void dfs( int s, int n );
void push( int item );
int pop();
main()
{
int n, i, s, ch, j;
char c, dummy;
printf( "ENTER THE NUMBER VERTICES " );
scanf( "%d", &n );
for ( i = 1;i <= n;i++ )
{
for ( j = 1;j <= n;j++ )
{
printf( "ENTER 1 IF %d HAS A NODE WITH %d ELSE 0 ", i, j );
scanf( "%d", &a[ i ][ j ] );
}
}
printf( "THE ADJACENCY MATRIX IS " );
for ( i = 1;i <= n;i++ )
{
for ( j = 1;j <= n;j++ )
{
printf( " %d", a[ i ][ j ] );
}
printf( " " );
}
do
{
for ( i = 1;i <= n;i++ )
vis[ i ] = 0;
printf( " MENU" );
printf( " 1.B.F.S" );
printf( " 2.D.F.S" );
printf( " ENTER YOUR CHOICE" );
scanf( "%d", &ch );
printf( "ENTER THE SOURCE VERTEX :" );
scanf( "%d", &s );
switch ( ch )
{
case 1:
bfs( s, n );
break;
case 2:
dfs( s, n );
break;
}
printf( "DO U WANT TO CONTINUE(Y/N) ? " );
scanf( "%c", &dummy );
scanf( "%c", &c );
}
while ( ( c == 'y' ) || ( c == 'Y' ) );
}
void bfs( int s, int n )
{
int p, i;
add
( s );
vis[ s ] = 1;
p = delete();
if ( p != 0 )
printf( " %d", p );
while ( p != 0 )
{
for ( i = 1;i <= n;i++ )
if ( ( a[ p ][ i ] != 0 ) && ( vis[ i ] == 0 ) )
{
add
( i );
vis[ i ] = 1;
}
p = delete();
if ( p != 0 )
printf( " %d ", p );
}
for ( i = 1;i <= n;i++ )
if ( vis[ i ] == 0 )
bfs( i, n );
}
void add
( int item )
{
if ( rear == 19 )
printf( "QUEUE FULL" );
else
{
if ( rear == -1 )
{
q[ ++rear ] = item;
front++;
}
else
q[ ++rear ] = item;
}
}
int delete()
{
int k;
if ( ( front > rear ) || ( front == -1 ) )
return ( 0 );
else
{
k = q[ front++ ];
return ( k );
}
}
void dfs( int s, int n )
{
int i, k;
push( s );
vis[ s ] = 1;
k = pop();
if ( k != 0 )
printf( " %d ", k );
while ( k != 0 )
{
for ( i = 1;i <= n;i++ )
if ( ( a[ k ][ i ] != 0 ) && ( vis[ i ] == 0 ) )
{
push( i );
vis[ i ] = 1;
}
k = pop();
if ( k != 0 )
printf( " %d ", k );
}
for ( i = 1;i <= n;i++ )
if ( vis[ i ] == 0 )
dfs( i, n );
}
void push( int item )
{
if ( top == 19 )
printf( "Stack overflow " );
else
stack[ ++top ] = item;
}
int pop()
{
int k;
if ( top == -1 )
return ( 0 );
else
{
k = stack[ top-- ];
return ( k );
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.