-1

Implemente um algoritmo que carregue um grafo direcionado e em seguida execute o algoritmo DFS no grafo carregado.

  1. 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;
  2. 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.
  3. 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)

1 Resposta 1

0

Foi ordenado de forma decrescente a lista com a maior quantidade de elementos seja primeiro além de sua ordem de execução.

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()
    ordenado = []

    for numero in lista_adj:
        for chave, valor in enumerate(ordenado):
            if len(numero) > len(valor):
                ordenado.insert(chave, numero)
                break
        else:
            ordenado.append(numero)

    return ordenado, N


def DFS_visit(u):
    global mark, cor, d, f
    cor[u] = "Cinza"
    mark = mark + 1
    d[u] = mark
    for v in lista_adj[u]:
        if cor[v] == "Branco":
            print("Aresta (", u+1, v+1, "): Arvore")
            DFS_visit(v)
        elif cor[v] == "Cinza":
            print("Aresta (", u+1, v+1, "): Retorno")
        elif d[u] < f[v]:
            print("Aresta (", u+1, v+1, "): Avanco")
        else:
            print("Aresta (", u+1, v+1, "): Cruzamento")

    cor[u] = "Preto"
    mark = mark + 1
    f[u] = mark


def DFS():
    global mark, cor, d, f
    V = list(range(0, N))
    cor = ["Branco"]*N
    d = [0]*N
    f = [0]*N
    for u in V:
        cor[u] = "Branco"
    mark = 0
    for u in V:
        if cor[u] == "Branco":
            DFS_visit(u)


[lista_adj, N] = loadlista()
DFS()

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .