forked from spring1843/go-dsa
-
Notifications
You must be signed in to change notification settings - Fork 0
/
is_dag.go
28 lines (26 loc) · 600 Bytes
/
is_dag.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package graph
// IsDAG solves the problem in O(V+E) time and O(V) space.
func IsDAG(graph []*Vertex) bool {
for _, vertex := range graph {
visited := make(map[*Vertex]struct{})
visited[vertex] = struct{}{}
if hasCycle(vertex, visited) {
return false
}
}
return true
}
func hasCycle(vertex *Vertex, visited map[*Vertex]struct{}) bool {
for _, neighbor := range vertex.Edges {
if _, ok := visited[neighbor]; !ok {
visited[neighbor] = struct{}{}
if hasCycle(neighbor, visited) {
return true
}
delete(visited, neighbor)
} else {
return true
}
}
return false
}