Hi,

I have the following program, which represents a given undirected graph:

#include #include

// 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 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 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; }

I need to find if a path exists between 2 given points, a source and target, for example, 1 and 6.

In the given case written in the program, the answer should be 'Yes' rather than 'No', as there is a path as follows: 1->5->4->6.

The following picture shows the representation of the given example in the program:

I think the following should help:

// 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); } } }

// return 1 if source and target in same connected component int isConnection(int source, int target) { return nodeMark[source] == nodeMark[target]; }

I also need to add the function destroyGraph() to my code, but don't know how?

Thanks!