背景:
有如下场景:
// 定义结构体 dep,表示 Src依赖Depend type depModel struct { Src string `json:"src"` // 源 Depend string `json:"depend"` // 依赖 } // 示例输入 deps := []depModel{ {"A", "B"}, {"A", "F"}, {"B", "C"}, {"B", "F"}, {"C", "D"}, {"D", "E"}, {"E", "B"}, // 这里是一个循环依赖 }
需要根据deps找出全部的依赖路径,有间接依赖的也需要找出,并检查是否有循环依赖。
方案
使用DFS来进行查找
实现逻辑如下:
package main import ( "fmt" "strings" ) // 定义结构体 dep type depModel struct { Src string `json:"src"` Depend string `json:"depend"` } // 构建依赖图 func buildGraph(deps []depModel) map[string][]string { graph := make(map[string][]string) for _, d := range deps { graph[d.Src] = append(graph[d.Src], d.Depend) } return graph } // 非递归深度优先搜索 func nonRecursiveDFS(graph map[string][]string, startNode string, results map[string][][]string) { type stackItem struct { node string // 当前节点 path []string // 记录当前节点依赖路径 visited map[string]bool // 记录访问节点 } stack := []stackItem{{startNode, []string{startNode}, map[string]bool{startNode: true}}} for len(stack) > 0 { item := stack[len(stack)-1] stack = stack[:len(stack)-1] node := item.node path := item.path visited := item.visited if neighbors, exists := graph[node]; exists { for _, neighbor := range neighbors { if _, has := visited[neighbor]; has { // 检测到循环依赖 //results[startNode] = append(results[startNode], append(path, neighbor)) // 如果循环依赖的节点不需要在路径中,path不要添加当前节点即可,如下: results[startNode] = append(results[startNode], path) continue } newPath := append([]string{}, path...) newPath = append(newPath, neighbor) newVisited := copyVisited(visited) newVisited[neighbor] = true stack = append(stack, stackItem{neighbor, newPath, newVisited}) } } else { results[startNode] = append(results[startNode], path) } } } // 非递归深度优先搜索 func nonRecursiveDFSCheckCircle(graph map[string][]string, startNode string, results map[string][][]string) (bool, string) { type stackItem struct { node string // 当前节点 path []string // 记录当前节点依赖路径 visited map[string]bool // 记录访问节点 } stack := []stackItem{{startNode, []string{startNode}, map[string]bool{startNode: true}}} for len(stack) > 0 { item := stack[len(stack)-1] stack = stack[:len(stack)-1] node := item.node path := item.path visited := item.visited if neighbors, exists := graph[node]; exists { for _, neighbor := range neighbors { if _, has := visited[neighbor]; has { // 检测到循环依赖 results[startNode] = append(results[startNode], append(path, neighbor)) circularDependency := strings.Join(path, " -> ") + " -> " + neighbor // 如果循环依赖的节点不需要在路径中,path不要添加当前节点即可,如下: //results[startNode] = append(results[startNode], path) return true, circularDependency } newPath := append([]string{}, path...) newPath = append(newPath, neighbor) newVisited := copyVisited(visited) newVisited[neighbor] = true stack = append(stack, stackItem{neighbor, newPath, newVisited}) } } else { results[startNode] = append(results[startNode], path) } } return false, "" } // 检查路径中是否包含节点 func pathContains(path []string, node string) bool { for _, n := range path { if n == node { return true } } return false } // 复制访问节点记录 func copyVisited(visited map[string]bool) map[string]bool { newVisited := make(map[string]bool) for k, v := range visited { newVisited[k] = v } return newVisited } func findDependencies(deps []depModel) map[string][][]string { graph := buildGraph(deps) Results := make(map[string][][]string) for node := range graph { nonRecursiveDFS(graph, node, Results) } return Results } func HasCircleDep(deps []depModel) (bool, string) { graph := buildGraph(deps) Results := make(map[string][][]string) for node := range graph { hasCircle, circlePath := nonRecursiveDFSCheckCircle(graph, node, Results) if hasCircle { return hasCircle, circlePath } } return false, "" } func main() { // 示例输入 deps := []depModel{ {"A", "B"}, {"A", "F"}, {"B", "C"}, {"B", "F"}, {"C", "D"}, {"D", "E"}, {"E", "B"}, // 这里是一个循环依赖 } // 检查是否有循环依赖 hasCircle, circlePath := HasCircleDep(deps) if hasCircle { fmt.Println("存在循环依赖:", circlePath) } else { fmt.Println("没有循环依赖") } // 调用 findDependencies 函数,获取全路径依赖 results := findDependencies(deps) // 输出结果 fmt.Println("全路径依赖:") fmt.Println(results) for src, paths := range results { fmt.Printf("%s:\n", src) for _, path := range paths { fmt.Printf(" -> %v\n", path) } } }
标签:startNode,string,map,路径,results,DFS,查找,path,stack From: https://www.cnblogs.com/276815076/p/18350548