Algoritmo k-s feito em Python (usado para descobrir os CFCs de um digrafo)

k_s.py

# coisos globais
valor_profundidade_entrada = 0 # contador da profundidade em que os vertices entram da pilha (chamado recursivamente)
valor_profundidade_saida = 0 # contador da profundidade em que os vertices saem da pilha (termina sua chamada recursiva)
# dicionario com as profunfidades em que cada vertice entrou e saiu da pilha numa lista [profundidade_entrada, profundidade_saida]
profundidades_entrada_saida = {}
pai = {} # dicionario com os pais de cada vertice na arvore de busca em profundidade
aresta = {} # classificacao das arestas na arvore de busca em profundidade do grafo
niveis = {} # nivel de cada vertice na arvore de busca em profundidade
# conjunto de vertices ainda nao visitados (nunca entraram (e portanto nem sairam) da pilha)
nao_visitados = set()
# lista de arvores (floresta) da busca em profundidade
floresta = []
lista_de_vertices = []
lista_de_arestas = []

def cria_grafo(lista_de_vertices, lista_de_arestas):
    grafo = {}
    for vertice in lista_de_vertices:
        grafo[vertice] = []
    for aresta in lista_de_arestas:
        grafo[aresta[0]].append(aresta[1])
    return grafo

# funcao de chamada
def busca_em_profundidade(digrafo, vertice_do_digrafo):
    # marcando todos como nao_visitados
    for vertice in digrafo:
        nao_visitados.add(vertice)

    pai[vertice_do_digrafo] = None # a raiz naum tem pai
    lista_de_vertices[:] = [vertice_do_digrafo]
    lista_de_arestas[:] = []
    floresta.append(call_to_busca_em_profundidade(digrafo, vertice_do_digrafo, 1))

    # para garantir que todos os vertices serao visitados, precisamos recomecar a busca de vertices que nunca entraram na pilha (caso ainda existam)
    while len(nao_visitados): # enquanto naum terminar de visitar todos os vertices precisamos repetir o processo...
        vertice_do_digrafo = nao_visitados.pop() # (**) ... com uma nova raiz que seja um vertice ainda nao visitado
        pai[vertice_do_digrafo] = None
        lista_de_vertices[:] = [vertice_do_digrafo]
        lista_de_arestas[:] = []
        floresta.append(call_to_busca_em_profundidade(digrafo, vertice_do_digrafo, 1))

# funcao de chamada especial para o k-s, onde as raizes escolhidas para a arvore de profundidade a cada busca eh o vertice ainda nao visitado com a maior profundidade de saida calculada de uma busca anterior
def busca_em_profundidade_modificada(digrafo):
    profundidades_entrada_saida
    vertice_do_digrafo = ordem_profundidades_saida_old.pop()
    # print('Comecando por: %c' % vertice_do_digrafo)
    # marcando todos como nao_visitados
    for vertice in digrafo:
        nao_visitados.add(vertice)

    pai[vertice_do_digrafo] = None # a raiz naum tem pai
    lista_de_vertices[:] = [vertice_do_digrafo]
    lista_de_arestas[:] = []
    floresta.append(transpor_digrafo(call_to_busca_em_profundidade(digrafo, vertice_do_digrafo, 1)))

    # para garantir que todos os vertices serao visitados, precisamos recomecar a busca de vertices que nunca entraram na pilha (caso ainda existam)
    while len(nao_visitados): # enquanto naum terminar de visitar todos os vertices precisamos repetir o processo...
        # ... com uma nova raiz que seja um vertice ainda nao visitado
        vertice_do_digrafo = ordem_profundidades_saida_old.pop()
        while vertice_do_digrafo not in nao_visitados:
            vertice_do_digrafo = ordem_profundidades_saida_old.pop()
        # print nao_visitados
        # print('Novo vertice: %c' % vertice_do_digrafo)
        pai[vertice_do_digrafo] = None
        lista_de_vertices[:] = [vertice_do_digrafo]
        lista_de_arestas[:] = []
        floresta.append(transpor_digrafo(call_to_busca_em_profundidade(digrafo, vertice_do_digrafo, 1)))

# funcao recursiva
def call_to_busca_em_profundidade(digrafo, vertice_do_digrafo, nivel):
    global valor_profundidade_entrada, valor_profundidade_saida
    valor_profundidade_entrada += 1 # atualizando o contador de profundidade de entrada
    profundidades_entrada_saida[vertice_do_digrafo] = [valor_profundidade_entrada, None] # anotando profundidade de entrada de vertice_do_digrafo
    niveis[vertice_do_digrafo] = nivel # anotando o nivel desse vertice_do_digrafo na arvore de busca em profundidade

    # como eh certo de que um vertice_do_digrafo que entra na pilha um hora sairah dela, podemos jah marcar esse vertice_do_digrafo como visitado retirando do conjunto de nao_visitados
    nao_visitados.discard(vertice_do_digrafo) # usando o metodo discard para evitar problemas caso o pop jah tenha tirado o vertice_do_digrafo do conjunto a fim de selecionar uma nova raiz em (**)

    for vizinho in digrafo.get(vertice_do_digrafo): # percorrendo os vizinhos de vertice_do_digrafo
        # (descomente os codigos abaixo para ver a ordem em que as arestas sao visitadas e suas respectivas classificacoes)
        # print('%s -> %s:' % (str(vertice_do_digrafo), str(vizinho)))
        if not profundidades_entrada_saida.get(vizinho): # testa se esse vizinho jah foi empilhado (chamado pela recursao)
            # se ainda naum foi empilhado, eh hora de...
            pai[vizinho] = vertice_do_digrafo # ... atualizar quem eh o pai dele na arvore de busca em profundidade e...
            lista_de_vertices.append(vizinho) # ... colocar o vizinho na lista de vertices dessa arvore
            # MOMENTO PARA VISITAR vertice_do_digrafo -> vizinho COMO ARESTA DE ARVORE
            aresta[(vertice_do_digrafo, vizinho)] = 'aresta de arvore'
            lista_de_arestas.append((vertice_do_digrafo, vizinho))
            # print('aresta de arvore')
            # chamada de recursao escolhendo agora esse vizinho como raiz:
            call_to_busca_em_profundidade(digrafo, vizinho, nivel + 1) # o proximo vertice estarah um nivel abaixo desse na arvore de busca em profundidade
        else: # caso o vizinho jah esteja na pilha (jah houve uma chamada de call_to_busca_em_profundidade com parametro vertice_do_digrafo=vizinho)
            # testa se esse vizinho jah foi desempilhado (terminou sua chamada de call_to_busca_em_profundidade)
            if not profundidades_entrada_saida[vizinho][1]:
                # MOMENTO PARA VISITAR vertice_do_digrafo -> vizinho COMO ARESTA DE RETORNO
                aresta[(vertice_do_digrafo, vizinho)] = 'aresta de retorno'
                lista_de_arestas.append((vertice_do_digrafo, vizinho))
                # print('aresta de retorno')
            else: # vizinho jah foi desempilhado
                if profundidades_entrada_saida[vertice_do_digrafo][0] < profundidades_entrada_saida[vizinho][0]: # testa quem foi empilhado primeiro
                    # MOMENTO PARA VISITAR vertice_do_digrafo -> vizinho COMO ARESTA DE AVANCO
                    aresta[(vertice_do_digrafo, vizinho)] = 'aresta de avanco'
                    lista_de_arestas.append((vertice_do_digrafo, vizinho))
                    # print('aresta de avanco')
                else: # vertice_do_digrafo foi empilhado e desempilhado antes de vizinho ser empilhado
                    # MOMENTO PARA VISITAR vertice_do_digrafo -> vizinho COMO ARESTA DE CRUZAMENTO
                    aresta[(vertice_do_digrafo, vizinho)] = 'aresta de cruzamento'
                    # print('aresta de cruzamento')

    valor_profundidade_saida += 1 # atualizando o contador de profundidade de saida
    profundidades_entrada_saida[vertice_do_digrafo][1] = valor_profundidade_saida

    return cria_grafo(lista_de_vertices, lista_de_arestas)

# transpor um digrafo significa inverter a direção de todas as suas arestas, esse algoritmo faz isso com complexidade O(n+m) (O(2n+m), caso prefira ser mais preciso... (coisa que a propria notacao O deveria ter ensinado a "negligenciar"))
def transpor_digrafo(digrafo):
    digrafo_t = {}
    for vertice in digrafo:
        digrafo_t[vertice] = []
    for vertice in digrafo:
        for vizinho in digrafo[vertice]:
            digrafo_t[vizinho].append(vertice)
    return digrafo_t
# lista de vertices ordenados pelos seus graus de profundidade de saida da ultima busca_em_profundidade
ordem_profundidades_saida_old = []

def copiar_profundidades_de_saida_em_ordem():
    # print profundidades_entrada_saida
    profundidades_invertido = {v[1]: k for k, v in profundidades_entrada_saida.items()}
    # print profundidades_invertido
    for profundidade_saida in xrange(1, valor_profundidade_saida + 1):
        ordem_profundidades_saida_old.append(profundidades_invertido[profundidade_saida])
    # print ordem_profundidades_saida_old

def limpar_globais():
    global valor_profundidade_entrada, valor_profundidade_saida
    valor_profundidade_entrada = 0
    valor_profundidade_saida = 0
    profundidades_entrada_saida.clear()
    pai.clear()
    aresta.clear()
    niveis.clear()
    floresta[:] = []
    lista_de_vertices[:] = []
    lista_de_arestas[:] = []

# O algoritmo k-s (Kosaraju-Sharir) eh capaz de retornar todos os componentes fortemente conexos (CFCs) de um digrafo. Ele se aproveita do fato que os CFCs de um digrafo D sao iguais aos CFCs transpostos de D_t, onde D_t eh o digrafo transposto de D
def k_s(digrafo):
    busca_em_profundidade(digrafo, digrafo.keys()[0])
    digrafo_t = transpor_digrafo(digrafo)
    copiar_profundidades_de_saida_em_ordem()
    limpar_globais()
    busca_em_profundidade_modificada(digrafo_t)





digrafo = {
    'a': ['c', 'd', 'f'],
    'b': ['a'],
    'c': ['b'],
    'd': ['e', 'f'],
    'e': [],
    'f': ['e']
}

k_s(digrafo)