Gio 22 Agosto, 17:50:02 - 2019

Autore Topic: connessione forte  (Letto 416 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
connessione forte
« il: Gio 29 Giugno, 19:53:54 - 2017 »
Sono incappato in un esercizio sui grafi che chiede: Dato in input un grafo G, determinare se G è fortemente connesso. Posto lo pseudocodice della soluzione che penso risolva il problema. Ovviamente non sono sicuro della correttezza. In pratica quello che faccio è partire da un vertice qualunque e faccio la visita. Nella visita utilizzo un contatore cont che mi tiene conto dei nodi effettivamente visitati. Se non li visito tutti, non è fortemente connesso, altrimenti calcolo il grafo G1 invertendo gli archi con reverseDirection() (questo metodo sta nel libro di testo :D) e faccio la stessa cosa con il grafo G1. Ripeto, è una mia personale soluzione, di cui non sono sicuro della correttezza di cio che ho scritto.

Algoritmo isFortementeConnesso( Grafo G)
Input: Sia G grafo
Output: true se è fortemente connesso, false altrimenti

    for all u in G.vertices()
        setLabel(u, UNEXPLORED)
    for all e ? G.edges()
        setLabel(e, UNEXPLORED)
    Sia x in G.vertices() // vertice di partenza da cui parte la visita
    int cont=0 // conta il numero di vertici visitati
    D-DFS(G, x, cont)
    if( cont+1 != G.vertices().size)
        return false;
    G1 = G.reverseDirection() // metodo che inverte i lati del grafo G
    cont = 0;
    D-DFS(G1, x, cont);
    if( cont+1 != G.vertices().size)
        return false;

    return true;

Algoritmo D-DFS(G, v, cont)
Input: Grafo G, vertice v, cont valore intero

    setDiscoveryLabel(v, getNextDLabel());
    for all e in outgoingEdges(v)
        if(getLabel(e) == UNEXPLORED)
        w = opposite(e, v)
        if(getDiscoveryLabel(w)==UNEXPLORED)
            setLabel(e, DISCOVERY)
            D-DFS(G, w, cont+1)
        else if(getLeavingLabel(w) == 0)
            setLabel(e, BACK)
        else if(getDiscoveryLabel(v)<getDiscoveryLabel(w))
            setLabel(e, FORWARD)
        else setLabel(e, CROSS)
    setLeavingLabel(v, getNextLLabel())
« Ultima modifica: Gio 29 Giugno, 20:01:21 - 2017 da scheggia89 »