Implemente um algoritmo que carregue um grafo direcionado e em seguida execute o algoritmo DFS no grafo carregado.
- Você pode armazenar o grafo na estrutura de dados que desejar;
a. Use precedência alfabética/numérica para armazenar os dados do grafo; - O DFS deve iniciar pelo vértice que tem maior grau de saída;
a. Caso precise reiniciar o DFS, escolha o vértice que tem o segundo maior grau de saída, depois o terceiro e assim por diante. - O seu algoritmo deve imprimir na tela a nomenclatura de todas as arestas (Aresta de Árvore, Aresta de Retorno, Aresta de Avanço ou Aresta de Cruzamento) do grafo carregado de acordo com o DFS executado.
def imprime(d, f, N):
for i in range(N):
print("Vertice ", i+1, "->", d[i], f[i])
def loadlista():
arquivo = open('grafo.txt', 'r')
lista = arquivo.readlines() # ler todas as linhas e salva em lista
for i in range(len(lista)):
linha = lista[i].split()
if i == 0:
N = int(linha[0])
lista_adj = [[] for _ in range(N)] # criando uma lista de lista
Ori = linha[2]
else:
if Ori == "D":
lista_adj[int(linha[0])-1].append(int(linha[1])-1)
else:
lista_adj[int(linha[0])-1].append(int(linha[1])-1)
lista_adj[int(linha[1])-1].append(int(linha[0])-1)
arquivo.close()
L = []
n = 0
numero = lista_adj[0+n]
for chave, valor in enumerate(lista_adj):
if len(numero) < len(valor):
L.insert(chave, numero)
break
else:
L.append(numero)
n+=1
print("Lista atual:", L)
return L, N
def DFS_visit(u):
global cor, d, f
cor[u] = "Cinza"
# d[u] =
f[u] = "arvore"
for v in lista_adj[u]:
d[u] = v
if cor[v] == "Branco":
DFS_visit(v)
cor[u] = "Preto"
def DFS():
global cor, d, f
V = list(range(0, N))
cor = ["Branco"]*N
d = [0]*N
f = [0]*N
for u in V:
cor[u] = "Branco"
for u in V:
if cor[u] == "Branco":
DFS_visit(u)
[lista_adj, N] = loadlista()
DFS()
imprime(d, f, N)