Hi, I have a part solution to the following problem but I am not sure how to fin

Question

Hi,

I have a part solution to the following problem but I am not sure how to finish it:

You are working for a travel agency and are asked to write a computer program that can provide travel advice between cities based on a given map. The first line of the input of the program contains one integer n. n (2<=n<=10000) is the number of cities on the map. The second line of the input also contains an integer, m, (2<=m<=10000), which indicates the number of connections that will follow in the input below. Then, starting from the third line of the input, each line contains two integers from 1 to n, i.e. the connections between the cities. If a line says "a b", then it means that there is direct flight between city a and city b. There will be m of such connections. The last line also contains a pair of cities, say "c d", which will represent a query: "is there a connecting flight between c and d?"

Here is one sample input:

6

7

6 4

3 4

5 4

3 2

5 2

5 1

2 1

1 6

This sample input can be visualized as follows:

For this flight network, there exists at least one route between every pair of cities. For example, between city 5 and 6, there exists a route with 1 stop at city 4.

Given the input and the query, answer whether there is a route between cities c and d (note that this connection can be indirect). The output should be "Yes" or "No".

Let x be the total number of lines of the input. We know for sure that x is much smaller than n square. Your implementation should take this into consideration (for the purpose of saving memory).

For example, let us consider the case with n=10000 and x=10000 (so x is much less than n square). One easy way to represent a graph in memory is to use a n by n matrix. If the element in the i-th row and the j-th column equals 1, then that means node i and j are directly connected (0 means not directly connected). The memory consumption of the matrix representation is at least n square over 2 bits (each element only needs 1 bit; also, we only need to store half of the matrix due to symmetry). When n=10000, n square over 2 bits is just too much. You should find better ways to represent graphs in memory.

The program has to be written in C and be implemented using an adjacency linked list.

I have the following code (which compiles):

// Adjacency list ADT representation of a given undirected graph
// I.e. a vertex indexed array of lists

#include
#include

#define NOT_MARKED -1

typedef struct node *nodelink;
struct node
{
// Current vertex in adjacency list
int currentVertex;
// Next node in adjacency list
nodelink nextNode;
};

typedef struct graph *graph;
struct graph
{
// Number of vertices
int vertices;
// Number of edges
int edges;
// Array of vertices adjacency lists
nodelink *adjacent;
};

typedef struct
{
int vertex;
int adjacentToVertex;
} edge;

edge newEdge(int vertex, int adjacentToVertex);

nodelink newNode(int theCurrentVertex, nodelink nextNode);
graph representGraph(int numberOfVertices);
void insertGraphEdge(graph newGraph, edge theNewEdge);

static int nodeMark[10000];

int connectedGraphComponents(graph theGraph);
void recursiveDFS(graph theGraph, int theNode, int theNodeID);

int main()
{
int vertices = 6;
graph newGraph = representGraph(vertices);

// HERE: Call method to show graph newGraph

printf("%d component(s) ", connectedGraphComponents(newGraph));

return 0;
}

nodelink newNode(int theCurrentVertex, nodelink nextNode)
{
nodelink nodeNew = malloc(sizeof *nodeNew);
nodeNew->currentVertex = theCurrentVertex;
nodeNew->nextNode = nextNode;

return nodeNew;
}

// Initialize a new graph with numberOfVertices vertices
graph representGraph(int numberOfVertices)
{
int vertex;

graph newGraph = malloc(sizeof *newGraph);
newGraph->vertices = numberOfVertices;
newGraph->edges = 0;
newGraph->adjacent = malloc(numberOfVertices * sizeof(nodelink));

for(vertex=0; vertex {
newGraph->adjacent[vertex] = NULL;
}

return newGraph;
}

// Insert an edge (edge = currentVertex-adjacentToVertex)
// into graph newGraph
void insertGraphEdge(graph newGraph, edge theNewEdge)
{
int currentVertex = theNewEdge.vertex;
int adjacentToVertex = theNewEdge.adjacentToVertex;

newGraph->adjacent[currentVertex] = newNode(adjacentToVertex, newGraph->adjacent[currentVertex]);

newGraph->adjacent[adjacentToVertex] = newNode(currentVertex, newGraph->adjacent[adjacentToVertex]);

newGraph->edges++;
}

// Graph search: traverse every node and edge in the given graph
// Use Depth-first search: mark a visited node as visited, recursively
// visit all unmarked nodes adjacent to the current node being visited
// To traverse the given graph rather than the node: initialise all the
// nodes as unmarked and then visit each unmarked node

//static int nodeMark[10000];

// Traverse component of graph
int connectedGraphComponents(graph theGraph)
{
int node = 0;
int nodeID = 0;

// Initialise all nodes as unmarked
for(node=0; nodevertices; node++)
{
nodeMark[node] = NOT_MARKED;
}

// Visit each unmarked node
for(node=0; nodevertices; node++)
{
if(nodeMark[node] == NOT_MARKED)
{
recursiveDFS(theGraph, node, nodeID++);
}
}
return nodeID;
}

void recursiveDFS(graph theGraph, int theNode, int theNodeID)
{
nodelink link;
int adjacentNode;
nodeMark[theNode] = theNodeID;

// Iterate over all nodes adjacentNode adjacent to theNode
for(link=theGraph->adjacent[theNode]; link!=NULL; link=link->nextNode)
{
adjacentNode = link->currentVertex;

if (nodeMark[adjacentNode] == NOT_MARKED)
{
recursiveDFS(theGraph, adjacentNode, theNodeID);
}
}
}

Please could you edit this code in relation to the question, as I am struggling with it!

Please could you also add to the code by providing a showGraph() function and destroyGraph function()?!

Please could you also include comments.

I have the following code which I think may help:

#include "stdio.h"
#include "stdlib.h"

struct node
{
int vertex;
struct node *next;
};

struct graph
{
int vertices;
struct node *arr;
};

struct graph* createGraph(int v)
{

struct graph* Graph;
int i;
Graph = malloc(sizeof(struct graph));
Graph->vertices = v;

Graph->arr = malloc(Graph->vertices*sizeof(struct node));

for (i = 0; i < Graph->vertices; ++i)
{
Graph->arr[i].vertex = i;
Graph->arr[i].next = NULL;
}
return Graph;
}
void join(struct graph *Graph,int m,int n)
{
struct node *nodem,*noden,*temp;
nodem =(struct node *) malloc(sizeof(struct node));
nodem->vertex = m;
temp = Graph->arr[n].next;
Graph->arr[n].next = nodem;
nodem->next = temp;

noden =(struct node *) malloc(sizeof(struct node));
noden->vertex = n;
temp = Graph->arr[m].next;
Graph->arr[m].next = noden;
noden->next = temp;
}
void printgraph(struct graph *Graph)
{
int i;
for (i = 0; i < Graph->vertices; ++i)
{
printf("%d ",i );
struct node *temp;
temp = Graph->arr[i].next;
while(temp!=NULL)
{ printf("%d->",(*temp).vertex);
temp = temp->next;}
printf("NULL ");
}
}
void dfsutil(struct graph *Graph,int i,int *visited)
{

if(!visited[i])
{
visited[i] = 1;
printf("%d->",i);
}
else
return;
struct node *temp;
temp = Graph->arr[i].next;
while(temp!=NULL)
{
dfsutil(Graph,temp->vertex,visited);
temp = temp->next;
}

}
void dfs(struct graph *Graph)
{
int *visited;
int i;
visited = calloc(Graph->vertices ,sizeof(int));
for (i = 0; i < Graph->vertices; ++i)
{
printf(" ");
if(!visited[i]) dfsutil(Graph,i,visited);
}
}

int main(int argc, char const *argv[])
{
struct graph *Graph;
int v,op,i,m,n;
printf("enter no.of vertices ");
scanf("%d",&v);
Graph = createGraph(v);
printf("enter no. of operations ");
scanf("%d",&op);
for (i = 0; i < op; ++i)
{
scanf("%d %d",&m,&n);
if(m }
printgraph(Graph);
dfs(Graph);
return 0;
}

This code was found online. Please could you keep my variable names i.e. just edit my code, in answering the problem.

Many thanks!

----------------------- NEW PART SOLUTION -----------------------

#include <stdio.h>
#include <stdlib.h>

// A structure to represent an adjacency list node
struct AdjListNode
{
int dest;
struct AdjListNode* next;
};

// A structure to represent an adjacency list
struct AdjList
{
struct AdjListNode *head; // pointer to head node of list
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
int V;
struct AdjList* array;
};

// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest)
{
struct AdjListNode* newNode =
(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}

// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;

// Create an array of adjacency lists. Size of array will be V
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

// Initialize each adjacency list as empty by making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;

return graph;
}

// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest)
{
// Add an edge from src to dest. A new node is added to the adjacency
// list of src. The node is added at the begining
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;

// Since graph is undirected, add an edge from dest to src also
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}

// A utility function to print the adjacenncy list representation of graph
void printGraph(struct Graph* graph)
{
int v;
for (v = 1; v <= graph->V; ++v)
{
struct AdjListNode* pCrawl = graph->array[v].head;
printf(" Adjacency list of vertex %d head ", v);
while (pCrawl)
{
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf(" ");
}
}

// Driver program to test above functions
int main()
{
// create the graph
int V = 5;
struct Graph* graph = createGraph(V);
addEdge(graph, 6, 4);
addEdge(graph, 3, 4);
addEdge(graph, 5, 4);
addEdge(graph, 3, 2);
addEdge(graph, 5, 2);
addEdge(graph, 5, 1);
addEdge(graph, 2, 1);

// print the adjacency list representation
printGraph(graph);

return 0;
}

However, I need a destroyGraph() function and I need to know how to check that there is a connection between c and d (e.g. 1 and 6- see requirement explanation). Thank you.

Explanation / Answer

~Graph()
{
//free mem allocated to verticies
for(int i=0 ; i < nodeList.size() ; i++)
delete nodeList[i];
nodeList.clear();
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.