DFS查找依赖路径

背景：

有如下场景:

// 定义结构体 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)
        }
    }

}