How to solve this Depth first search problem?

user_19571903 0
Viewed 105

So I need to do a depth first search traversal of a given graph, however if a node in the graph has multiple adjacent neighbours, I need to choose the node with the lowest value to go to. So I implemented the following recursive depth first search function:

void DFS(struct Graph *graph, int vertex) {
    struct node *adjList = graph->adjLists[vertex];
    struct node *temp = adjList;

    graph->visited[vertex] = 1;
    printf("Visited %d \n", vertex);
  
    int neighbouring_nodes[graph->numVertices];
  
    while (temp != NULL) {
        int count = 0;
        struct node *temp_cpy = temp;
     
        while (temp_cpy != NULL) {
            neighbouring_nodes[count] = temp_cpy->vertex;
            count++;
            temp_cpy = temp_cpy->next;
        }

        int smallest_node = neighbouring_nodes[0];
        
        for (int i = 0; i < count; i++) {
            if (neighbouring_nodes[i] < smallest_node) {
                smallest_node = neighbouring_nodes[i];
            }
        }
    
        if (graph->visited[smallest_node] == 0) {
            DFS(graph, smallest_node);
        } else if (graph->visited[smallest_node] == 1 && count == 1) {
            //if the node is visited but is it the only neighbour
            DFS(graph, smallest_node);
        }
        temp = temp->next;
    }
}

But when I run my program, it results in an infinite loop. I think I know why I am getting an infinite loop, it might be because there is never a return condition, so the recursive function just keeps running?

Is this type of depth first search possible with a recursive function? If yes, where am I going wrong? If no, how would I do it iteratively? Help would be much appreciated.

Below is my full program without the DFS function:

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

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

// Add edge
void addEdge(struct Graph *graph, int src, int dest) {
    // Add edge from src to dest
    struct node *newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // Add edge from dest to src
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// 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(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);

    printGraph(graph);

    DFS(graph, 2);

    return 0;
}
depth-first-search graph recursion function c
2 Answers

"if a node in the graph has multiple adjacent neighbours, I need to choose the node with the lowest value to go to."

I assume the 'value' of a node is an attribute of the node object?

Most implementations of DFS will first look at the node with the lowest index in the data structure containing the node objects. So, if you first sort the nodes in your data structure into ascending value order, then the DFS will do what you want without needing to change the DFS code.

user_165820

Here is what I came up with:

void DFS(struct Graph* graph, int vertex) {
    struct node* temp = graph->adjLists[vertex];

    graph->visited[vertex] = 1;
    printf("Visited %d \n", vertex);

    int neighbouring_nodes[graph->numVertices];

    int count = 0;

    while(temp != NULL) {
        neighbouring_nodes[count] = temp->vertex;
        count++;
        temp = temp->next;
    }

    int smallest_node = neighbouring_nodes[0];
    
    //   Need to search (at most) in every neighbouring node
    for (int i = 0; i < count; i++) {
        //   Go through all nodes in neighbouring_nodes array in order
        //   to find the smallest unvisited one, if it exists
        for (int j = 0; j < count; j++){
            //   if current smallest_node has already been visited and
            //   neighbouring_nodes[j] is unvisited, assign it to smallest_node
            if (graph->visited[smallest_node] == 1 && graph->visited[neighbouring_nodes[j]] == 0){
                    smallest_node = neighbouring_nodes[j];
            }
            //   if neighbouring_nodes[j] is smaller than smallest_node,
            //   assign it to smallest_node
            if (graph->visited[neighbouring_nodes[j]] == 0 && neighbouring_nodes[j] < smallest_node){
                smallest_node = neighbouring_nodes[j];
            }
        }
        if (graph->visited[smallest_node] == 0){
            //   calls DFS on the smallest unvisited neighboring node, if it exists
            DFS(graph, smallest_node);
        }else{
            //   otherwise (all neighboring nodes already visited)
            //   return control to the caller function
            return;
        }
    }
}

I'm not 100% sure I understood what you wanted to do with the while (temp != NULL) and while (temp_cpy != NULL) loops but couldn't really figure out a way to use this approach especially in your particular case in which you want to visit the neighboring nodes in ascending order.

Let's assume a simple graph like 6->0->1, calling DFS(g, 0) will get temp to point to 6->1->NULL (could be also 1->6->NULL, depending on how you construct the graph), then smallest_node will be 1 and therefore the node 1 will be visited and the temp = temp->next will "assign" 1->NULL to temp. Back to the beginning of the loop, now temp_cpy will "be equal" to temp, hence 1->NULL. The node 6 is not on the list anymore even if it was not visited, on the other hand the already visited node 1 is still there. Also count is now equal to 1 therefore the condition (graph->visited[smallest_node] == 1 && count == 1) is met and DFS(g, 1) is called, which should not since node 1 was already visited. The infinite loop arises from this, since the previous condition is always met when temp has one (already visited) element left ([some value]->NULL). Once you reach that point you always call DFS(g, [some value]) and this will never give back control, since before reaching the temp = temp->next statement (which should assign NULL to temp , hence ending the while loop), DFS(g, [some other value]) is again called, which at some point will again call DFS(g, [some value]), and so forth.

As mentioned, one problem your original code has is that you call the DFS function also for an already visited vertex, and this should never be the case. When you encounter an already visited neighboring vertex, you want either to check the next or, if there are no unvisited neighboring vertices left, to give back control to the caller function. Therefore the last if else statement should not be there. The second problem is that smallest_node is selected in the wrong way. This is because temp_cpy, as explained above, is not constructed in such a way that it necessarily contains all unvisited neighboring nodes and also because you're actually looking for the smallest element in this list, regardless if it has already been visited or not (again because of the assumption that temp_cpy contains only all unvisited nodes). In fact you should be looking for the "smallest unvisited node" rather than the "smallest node".

In my code I go through all neighboring nodes with two for loops, find the smallest unvisited one and call DFS(g, [smallest unvisited node]) and once there are no unvisited neighbors left, return control back to the caller function.

I Hope this is somewhat understandable and I also hope I'm not missing something about what you had in mind with your implementation, in which case I would be very much interested in some explanations!

Here is a simpler version of the DFS in which neighboring nodes are checked and eventually visited in the order they're presented in the adjList. In this case I think the while (temp != NULL)/temp = temp->next approach makes sense:

void DFS(struct Graph *graph, int vertex) {
    struct node *temp = graph->adjLists[vertex];

    graph->visited[vertex] = 1;
    printf("Visited %d \n", vertex);

    //   for vertex search in every neighboring node
    while (temp != NULL) {
        //   if neighboring vertex temp->vertex not visited, then search there
        if (graph->visited[temp->vertex] == 0) {
            DFS(graph, temp->vertex);
        //   if already visited, go to the next vertex on the neighbors list
        }else{
            temp = temp->next;
        }
    }
    // when searched in all neighboring vertexes return control to caller
    return;
}
user_170542180
Related