Monte o grafo, escolha o algoritmo e acompanhe cada passo da execução.
Um laboratório visual para aulas e monitorias. Desenhe vértices e arestas direcionadas ou não direcionadas, defina pesos e execute os métodos clássicos da disciplina na mesma notação usada em sala, com tabelas, filas e a justificativa de cada iteração.
Edição direta no canvas
Crie vértices com um clique, conecte-os e ajuste pesos e direção sem sair da tela.
Direcionado, não direcionado ou misto
Cada aresta guarda sua própria orientação. Os algoritmos validam o tipo de grafo exigido antes de executar.
Traço passo a passo
Filas, pilhas, tabelas de dist e pred e matrizes de distância acompanham a animação em cada iteração.
Da busca em grafos à coloração, na ordem da disciplina
Cada execução gera um traço completo: marcação dos vértices, tabelas auxiliares e a justificativa de cada decisão.
Busca em Profundidade
O(n + m)Escolhe sempre o vértice marcado mais recentemente alcançado, registrando tempo de descoberta TD e tempo de término TT.
Busca em grafos
Busca em Largura
O(n + m)Escolhe sempre o vértice marcado menos recentemente alcançado, usando uma fila, e define o nível de cada vértice.
Busca em grafos
Método de Kosaraju
O(n + m)Encontra os componentes fortemente conexos (f-conexos) com duas buscas em profundidade: uma em G e outra no grafo reverso Gᴿ.
Conectividade
Método de Fleury
O(m² )Constrói um trajeto euleriano caminhando pelo grafo e evitando atravessar uma ponte enquanto houver outra aresta disponível.
Grafos eulerianos
Método de Prim
O(m log n)Inclui vértices um a um: a cada passo acrescenta a aresta de menor peso entre V(T) e os vértices ainda não selecionados.
Árvore geradora mínima
Método de Kruskal
O(m log m)Inclui arestas, e não vértices: ordena as arestas por peso não decrescente e aceita cada uma que não forme ciclo com as já inseridas em E(T).
Árvore geradora mínima
Método de Dijkstra
O(n²)"Fecha" um vértice por iteração, sempre o de menor dist, e relaxa as arestas tensas que saem dele.
Caminho mínimo
Método de Bellman-Ford
O(n · m)Programação dinâmica: examina todas as arestas a cada iteração, relaxando as que estiverem tensas, por |V(G)| − 1 iterações.
Caminho mínimo
Método de Floyd-Warshall
O(n³)Caminhos mínimos entre todos os pares por programação dinâmica: a rodada k libera o vértice k como intermediário.
Caminho mínimo
Método de Ford-Fulkerson
O(m · f) com capacidades inteirasEnquanto existir algum caminho aumentante em G'(f), envia por ele o gargalo δ e atualiza a rede residual.
Fluxo máximo
Método de Edmonds-Karp
O(n · m² )Implementação eficiente de Ford-Fulkerson: a cada iteração escolhe o caminho aumentante mais curto, obtido por busca em largura.
Fluxo máximo
Método de Dinic
O(n² · m)A cada iteração constrói a rede em níveis GL a partir de G′(f) e determina nela um fluxo de bloqueio.
Fluxo máximo
Método de Kahn
O(n + m)Determina a cada instante um vértice com grau de entrada zero, insere-o no fim do resultado e reduz o grau de entrada de seus sucessores.
Ordenação topológica
Ordenação topológica por busca em profundidade
O(n + m)Descrito por Tarjan em 1976: insere cada vértice no início do resultado somente depois de visitar todos os que dependem dele.
Ordenação topológica
Método de Edmonds
O(n² · m)Busca caminhos M-aumentantes entre vértices expostos, contraindo os botões (blossoms) que aparecem, até que não exista mais nenhum.
Emparelhamento
Método guloso
O(n + m)Percorre os vértices em uma ordem qualquer e atribui a cada um a cor de menor índice não utilizada por nenhum de seus vizinhos.
Coloração
Método de Welsh-Powell
O(n² )Ordena os vértices em ordem não crescente de graus e colore, com uma mesma cor, todos os que não estiverem conectados a um vértice já colorido com ela.
Coloração