I want to make DFS with adjacent matrix to have ability on DFS with adjacent List

Question

Please let me know how to change the performance from O(n^2) to O(n+e) by inserting any codes.. without modification

typedef struct GraphType 
{ 
    int n; //the number of vertex GraphNode
    int adj_mat[50][50]; 
} GraphType;

void dfs_mat(GraphType* g,int v)
{
   int w;
   visited[v] = TRUE; // Show Visits at Vertex v
   print("visit %d ->", v); print visited vertex
   for(w = 0; w<g->n; w++) // search adjacent vertex
      if(g->adj_mat[v][w] && !visited[w])
         dfs_mat(g,w); // restart from vertex w
}

void graph_init(GraphType *g)
{
   int r,c;
   g->n=0;
   for(r=0;r<50;r++)
      for(c=0;c<50;c++)
         g->adj_mat[r][c]=0;
}

void insert_vertex(GraphType *g,int v)
{
   if(((g->n)+1)>50){
      printf("error");
      return;
   }
g->n++;
}

void insert_edge(GraphType *g, int start, int end)
{
   if(start >= g->n || end >= g->n){
      printf("error");
      return;
   }
   g->adj_mat[start][end] = 1;
   g->adj_mat[end][start] = 1;
}

int main(void){
   int i;
   GraphType g;

   graph_init(&g);
   for(i=0;i<4;i++)
      insert_vertex(&g,i);
   insert_edge(&g,0,1);
   insert_edge(&g,1,0);
   insert_edge(&g,0,3);
   insert_edge(&g,3,0);
   insert_edge(&g,1,2);
   insert_edge(&g,2,1);
   insert_edge(&g,1,3);
   insert_edge(&g,3,1);
   insert_edge(&g,2,3);
   insert_edge(&g,3,2);
   dfs_mat(&g,0);
}

First, recursion occurs as much as the vertex number Because we need to check the edges.

The problem is when the program visited all vertices. Even though all vertices have already been visited, the rest of the iterative operations are executed. I think I must include conditions in the operation of the iteration sentence. but I don't know that.

Please save me.

Answer 1

You can initialize a variable, say visited_count and set it to number of nodes. Decrement this variable on each visit operation. Check each time if visited_count is equal to zero and if yes, then break out of the loop. Check the lines with ////////////////// CHANGE written in the comments.

#include <stdio.h>
#include <stdbool.h>


typedef struct GraphType 
{ 
    int n; //the number of vertex GraphNode
    int adj_mat[50][50]; 
} GraphType;

static bool visited[50] = {false};
static int visited_count;            ////////////////// CHANGE

void dfs_mat(GraphType* g,int v)
{
   int w;
   visited[v] = true; // Show Visits at Vertex v
   visited_count--;         ////////////////// CHANGE
   printf("=== visit %d ===\n", v); // print visited vertex
   for(w = 0; w<g->n && visited_count; w++) // search adjacent vertex        ////////////////// CHANGE
   {
       if (v != w)         ////////////////// CHANGE
       {
          printf("Processing node: %d, neighbor = %d\n", v, w);      ////////////////// CHANGE - added for debugging
          if(g->adj_mat[v][w] && !visited[w])
             dfs_mat(g,w); // restart from vertex w
       }
   }
}

void graph_init(GraphType *g)
{
   int r,c;
   g->n=0;
   for(r=0;r<50;r++)
      for(c=0;c<50;c++)
         g->adj_mat[r][c]=0;
}

void insert_vertex(GraphType *g,int v)
{
   if(((g->n)+1)>50){
      printf("error");
      return;
   }
g->n++;
}

void insert_edge(GraphType *g, int start, int end)
{
   if(start >= g->n || end >= g->n){
      printf("error");
      return;
   }
   g->adj_mat[start][end] = 1;
   g->adj_mat[end][start] = 1;
}

int main(void){
   int i;
   GraphType g;

   graph_init(&g);
   visited_count = 4;        ////////////////// CHANGE
   for(i=0;i<4;i++)
      insert_vertex(&g,i);
   insert_edge(&g,0,1);
   insert_edge(&g,1,0);
   insert_edge(&g,0,3);
   insert_edge(&g,3,0);
   insert_edge(&g,1,2);
   insert_edge(&g,2,1);
   insert_edge(&g,1,3);
   insert_edge(&g,3,1);
   insert_edge(&g,2,3);
   insert_edge(&g,3,2);
   dfs_mat(&g,0);
}