DFS

// Algoritmul de parcurgere in adancime (DFS). Reprezentarea grafului se face cu matrice de adiacenta.

#include <stdio.h>
#include <string.h>

#define NMAX 100

char vecin[NMAX][NMAX]; // Matricea de adiacenta a grafului

char visit[NMAX];      // visit[k] = 1 daca nodul k a fost vizitat si 0 in caz contrar

int trace[NMAX];       // tablou ce pastreaza nodurile in ordinea in care sunt intalnite la parcurgerea in latime
int kth;               // numarul de elemente vizitate


void dfs(int n, short u) {
  int v;

  visit[u] = 1;        // marcheaza nodul u ca fiind vizitat
  trace[kth++] = u;    // adauga nodul u in tabloul ce contine lista nodurilor deja vizitate

  for (v = 0; v < n; v++) {       // pentru toate nodurile grafului
    if ((vecin[u][v] == 1) && !visit[v]) {  // verifica daca u si v sunt vecine si daca v nu a fost vizitat
      dfs(n, v);                  // apeleaza recursiv dfs pentru nodul v
    }
  }
}


int main() {
  FILE *fin, *fout;
  int n, m, u, v, i, start;

  fin = fopen("dfs.in", "r");
  fout = fopen("dfs.out", "w");

  fscanf(fin, "%d %d %d", &n, &m, &start);
  start--;

  for (i = 0; i < m; i++) {
    fscanf(fin, "%d %d", &u, &v);  // citeste o pereche de noduri adiacente

    u--;                           // scade 1 din valorile nodurilor
    v--;                           // transforma nodurile din intervalul 1...n in 0...(n-1)
    vecin[u][v] = 1;               // marcheaza faptul ca u si v sunt adiacente
    vecin[v][u] = 1;
  }

  dfs(n, start);                   // porneste din start sa viziteze nodurile folosind strategia DFS

  for (i = 0; i < kth; i++) {      // afiseaza in ordine nodurile vizitate
    fprintf(fout, "%d ", trace[i] + 1);
  }

  fclose(fin);
  fclose(fout);

  return 0;
}