dfs

#--- LEZIONE 24 (19 maggio 2020)  ---
#--- DFS Visita in profondità di un grafo

#--- CREA GRAFO ---

inf = float("inf")

def createGraph(n):
    G = []
    for i in range(n):
        G.append([])
    return G

def size(G):
    return len(G)

def printGraph(G):
    for i in range(len(G)):
        print(G[i])

#--- theta(1) ---
def insert(G,i,j,w):
    if not isEdge(G,i,j):
        G[i].append([j,w])

#--- theta(n) ---
def delete(G,i,j):
    for k in range(len(G[i])):
        if G[i][k][0] == j:
            G[i].pop(k)

#--- theta(n) ---
def isEdge(G,i,j):
    for k in range(len(G[i])):
        if G[i][k][0] == j:
            return True
    return False

#--- theta(n) ---
def weight(G,i,j):
    for k in range(len(G[i])):
        if G[i][k][0] == j:
            return G[i][k][1]
    return inf

def outDegree(G,i):
    return len(G[i])

#--- theta(1) ---
def neighbors(G,i):
    return G[i]

#--- theta(n) ---
def neighborsCopy(G,i):
    V = []
    for [j,w] in G[i]:
        V.append(j)
    return V

#---------- Programma principale ------------

G = createGraph(10)

insert(G, 0, 1, 1)
insert(G, 0, 4, 1)
insert(G, 0, 5, 1)
insert(G, 1, 2, 1)
insert(G, 2, 3, 1)
#insert(G, 3, 1, 1)
insert(G, 4, 5, 1)
insert(G, 4, 6, 1)
insert(G, 4, 7, 1)
insert(G, 4, 8, 1)
insert(G, 6, 5, 1)
insert(G, 7, 8, 1)
insert(G, 8, 9, 1)
insert(G, 9, 7, 1)

print("")
print("--- Grafo (Lista di Adiacenza) ---")
printGraph(G)

def DFS(Graph,source):
    n = size(Graph)
    reached = []
    for i in range(n):
        reached.append(False)
    reached[source] = True          ## apparecchio le variabili, dicendo che source
    Tree = []                       ## è stata visitata
    DFSV(Graph,source,reached,Tree)
    return Tree

def DFSV(Graph,k,reached,Tree):
    V = neighbors(Graph,k)
    for [j,w] in V:
        if reached[j] == False:
            reached[j] = True
            Tree.append([k,j])
            DFSV(Graph,j,reached,Tree)

print("")
print("DFS: ", DFS(G,0))