Golang实现：如何计算节点间跳数及检测连通性

需求说明 #

现有n个节点，每个节点最多可拥有m条连接，模拟场景中为每个节点随机分配至多m条连接。需要实现：

• 计算任意两个节点之间的最短跳数（例如n=10时，需计算所有节点对如n1→n2、n1→n5的跳数）
• 检测是否存在节点间无法连通的情况

原代码问题 #

你提供的原代码仅能检测直接连接的节点对，且未找到连接时的逻辑存在错误，无法处理间接连接的情况，也无法判断节点是否连通：

type node struct {
    id int
    connections map[int]*node
}

func calc() {
   for n := 0; n < len(nodes); n++ {
    
    NEXT:
      for target := 0; target < len(nodes); target++ {
        if target == n {
          continue // 跳过自身连接
        }
        for i := range nodes[n].connections {
          if i == target {
            fmt.Printf("%d to %d has %d hops\n", n, target, count)
            count = 0 
            break NEXT
          }
          count++
        }
      }
    }
}

正确实现方案 #

要解决这个问题，应该使用**广度优先搜索（BFS）**算法，因为BFS天然适合寻找无权图中的最短路径（跳数），同时可以通过遍历记录判断节点是否连通。以下是完整的实现代码：

package main

import (
    "fmt"
    "container/list"
)

type node struct {
    id          int
    connections map[int]*node
}

// 全局节点列表，假设已完成初始化
var nodes []*node

func calc() {
    // 遍历所有节点对
    for startIdx := 0; startIdx < len(nodes); startIdx++ {
        startNode := nodes[startIdx]
        for targetIdx := 0; targetIdx < len(nodes); targetIdx++ {
            if startIdx == targetIdx {
                fmt.Printf("%d to %d has 0 hops（自身）\n", startNode.id, nodes[targetIdx].id)
                continue
            }
            // 使用BFS计算最短跳数并检测连通性
            hops, reachable := calculateShortestHops(startNode.id, nodes[targetIdx].id)
            if reachable {
                fmt.Printf("%d to %d has %d hops\n", startNode.id, nodes[targetIdx].id, hops)
            } else {
                fmt.Printf("%d to %d 无法连通\n", startNode.id, nodes[targetIdx].id)
            }
        }
    }
}

// calculateShortestHops 计算从startId到targetId的最短跳数，返回跳数和是否可达
func calculateShortestHops(startId, targetId int) (int, bool) {
    // 记录已访问的节点，避免重复遍历
    visited := make(map[int]bool)
    // 队列存储节点ID和当前跳数
    queue := list.New()
    queue.PushBack(struct{ id, hops int }{id: startId, hops: 0})
    visited[startId] = true

    for queue.Len() > 0 {
        elem := queue.Front()
        queue.Remove(elem)
        current := elem.Value.(struct{ id, hops int })

        // 遍历当前节点的所有邻居
        for neighborId := range nodes[current.id].connections {
            if neighborId == targetId {
                return current.hops + 1, true
            }
            if !visited[neighborId] {
                visited[neighborId] = true
                queue.PushBack(struct{ id, hops int }{id: neighborId, hops: current.hops + 1})
            }
        }
    }
    // 队列为空仍未找到目标，说明无法连通
    return 0, false
}

代码关键点说明 #

• BFS遍历逻辑：从起始节点开始，按层级遍历所有可达节点，第一次到达目标节点时的层级就是最短跳数
• 访问标记：用visited map记录已访问的节点，防止循环遍历和重复计算
• 连通性检测：如果遍历完所有可达节点仍未找到目标，说明两个节点处于不同的连通分量，无法连通

内容的提问来源于stack exchange，提问作者phetherer