/* 
 * Code example for CP264 Data Structures II
 * graph representation by adjacent matrix
 * modified from textbook example
 * HBF 
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 10

void randomGraph(int adj[][MAX]);
void displayAdjacentMatrix(int adj[][MAX]);
void breadth_first_search(int adj[][MAX], int visited[], int start);
void depth_first_search(int adj[][MAX], int visited[], int start);
void depth_first_search_recursive(int adj[][MAX], int visited[], int start);

int main() {
  int adj[MAX][MAX];
  int visited[MAX];
  int i;

  randomGraph(adj);
  displayAdjacentMatrix(adj);

  printf("\nBFS:\n");
  for (i=0; i<MAX; i++) visited[i] = 0;
  breadth_first_search(adj, visited, 0);

  printf("\nDFS:\n");
  for (i=0; i<MAX; i++) 
    visited[i] = 0;
  depth_first_search(adj,visited,0);

  printf("\nDFS recursion:\n");
  for (i=0; i<MAX; i++) visited[i] = 0;
  depth_first_search_recursive(adj,visited,0);  
  return 0;
}

void randomGraph(int adj[][MAX]) {
  int i, j, v;
  srand(time(NULL));
  for (i = 0; i < MAX; i++) {
    for (j = 0; j < MAX; j++) {
      if (j == i)
        adj[i][j] = 0;
      else {
        v = rand() % 2;
        adj[i][j] = v;
        adj[j][i] = v;
      }
    }
  }
}

void displayAdjacentMatrix(int adj[][MAX]) {
  int i, j;
  printf("   ");
  for (i = 0; i < MAX; i++)
    printf("%d ", i);
  printf("\n");
  for (i = 0; i < MAX; i++) {
    printf("%d ", i);
    for (j = 0; j < MAX; j++) {
      printf(" %d", adj[i][j]);
    }
    printf("\n");
  }
}

void breadth_first_search(int adj[][MAX], int visited[], int start) {
  int queue[MAX], rear = -1, front = -1, i;
  queue[++rear] = start;
  visited[start] = 1;
  while (rear != front) {
    start = queue[++front];
    printf("%d ", start);
    for (i = 0; i < MAX; i++) {
      if (adj[start][i] == 1 && visited[i] == 0) {
        queue[++rear] = i;
        visited[i] = 1;
      }
    }
  }
}

void depth_first_search(int adj[][MAX], int visited[], int start) {
  int stack[MAX];
  int top = -1, i;
  printf("%d ", start);
  visited[start] = 1;
  stack[++top] = start;
  while (top != -1) {
    start = stack[top];
    for (i = 0; i < MAX; i++) {
      if (adj[start][i] && visited[i] == 0) {
        stack[++top] = i;
        printf("%d ", i);
        visited[i] = 1;
        break;
      }
    }
    if (i == MAX) top--;
  }
}

void depth_first_search_recursive(int adj[][MAX], int visited[], int start) {
  printf("%d ", start);
  visited[start] = 1;
  int i;
  for (i = 0; i < MAX; i++) {
    if (adj[start][i] && visited[i] == 0) {
      depth_first_search_recursive(adj, visited, i);
    }
  }
}


/*
   0 1 2 3 4 5 6 7 8 9
0  0 0 1 1 0 1 0 0 0 0
1  0 0 0 1 1 0 1 1 1 0
2  1 0 0 1 0 1 0 1 0 1
3  1 1 1 0 0 0 1 0 1 0
4  0 1 0 0 0 1 0 0 1 1
5  1 0 1 0 1 0 1 0 0 0
6  0 1 0 1 0 1 0 1 1 1
7  0 1 1 0 0 0 1 0 1 0
8  0 1 0 1 1 0 1 1 0 1
9  0 0 1 0 1 0 1 0 1 0

BFS:
0 2 3 5 7 9 1 6 8 4
DFS:
0 2 3 1 4 5 6 7 8 9
DFS recursion:
0 2 3 1 4 5 6 7 8 9
 */