Algoritmi su grafi

di il
2 risposte

Algoritmi su grafi

Salve, propongo un codice utilizzato per approcciare un quesito sui grafi: funzione per determinare se un grafo avente tre nodi è bipartito o no (dati due sottoinsiemi di nodi, i nodi di un sottoinsieme devono essere collegati esclusivamente a quelli dell'altro sottoinsieme):
#diamo in ingresso un grafo di tre nodi e una sorgente
def isBipartite(G,src):
   colorArr = [-1] * len(G)
   colorArr[src] = 1
   coda = []
   coda.append(src)
   while coda:
       u = coda.pop()
       if isEdge(G,u,u):
            return False;
       for v in range(len(G)):
            if isEdge(G,u,v) and colorArr[v] == -1:
                  colorArr[v] = 1 - colorArr[u]
                  coda.append(v)
            elif isEdge(G,u,v) and colorArr[v] == colorArr[u]:
                  return False
    return True
Le funzioni per la costruzione del grafo e il metodo isEdge (presenza di archi) sono stati precedentemente definiti. L'algoritmo che ho utilizzato approccia il problema chiedendosi se il grafo è 2-colorabile. Il passaggio che non mi è ben chiaro è quello dove inseriamo coda.append(v). Perché è necessario farlo? il ciclo while viene ripetuto con v?

2 Risposte

  • Re: Algoritmi su grafi

    Salve,
    Da quello che ho capito dal codice...
    Sì, il while viene ripetuto con v per analizzare ed elaborare eventuali "sotto-elementi".
  • Re: Algoritmi su grafi

    Il grafo da analizzare ha 3 nodi (0,1 e 2) ed è bipartito in quanto i nodi 1 e 2 non sono collegati tra di loro. Ho utilizzato due tipi di colore in modo tale da avere due sottoinsiemi: se esiste un arco che collega una coppia di nodi e i nodi hanno colori diversi, allora il grafo è bipartito, se un nodo invece è collegato ad un nodo dello stesso colore allora il grafo non è bipartito. Partendo da un nodo src in input, è corretto dire che il for dovrebbe servire a colorare i due nodi diversi da src di un colore alternativo?
    Il while, dopo la prima iterazione, va a ciclare avendo in coda i due nodi v con colore diverso da src?
Devi accedere o registrarti per scrivere nel forum
2 risposte