Implementation (Part 1)
Lição 5 de 9 do curso Busca em Profundidade - Algoritmos de Grafos da Coddy.
Vamos construir a DFS começando pela busca de adjacência.
Desafio
FácilAntes de percorrer um grafo, precisamos conhecer os vizinhos de cada vértice. Vamos construir essa busca a partir da lista linear de arestas.
Escreva uma função chamada getNeighbors que recebe o array edges (pares lineares [u0, v0, u1, v1, ...], não direcionados) e um vértice node, e retorna a lista ordenada dos vizinhos de node, sem duplicatas.
Por exemplo, getNeighbors([0,1, 0,2, 1,2, 3,0], 0) retorna [1, 2, 3].
Experimente você mesmo
#include <stdlib.h>
int* getNeighbors(int* edges, int edges_size, int node, int* returnSize) {
// Escreva o código aqui
*returnSize = 0;
return edges;
}
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Busca em Profundidade - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity