Hi so I've implemented a function that does a depth first search traversal of an undirected graph. But I am struggling to print the DFS traversal like the below output.

note: I have implemented my graph in a way so that the traversal would choose the neighbour node with the smallest value if a node has multiple adjacent neighbours.

the graph given is shown in the image and is my program and the start node is 0:

the DFS traversal by my function would be:

1 > 2 > 3 > 2 > 4 > 5 > 4 > 6

But what I have prints out:

1 > 2 > 3 > 4 > 5 > 6 

Some nodes that are being revisited (when there is no choice but to visit them to go to the other unvisited ones) are not being printed.

below is my dfs function:

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

  graph->visited[vertex] = 1;

  while (temp != NULL) {
    int connectedVertex = temp->vertex;
     
    if (graph->visited[connectedVertex] == 0) {

        printf("node: %d\n", connectedVertex);
      DFS(graph, connectedVertex);
    }

    temp = temp->next;
  }
}

below is my full program:

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

  graph->visited[vertex] = 1;

  while (temp != NULL) {
    int connectedVertex = temp->vertex;
     
    if (graph->visited[connectedVertex] == 0) {

        printf("node: %d\n", connectedVertex);
      DFS(graph, connectedVertex);
    }

    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：

This will produce the output you want:

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