G = (V,E) directed acyclic graph $\iff$G hasn’t directed cycles.
modify DFS to check if G is acyclic.
def func (G)
vis = [0,0,0,0,…,0] //$O(n)$
stack = {}
x = random(V(G))
stack.push(x)
while stack is not empty:
y = stack.top()
if y.adjacent_out[0] == 0:
stack.push(y.adjacent_out[0])
vis[y.adjacent_out[0]] = 1
else:
if y.adjacent_out[0] == 1 $\land$ stack.length ≥ 1:
return true
y.adjacent_out.remove(0)
if y.adjacetn_out == []:
stack.pop()
return false
Incorrect
exercise2)
G is non-directed graph, G=(V,E) bipartite if:
V = U (UNION) W
V$\cap$U = {}
$\forall$ (u,v) $\in$ E(G), u $\in$ U, v $\in$ W
modify dfs to check if G is a bipartite graph.
G is bipartite $\iff$ G hasn’t odd cycle.
def func (G,list = [])
vis = [0,0,0,…,0] //initialize a list of N elements set at 0
x = random(V(G)) //select a random node
counter = 0
stack = {}
stack.push(x)
counter = 1
while stack is not empty:
current = stack.top
if (vis[current.adjacent[0]] == 0):
z = current.adjacent[0]
vis[z] = 1
stack.push(z)
counter ++
else:
if vis[z] == 1 $\land$ counter % 2 == 1:
return true
current.adjacent.remove(0)
if current.adjacent == []:
stack.pop
counter -= 1
return false
incorrect
def func (G)
vis = [0,…,0]
part = vis.copy()
vis[x] = 1
parità = 1
part[x] = 1
S = new Stack
S.push(x)
while S is not empty
y=S.top()
if(vis[y.adjacent[0] == 0)
z = y.adjacent[0]
parità *=-1
vis[z] = 1
part[z] = parità
S.push(z)
y.adjacent.remove(0)
else:
y.adjacent.remove(0)
if y.adjacent == []
S.pop()
for each (v,u) $\in$ E(G)
if (part[u] == part[v]
return false
return true
correct (?)
exercise 3)
this path (not 0 nodes) is possible starting dfs from random node
no, unless (E,B) is removed from not 0 nodes list and (C,B) is added to not 0 nodes list and dfs start from D.