Implementazione (Parte 2)

Lezione 6 di 9 del corso Ricerca in profondità - Algoritmi su grafi di Coddy.

Ora attraversiamo l'intero grafo con uno stack.

Sfida

Medio

Ora costruisci la visita completa.

Scrivi una funzione chiamata dfs che prende n, l'array piatto edges (non orientato) e un vertice start, e restituisce l'ordine in cui la DFS visita i vertici, iniziando da start.

Prima costruisci la lista di adiacenza (ordina i vicini di ogni vertice in ordine crescente). Poi esegui una DFS iterativa con uno stack. Vengono visitati solo i vertici raggiungibili da start.

Per visitare i vicini in ordine crescente, inseriscili nello stack dal più grande al più piccolo.

Provalo tu

#include <stdlib.h>

int* dfs(int n, int* edges, int edges_size, int start, int* returnSize) {
    // Scrivi il codice qui
    *returnSize = 0;
    return edges;
}