so I have this function which does a depth first search traversal of a graph and prints out the nodes traversed. But instead of printing the nodes I want this function to return the node it newly moved to, return one node per call of the function.
when I call the function with the start node 0, it should return the next node in traversal (order of the nodes when traversing is printed out when running the program, along with the graph's adjacency list), which is 1 but it is returning 3.
the traversal order is: 1 2 3 2 4 5 4 6
below is what I have tried:
int DFS(struct Graph* graph, int vertex) {
struct node* adjList = graph->adjLists[vertex];
struct node* temp = adjList;
int back = 0;
graph->visited[vertex] = 1;
while (temp != NULL) {
int connectedVertex = temp->vertex;
if (graph->visited[connectedVertex] == 0) {
if ( back==1 ) {
return vertex;
printf("node: %d\n", vertex);
}
printf("node 1: %d\n", connectedVertex);
return DFS(graph, connectedVertex);
back = 1;
}
temp = temp->next;
}
return vertex;
}
and here is the function without the return statements (originally a void function):
void DFS(struct Graph* graph, int vertex) {
struct node* adjList = graph->adjLists[vertex];
struct node* temp = adjList;
int back = 0; // = "We have already expanded vertex"
graph->visited[vertex] = 1;
while (temp != NULL) {
int connectedVertex = temp->vertex;
if (graph->visited[connectedVertex] == 0) {
if ( back==1 ) // Report the revisited node
printf("node: %d\n", vertex);
printf("node: %d\n", connectedVertex);
DFS(graph, connectedVertex);
back = 1; // Tag this node as having been expanded.
}
temp = temp->next;
}
}
and here is my full program:
// DFS algorithm in C
#include <stdio.h>
#include <stdlib.h>
struct node {
int vertex;
struct node* next;
};
struct node* createNode(int v);
struct Graph {
int numVertices;
int* visited;
struct node** adjLists;
};
void DFS(struct Graph* graph, int vertex) {
struct node* adjList = graph->adjLists[vertex];
struct node* temp = adjList;
int back = 0; // = "We have already expanded vertex"
graph->visited[vertex] = 1;
while (temp != NULL) {
int connectedVertex = temp->vertex;
if (graph->visited[connectedVertex] == 0) {
if ( back==1 ) // Report the revisited node
printf("node: %d\n", vertex);
printf("node: %d\n", connectedVertex);
DFS(graph, connectedVertex);
back = 1; // Tag this node as having been expanded.
}
temp = temp->next;
}
}
// Create a node
struct node* createNode(int v) {
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Create graph
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct node*));
graph->visited = malloc(vertices * sizeof(int));
int i;
for (i = 0; i < vertices; i ) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
void sortedInsert(struct node** head_ref,
struct node* new_node)
{
struct node* current;
/* Special case for the head end */
if (*head_ref == NULL
|| (*head_ref)->vertex
>= new_node->vertex) {
new_node->next = *head_ref;
*head_ref = new_node;
}
else {
/* Locate the node before
the point of insertion */
current = *head_ref;
while (current->next != NULL
&& current->next->vertex < new_node->vertex) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
// Add edge
void addEdge(struct Graph* graph, int src, int dest) {
// Add edge from src to dest
sortedInsert(&graph->adjLists[src], createNode(dest));
// Add edge from dest to src
sortedInsert(&graph->adjLists[dest], createNode(src));
}
// Print the graph
void printGraph(struct Graph* graph) {
int v;
for (v = 0; v < graph->numVertices; v ) {
struct node* temp = graph->adjLists[v];
printf("\n Adjacency list of vertex %d\n ", v);
while (temp) {
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}
int main() {
struct Graph* graph = createGraph(7);
addEdge(graph, 0, 1);
addEdge(graph, 0, 3);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
addEdge(graph, 2, 4);
addEdge(graph, 4, 5);
addEdge(graph, 4, 6);
printGraph(graph);
DFS(graph, 0);
return 0;
}
Help would be much appreciated.
CodePudding user response：
" I want this function to return the node it newly moved to, return one node per call of the function."
This is a bad idea, because your function is recursive.
To get the nodes traversed in order add the visited node index to a global data structure.
Note: Recursion is the correct way to go here. Returning the node visited from the recursive function will not work.
CodePudding user response：
I added this two fuctions:
// Adds a node to a list of nodes
void addNode(struct node** nodeList, int vertex){
struct node *temp = *nodeList;
if(*nodeList == NULL){
*nodeList = createNode(vertex);
}else{
while(temp->next != NULL){
temp = temp->next;
}
temp->next = createNode(vertex);
}
}
// Prints a list of nodes
void printNodeList(struct node* nodeList) {
struct node* temp = nodeList;
while(temp != NULL){
printf("%d", temp->vertex);
if(temp->next != NULL){
printf(" -> ");
}
temp = temp->next;
}
printf("\n");
}
and modified DFS and main as follow:
// added last argument
void DFS(struct Graph* graph, int vertex, struct node** nodeList) {
struct node* adjList = graph->adjLists[vertex];
struct node* temp = adjList;
graph->visited[vertex] = 1;
addNode(nodeList, vertex); // added this
while (temp != NULL) {
int connectedVertex = temp->vertex;
if (graph->visited[connectedVertex] == 0) {
printf("node: %d\n", connectedVertex);
DFS(graph, connectedVertex, nodeList);
addNode(nodeList, vertex); // added this
}
temp = temp->next;
}
}
int main() {
struct node* nodeList = NULL;
struct Graph* graph = createGraph(7);
addEdge(graph, 0, 1);
addEdge(graph, 0, 3);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
addEdge(graph, 2, 4);
addEdge(graph, 4, 5);
addEdge(graph, 4, 6);
printGraph(graph);
DFS(graph, 0, &nodeList);
printNodeList(nodeList);
return 0;
}
If I would have to define the traversal order of the nodes, in your example graph it would not be 1 -> 2 -> 3 -> 2 -> 4 -> 5 -> 4 -> 6 but rather 0 -> 1 -> 2 -> 3 -> 2 -> 4 -> 5 -> 4 -> 6 -> 4 -> 2 -> 1 -> 0, since I think that any time you "land" on a different node (either because you call DFS or because DFS gives back control to the caller), that "counts" in the path you're following to search the graph, and this until you're back to the main function, hence you've finished searching. Therefore in the DFS function above I implemented that, but if you need the order you mentioned, just add addNode(nodeList, vertex); below your printf statements and you should get it.
Since the function is recursive you can't really use the return statement to return the visited nodes, because what you want to have at the end is a list of elements and not just a single value. For instance in your code you defined the return type of DFS as int, this means that the function can only give you back a number, but when you call DFS in your main function you expect it to give you back a list of node that got visited. You may be able to figure out something returning a pointer to a data structure or maybe returning an int (the visited vertex) and calling something like addNode(list, DFS(g, vertex)) but you would still need to pass the list to DFS (otherwise you won't be able to call addNode(list,...) inside of it), so you would get addNode(list, DFS(g, vertex, list)), therefore I don't think you would get any advantage out of it, but I don't know.
What I did is to define a list in the main function and to pass it to the recursive function (does not need to return anything), which is then able to add the visited node to it when necessary. The first call to addNode(nodeList, vertex) happens only once per vertex since you never call DFS more than one time for any vertex, while the second happens every time you come back to a vertex after having searched into one of it's neighbors.