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?