首页 > 其他分享 >DFS查找依赖路径并按依赖层级展示生产的数据

DFS查找依赖路径并按依赖层级展示生产的数据

时间：2024-08-21 14:27:09浏览次数：3  
标签：node startNode 依赖 string DFS 层级 path append

背景

有如下场景：

// 定义结构体 dep
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找出全部的依赖路径，有间接依赖的也需要找出，并检查是否有循环依赖，依赖路径如下：

全路径依赖：
map[A:[[A F] [A B F] [A B C D E]] B:[[B F] [B C D E]] C:[[C D E B] [C D E B F]] D:[[D E B F] [D E B C]] E:[[E B F] [E B C D]]]
D:
  -> [D E B F]
  -> [D E B C]
E:
  -> [E B F]
  -> [E B C D]
A:
  -> [A F]
  -> [A B F]
  -> [A B C D E]
B:
  -> [B F]
  -> [B C D E]
C:
  -> [C D E B]
  -> [C D E B F]

根据依赖关系生成依赖数据，并记录层级关系，比如A:100 A->F的依赖系数是0.1，那么A->F这个路径计算得出F需要100*0.1=10；生成的数据如下：

// 根据依赖模型生成的依赖数据，按依赖关系生成依赖树
type DepData struct {
    ID          int     // 唯一id
    Src         string  // 源
    Depend      string  // 依赖
    RootID      int     // 根节点id
    ParentID    int     // 父节点id
    ResourceNum float64 // 依赖资源量
    Children    []*DepData
}

nodes := []*DepData{
        {ID: 1, Src: "A", RootID: 0, ParentID: 0, Depend: "B"},
        {ID: 2, Src: "B", RootID: 1, ParentID: 1, Depend: "C"},
        {ID: 3, Src: "C", RootID: 1, ParentID: 2, Depend: "D"},
        {ID: 4, Src: "B", RootID: 1, ParentID: 1, Depend: "F"},
        {ID: 5, Src: "A", RootID: 0, ParentID: 0, Depend: "F"},
        {ID: 6, Src: "F", RootID: 5, ParentID: 5, Depend: "G"},
        //...
}

需要将生成的数据按两种方式展示：
1. 根节点及其所有的子节点，两层展示

2. 根节点及其所有子节点逐层级展示，有多少层展示多少层

方案

完整实现代码如下：

package main

import (
    "fmt"
    "strings"
)

/*
如depModel所定义，src依赖Depend,可扩展依赖的具体内容，比如资源量的依赖关系，补充上依赖系数，即可根据源的资源量计算出所需依赖的资源量
依赖数据结构如下：
deps := []depModel{
        {"A", "B"},
        {"A", "F"},
        {"B", "C"},
        {"B", "F"},
        {"C", "D"},
        {"D", "E"},
        {"E", "B"}, // 这里是一个循环依赖
}
根据依赖关系生成的依赖数据结构如下：
nodes := []*DepData{
        {ID: 1, Src: "A", RootID: 0, ParentID: 0, Depend: "B"},
        {ID: 2, Src: "B", RootID: 1, ParentID: 1, Depend: "C"},
        {ID: 3, Src: "C", RootID: 1, ParentID: 2, Depend: "D"},
        {ID: 4, Src: "B", RootID: 1, ParentID: 1, Depend: "F"},
        {ID: 5, Src: "A", RootID: 0, ParentID: 0, Depend: "F"},
        {ID: 6, Src: "F", RootID: 5, ParentID: 5, Depend: "G"},
        //...
}
要生成依赖的数据，首先要从顶层找到每一个节点的依赖路径，并要检查是否有循环依赖
生成数据时需要记录根节点及父节点，然后支持按层级展示，按层级可选展示根和所有子节点两层，也可以从根节点逐层展示各层子节点
这里实现有：
1.根据依赖关系生成全部依赖路径的实现
2.检查依赖是否有环的实现
3.展示根和其所有子节点两层展示实现
4.展示根节点及逐层展示各层子节点实现
*/

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

// 非递归深度优先搜索,查找全部依赖路径,并检查是否有循环依赖, 如果不同业务依赖模型不同，且要按业务优先找模型，则使用这里的方法，生成唯一key时加上业务名
//func nonRecursiveDFSGetProductDependencePath(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
//
//        defaultNode := ""
//        if !strings.HasPrefix(node, "default") {
//            nodeList := strings.Split(node, ",")
//            defaultNode = strings.Join(append([]string{"default"}, nodeList[1:]...), ",")
//        }
//
//        if neighbors, exists := graph[node]; exists {
//            // 组件依赖其他组件
//            for _, neighbor := range neighbors {
//                //if productDependencePathContains(path, neighbor) {
//                if _, has := visited[neighbor]; has {
//                    // 检测到循环依赖,直接返回
//                    results[startNode] = append(results[startNode], append(path, neighbor))
//                    // 如果循环节点不需要记录在path里，则这里path不用加循环节点neighbor，如下:
//                    // results[startNode] = append(results[startNode], path)
//                    circularDependency := strings.Join(path, " -> ") + " -> " + neighbor
//                    log.Info("circularDependency path: %s", circularDependency)
//                    // 如果要获取所有的依赖路径，这里continue就行了，不用return
//                    // continue
//                    return true, circularDependency
//                }
//
//                newPath := append([]string{}, path...)
//                newPath = append(newPath, neighbor)
//                newVisited := copyVisitedProductDependenceNode(visited)
//                newVisited[neighbor] = true
//                stack = append(stack, stackItem{neighbor, newPath, newVisited})
//            }
//        } else if neighbors1, defaultExists := graph[defaultNode]; defaultNode != "" && defaultExists {
//            // 组件依赖其他组件
//            for _, neighbor := range neighbors1 {
//                //if productDependencePathContains(path, neighbor) {
//                if _, has := visited[neighbor]; has {
//                    // 检测到循环依赖,直接返回
//                    results[startNode] = append(results[startNode], append(path, neighbor))
//                    // 如果循环节点不需要记录在path里，则这里path不用加循环节点neighbor，如下:
//                    // results[startNode] = append(results[startNode], path)
//                    circularDependency := strings.Join(path, " -> ") + " -> " + neighbor
//                    log.Info("circularDependency path: %s", circularDependency)
//                    // 如果要获取所有的依赖路径，这里continue就行了，不用return
//                    // continue
//                    return true, circularDependency
//                }
//
//                newPath := append([]string{}, path...)
//                newPath = append(newPath, neighbor)
//                newVisited := copyVisitedProductDependenceNode(visited)
//                newVisited[neighbor] = true
//                stack = append(stack, stackItem{neighbor, newPath, newVisited})
//            }
//        } else {
//            // 组件不依赖其他组件，记录依赖路径
//            results[startNode] = append(results[startNode], path)
//        }
//    }
//    return false, ""
//}

// 非递归深度优先搜索  检查是否有循环依赖
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 CheckCircleDep() {
    // 示例输入
    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)
        }
    }

}

// 根据依赖模型生成的依赖数据，按依赖关系生成依赖树
type DepData struct {
    ID          int     // 唯一id
    Src         string  // 源
    Depend      string  // 依赖
    RootID      int     // 根节点id
    ParentID    int     // 父节点id
    ResourceNum float64 // 依赖资源量
    Children    []*DepData
}

// DepDataEveryLevelTree 按依赖关系生成依赖树,每一层之间的关系都要显示
func DepDataEveryLevelTree() {
    nodes := []*DepData{
        {ID: 1, Src: "A", RootID: 0, ParentID: 0, Depend: "B"},
        {ID: 2, Src: "B", RootID: 1, ParentID: 1, Depend: "C"},
        {ID: 3, Src: "C", RootID: 1, ParentID: 2, Depend: "D"},
        {ID: 4, Src: "B", RootID: 1, ParentID: 1, Depend: "F"},
        {ID: 5, Src: "A", RootID: 0, ParentID: 0, Depend: "F"},
        {ID: 6, Src: "F", RootID: 5, ParentID: 5, Depend: "G"},
        //...
    }

    nodeMap := mapNodesByParent(nodes)
    rootNodes := buildTree(nodeMap, 0) // 假设所有 root 节点的 ParentID = 0
    for i := range rootNodes {
        fmt.Printf("data %d tree: %v\n", i, rootNodes[i])
    }
    printNodes(rootNodes, 0)
}

func mapNodesByParent(nodes []*DepData) map[int][]*DepData {
    nodeMap := make(map[int][]*DepData)
    for _, node := range nodes {
        nodeMap[node.ParentID] = append(nodeMap[node.ParentID], node)
    }
    return nodeMap
}

func buildTree(nodeMap map[int][]*DepData, parentID int) []*DepData {
    nodes := nodeMap[parentID]
    for _, node := range nodes {
        node.Children = buildTree(nodeMap, node.ID)
    }
    return nodes
}

func printNodes(nodes []*DepData, level int) {
    for i, node := range nodes {
        if level == 0 {
            fmt.Printf("data %d tree: %v\n", i, node)
        }
        tabs := strings.Repeat("\t", level)
        fmt.Printf("%s%d, %s, %s\n", tabs, node.ID, node.Src, node.Depend)
        printNodes(node.Children, level+1)
    }
}

// DepDataTwoLevelTree 按依赖关系生成依赖树,只显示根节点和所有子节点两层之间的关系
func DepDataTwoLevelTree() {
    nodes := []*DepData{
        {ID: 1, Src: "A", RootID: 0, ParentID: 0, Depend: "B"},
        {ID: 2, Src: "B", RootID: 1, ParentID: 1, Depend: "C"},
        {ID: 3, Src: "C", RootID: 1, ParentID: 2, Depend: "D"},
        {ID: 4, Src: "B", RootID: 1, ParentID: 1, Depend: "F"},
        {ID: 5, Src: "A", RootID: 0, ParentID: 0, Depend: "F"},
        {ID: 6, Src: "F", RootID: 5, ParentID: 5, Depend: "G"},
        //...
    }

    nodeMap := mapNodesByRoot(nodes)
    rootNodes := buildTreeByRoot(nodeMap, nodes)
    for i := range rootNodes {
        fmt.Printf("data %d tree: %v\n", i, rootNodes[i])
        for _, children := range rootNodes[i].Children {
            fmt.Printf("children: %v\n", children)
        }
    }
}

func buildTreeByRoot(nodeMap map[int][]*DepData, nodes []*DepData) []*DepData {
    rootNodes := make([]*DepData, 0)
    for _, node := range nodes {
        if node.RootID == 0 {
            rootNodes = append(rootNodes, node)
        }
        node.Children = nodeMap[node.ID]
    }
    return rootNodes
}

func mapNodesByRoot(nodes []*DepData) map[int][]*DepData {
    nodeMap := make(map[int][]*DepData)
    for _, node := range nodes {
        // 根节点不记录在map中
        if node.RootID == 0 {
            continue
        }
        nodeMap[node.RootID] = append(nodeMap[node.RootID], node)
    }
    return nodeMap
}

func main() {
    CheckCircleDep()
    DepDataEveryLevelTree()
    DepDataTwoLevelTree()
}

 

标签：node,startNode,依赖,string,DFS,层级,path,append
From： https://www.cnblogs.com/276815076/p/18371508

相关文章

  • 设计模式六大原则-依赖倒置原则（五）
    设计模式六大原则之一的依赖倒置原则（DependencyInversionPrinciple,DIP）是面向对象编程中的一项重要设计原则，它强调高层模块不应该依赖于低层模块，而是应该依赖于抽象。这一原则的核心思想是面向接口编程，旨在提高软件系统的可维护性、可扩展性和可重用性。以下是对依赖倒置原......
  • mvc原理与依赖注入
    <?//模型层:当前页面要显示的数据$pdo=newPDO('mysql:host=localhost;dbname=16','root','3.1415926',[PDO::ATTR_ERRMODE=>PDO::ERRMODE_WARNING]);$users=$pdo->query('SELECT`id`,`gender`,`uname`,`c_time`FROM`user`order......
  • 欧拉回路 模版dfs stack两种版本
    stack堆栈代替dfs版本//欧拉模版.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。///**https://loj.ac/p/10105有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。一共两个子任务：这张图是无向图。（50分......
  • LeetCode-Python-3154. 到达第 K 级台阶的方案数（DFS + 数学）
    给你有一个 非负 整数 k 。有一个无限长度的台阶，最低 一层编号为0。Alice 有一个整数 jump ，一开始值为0。Alice从台阶1开始，可以使用 任意 次操作，目标是到达第 k 级台阶。假设Alice位于台阶 i ，一次 操作 中，Alice可以：向下走一级到 i-1 ，但该操作......
  • 关系代数、函数依赖、Armstrong公理及软考试题解析
    注：本文面向于软考高级—系统架构设计师，具体来说是数据库部分，知识点偏零碎化。想要系统学习数据库原理的，可考虑去看《数据库原理》，清华大学出版社或其他出版社皆可。概述概念关系，就是二维表。特性：列不可分性：关系中每一列都是不可再分的属性，即不能出现如下复合属性行列无序性：......
  • unbuntu更新Python3版本到最新，安装依赖手动编译
    安装依赖sudoaptupdatesudoaptinstallbuild-essentialzlib1g-devlibffi-devlibssl-dev下载安装包，手动配置编译官网查找对应linux版本tgz包wgethttps://www.python.org/ftp/python/3.11.0/Python-3.11.0.tgztar-xzvfPython-3.11.0.tgzcdPython-3.11.0......
  • 033、Vue3+TypeScript基础，路由传参时候把层级脱掉
    01、Datail.vue代码如下：<template><ulclass="news-list"><li>编号：{{route.query.id}}</li><li>编号：{{route.query.title}}</li><li>编号：{{route.query.content}}</li></ul></tem......
  • SpringBoot依赖之Spring Data Redis一有序集合Sorted Set
    概念SpringDataRedis(Access+Driver)依赖名称:SpringDataRedis(Access+Driver)功能描述:Advancedandthread-safeJavaRedisclientforsynchronous,asynchronous,andreactiveusage.SupportsCluster,Sentinel,Pipelining,Auto-Reconnect,Codecsand......
  • SpringBoot依赖之Spring Data Redis一集合Set
    概念SpringDataRedis(Access+Driver)依赖名称:SpringDataRedis(Access+Driver)功能描述:Advancedandthread-safeJavaRedisclientforsynchronous,asynchronous,andreactiveusage.SupportsCluster,Sentinel,Pipelining,Auto-Reconnect,Codecsand......
  • (nice!!!)LeetCode 552. 学生出勤记录 II（动态规划dp递归版、记忆化dfs）
    题目：552.学生出勤记录II思路：记忆化搜索dfs，细节看注释classSolution{public:constintmod=1e9+7;//状态f[u][a][b]表示：在选择第u个位置前，缺勤次数为a次，且当前连续迟到次数为b次时，可以得到的合法出勤次数intf[100010][5][5];intdfs(intu,int......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99