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 

Answer 1

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

Answer 2

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.