我正在尝试使用DFS通过检查图中的每个节点是否有循环来检查图中的循环。
我想为每个节点运行一个例程，并在检测到第一个周期或没有周期时终止。
当检测到第一个周期时终止似乎很好，但是当没有更多的节点时，我遇到了麻烦。
下面是一个似乎工作的实现，但对我来说看起来很糟糕，我正在寻找一个更好的实现。实际上，我使用缓冲通道，每次没有得到循环时增加计数器，并在计数器达到底层图的大小时终止。
使用计数器来确定何时完成对我来说似乎不习惯。或者，更确切地说，如果在Go中有一种更习惯的方法来做到这一点，那就太好了。
func (c *cycleDet) hasCycle() bool {
adj := c.b // adjacency list representation of the unerlying graph
hasCycles := make(chan bool, len(adj))
for node := range adj {
go func(no nodeID, co chan<- bool) {
visited := make(map[nodeID]struct{})
// c.nodeHasCycle will use a recursive implementation of DFS to
// find out if the node no leads to a cycle.
if c.nodeHasCycle(no, visited) {
co <- true
return
}
co <- false
}(node, hasCycles)
}
var i int
for {
select {
case v := <-hasCycles:
if v {
fmt.Println("got cycle")
return true
}
if i == len(c.b) {
return false
}
i++
}
}
}
我还看到另一篇推荐使用"观察者"的帖子。goroutine(虽然我找不到SO帖子)。我不确定那会是什么样子，但想象一下它会像这样与WaitGroup混合:
func (c *cycleDet) hasCycle() bool {
hasCycle := make(chan bool)
done := make(chan struct{})
var wg sync.WaitGroup
adj := c.b // adjacency list representation of the unerlying graph
for node := range adj {
go func(no nodeID, co chan<- bool) {
// Use wg to synchronize termination of read-only goroutines.
wg.Add(1)
defer wg.Done()
visited := make(map[nodeID]struct{})
// c.nodeHasCycle will use a recursive implementation of DFS to
// find out if the node no leads to a cycle.
if c.nodeHasCycle(no, visited) {
co <- true
return
}
}(node, hasCycle)
}
// Observer goroutine to notify when wg is done waiting.
time.Sleep(100 * time.Millisecond)
go func() {
wg.Wait()
done <- struct{}{}
}()
select {
case <-hasCycle:
fmt.Println("got a cycle")
return true
case <-done:
fmt.Println("no cycle detected")
return false
}
}
然而，这种方法让我担心，因为我需要睡眠，以便观察者只在第一个WaitGroup计数器增加后才开始等待，这似乎比第一个解决方案要脆弱得多。
你是正确的，WaitGroup可能是你想要的。但是，你没有正确地使用它。首先，需要在调用wg.Done()的go例程之外调用wg.Add(1)。其次，调用wg.Wait()阻塞，直到等待组中的所有go例程完成执行，所以您不希望它并发执行。
至于短路，并没有一个很好的方法。我的建议是使用上下文。在这种情况下，如果你想要真正的短路行为，你必须做的一件事是将上下文连接到nodeHasCycle的调用中。
修复你的代码，我们有:
func (c *cycleDet) hasCycle() bool {
ctx, cancel := context.WithCancel(context.Background())
hasCycle := make(chan bool)
var wg sync.WaitGroup
adj := c.b // adjacency list representation of the unerlying graph
for node := range adj {
wg.Add(1)
go func(ctx context.Context, no nodeID, co chan<- bool, cancel context.CancelFunc) {
// Use wg to synchronize termination of read-only goroutines.
defer wg.Done()
select {
case <-ctx.Done():
return
default:
}
visited := make(map[nodeID]struct{})
// c.nodeHasCycle will use a recursive implementation of DFS to
// find out if the node no leads to a cycle.
if c.nodeHasCycle(ctx, no, visited) {
co <- true
cancel()
return
}
}(ctx, node, hasCycle, cancel)
}
// Observer goroutine to notify when wg is done waiting.
time.Sleep(100 * time.Millisecond)
wg.Wait()
defer cancel()
select {
case <-hasCycle:
fmt.Println("got a cycle")
return true
default:
fmt.Println("no cycle detected")
return false
}
}
通过这种方式设置，您可以确保所有对go-routine的调用都将运行，除非找到循环，在这种情况下，不会调用额外的go-routes，并且，如果您在nodeHasSycle中添加检查取消的逻辑，那么您可以停止对它的任何运行调用的执行。