C Implementation of Depth First Search Algorithm Without Pointers (Graph as Adjacency Matrix)

Question

The Question can be seen in the image: Question

The following is the sample run info for the code: Test info for the Question

Please refer to the links above for better understanding of the question.

I looked at some solution using pointers but I don't really understand, would it be possible to write the solution without pointers and only arrays.

#include  /* Include header file for printf */
#define maxV 100 /* Define a constant */

int V, E, x, y; /* Declare variables */
int a[maxV][maxV]; /* Declare a two dimensional array */
int b[maxV][maxV]
int count = 0; /* Declare and initialize variable */
void read_graph(void); /* Function prototype */
void print_graph(void);
void print_graph_grid(void);
void copy_array(void);

void main() {/* Main program. */
    read_graph(); /* call function to input graph adjacency matrix */
    //print_graph(); /* call function to output graph adjacency matrix */
    print_graph_grid();
> copy_array();
 }
void read_graph( void ) {/* Function to read graph adjacency matrix */

    int edge, x;
    printf("\nInput number of vertices :");
    scanf("%d", &V);

    if (V > maxV)
        printf("Exceed the maximum number of vertices permitted");

    else {
        for (x=1; x

ckc · Accepted Answer · 2023-03-08 16:35:31Z

1

EDIT: graph[7][7], visited[7] set as global variables after ravenspoint's comments.

#include<stdio.h>
 
int n = 7;
int graph[7][7], visited[7];

void DFS(int i)
{
    visited[i]=1;
    for(int j=0;j<n;j++)
    if(visited[j] == 0 && graph[i][j] == 1 )  {
        visited[j] = 1;
        printf(" %d", j);
        DFS(j);
    }
}

int main()  {
  
    for(int i=0;i<n;i++)  {
        visited[i]=0;
        for(int j=0;j<n;j++)  graph[i][j] = 0;
    }
    graph[0][1] = graph[0][2] = graph[1][0] = graph[1][2] = graph[2][0] = graph[2][1] = graph[2][3] = graph[3][2] = graph[4][5] = graph[4][6] = graph[5][4] = graph[5][6] = graph[6][4] = graph[4][5] = 1;
    
    printf("%d:", 0);
    DFS(0);
    printf("\n\n");
    return 0;
}

n is the number of nodes (labeled from 0 to 6) and graph[i][j] is the adjacency matrix according to the link you provided. Here, it is applied for node 0 as the root (or origin):

DFS(0);

You can put any node as root, from 0 to 6.

The result is 0: 1 2 3, meaning that nodes 1,2,3 are reachable from node 0, and nodes 4,5,6 are not.

edited Mar 8, 2023 at 16:35

answered Mar 8, 2023 at 9:03

ckc

3734 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

ravenspoint Over a year ago

You are passing the entire adjacency matrix by value to the recursive function DFS. This might be fine if the graph has just 7 vertices. What happens if there are thousands of vertices. It will be horribly slow and run out of stack memory.

ckc Over a year ago

@ravenspoint you are right, but (if I understood well), the person who asked the question wants a simple, easily understandable implementation of DFS (e.g. without pointers), and not an efficient one.

ravenspoint Over a year ago

Simple and understandable is good. But first comes correct. For this code to be of any use at all, you need to specify a limit on the number of nodes. Anyway, making the adjacency matrix global is hardly any more complicated and will work so much better.

ravenspoint Over a year ago

Bad idea to name a global variable 'graph' Probability of a name collision very high

ravenspoint · Accepted Answer · 2023-03-08 16:55:24Z

0

Make the adjacency matrix global will allow you to handle graphs containing thousands of nodes

#include<stdio.h>
#define MAX_NODES 1000
int n = 7;
int global_visited[MAX_NODES];
int global_adjacency[MAX_NODES][MAX_NODES];

void DFS(int i)
{
    global_visited[i]=1;
    for(int j=0;j<n;j++)
    if(global_visited[j] == 0 && global_adjacency[i][j] == 1 )  {
        global_visited[j] = 1;
        printf(" %d", j);
        DFS(j);
    }
}

int main()  {
  
     if( n > MAX_NODES ) {
          printf("MAX Nodes exceeded\n");
          return 1;
    }
    for(int i=0;i<n;i++)  {
        global_visited[i]=0;
        for(int j=0;j<n;j++)  {
             global_adjacency[i][j] = 0;
         }
     }

    global_adjacency[0][1] = global_adjacency[0][2] = global_adjacency[1][0]
    = global_adjacency[1][2] = global_adjacency[2][0] = global_adjacency[2][1]
    = global_adjacency[2][3] = global_adjacency[3][2] = global_adjacency[4][5] 
    = global_adjacency[4][6] = global_adjacency[5][4] = global_adjacency[5][6] 
    = global_adjacency[6][4] = global_adjacency[4][5] = 1;
    
    printf("%d:", 0);
    DFS(0);
    printf("\n\n");
    return 0;
}

edited Mar 8, 2023 at 16:55

answered Mar 8, 2023 at 16:35

ravenspoint

21.2k7 gold badges64 silver badges114 bronze badges

2 Comments

ckc Over a year ago

You cannot define global variable arrays with variable for size

ravenspoint Over a year ago

Fixed ( my C is rusty )

Collectives™ on Stack Overflow

C Implementation of Depth First Search Algorithm Without Pointers (Graph as Adjacency Matrix)

2 Answers 2

4 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related