#include<stdio.h>

#define MAX 5

int spantree[MAX][MAX];

//depth-first search, recursive variant
int dfs(int adj[][MAX],int visited[],int start)
{
  int i;

  visited[start] = 1;
  for(i=0;i<MAX;i++)
  {
      if(adj[start][i] && visited[i] == 0)
      {
        dfs(adj,visited,i);
        //postwork, add edge to spanning tree
        spantree[start][i] = 1;
        spantree[i][start] = 1;
      }
  }

  return 0;
}

void printMatrix(int mat[][MAX], int m, int n)
{
  int i,j;

  for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
         printf("%3d", mat[i][j]);
    }
    printf("\n");
  }
}

int main()
{
  //assert that the graph is undirected, i.e., its adjacency matrix is symmetric
  int adj[MAX][MAX] = {{0,0,1,1,0},{0,0,1,0,0},{1,1,0,1,1},{1,0,1,0,1},{0,0,1,1,0}};
  int visited[MAX] = {0};

  dfs(adj,visited,0);
  printf("The spanning tree: \n\n");
  printMatrix(spantree,MAX,MAX);
  return 0;
}