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

CodePudding user response：

"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.