精华内容
下载资源
问答
  • 算法题解:寻找有向无环图中的最长路径(JAVA+动态规划)
    千次阅读
    2019-07-11 21:21:15

    寻找有向无环图中的最长路径(JAVA+动态规划)

    给出了一个具有n个顶点和m个边的有向图G。任务是找出图中最长有向路径的长度。

    注:有向路径的长度是指路径中的边数。

    例如:下图中有4个顶点,5条边。

    最长的有向路径的长度为 3。

    从1到3,到2,到4。


    算法实现

    package com.bean.algorithm.graph;
    
    import java.util.ArrayList;
    
    public class LongestPathDirectedAcyclicGraph {
    	
    	int vertices;
    	ArrayList<Integer> edge[];
    
    	LongestPathDirectedAcyclicGraph(int vertices) {
    		this.vertices = vertices;
    		edge = new ArrayList[vertices + 1];
    		for (int i = 0; i <= vertices; i++) {
    			edge[i] = new ArrayList<>();
    		}
    	}
    
    	void addEdge(int a, int b) {
    		edge[a].add(b);
    	}
    
    	void dfs(int node, ArrayList<Integer> adj[], int dp[], boolean visited[]) {
    		// 标记访问过的结点
    		visited[node] = true;
    
    		// 遍历所有子节点
    		for (int i = 0; i < adj[node].size(); i++) {
    
    			// 如果没有访问过
    			if (!visited[adj[node].get(i)])
    				dfs(adj[node].get(i), adj, dp, visited);
    
    			// 存储最长路径
    			dp[node] = Math.max(dp[node], 1 + dp[adj[node].get(i)]);
    		}
    	}
    
    	// 返回最长路径
    	int findLongestPath(int n) {
    		ArrayList<Integer> adj[] = edge;
    		// 开辟DP数组
    		int[] dp = new int[n + 1];
    
    		//访问数组来确认之前的结点是否被访问过 
    		boolean[] visited = new boolean[n + 1];
    
    		// 对没有访问过的结点采用DFS算法
    		for (int i = 1; i <= n; i++) {
    			if (!visited[i])
    				dfs(i, adj, dp, visited);
    		}
    
    		int ans = 0;
    
    		// 遍历和寻找所有最大的dp[i]
    		for (int i = 1; i <= n; i++) {
    			ans = Math.max(ans, dp[i]);
    		}
    		return ans;
    	}
    
    	// Driver code
    	public static void main(String[] args) {
    		int n = 5;
    		LongestPathDirectedAcyclicGraph graph = new LongestPathDirectedAcyclicGraph(n);
    		// Example-1
    		graph.addEdge(1, 2);
    		graph.addEdge(1, 3);
    		graph.addEdge(3, 2);
    		graph.addEdge(2, 4);
    		graph.addEdge(3, 4);
    		graph.findLongestPath(n);
    		System.out.println(graph.findLongestPath(n));
    
    	}
    }
    

    程序运行结果:

    3

     

    更多相关内容
  • 有向图java程序

    2020-05-03 10:58:15
    有向图寻找java语言,文件读入为两个节点之间进行连接的数据,输出为长度为3到7的收尾相连的链,多次使用arraylist运行速度较慢。
  • NULL 博文链接:https://128kj.iteye.com/blog/1675685
  • * @Description:判断无向图是否有环 深度优先遍历 * 需要保存父节点 * @Create 2020-04-03 21:04 * @Email:1173748742@qq.com */ public class IsHaveLoop { public static void main(String[] args) { ...
  • 有向无环图(DAG)才拓扑排序,非DAG没有拓扑排序一说。一般用有向边指示顺序关系,运用于顺序关系。例如,下面这个:显然是一个DAG,1→4表示4的入度+1,4是1的邻接点,代码表示:前者deg[4]++;后者用vector[1...

    条件:

    1.每个顶点出现且只出现一次。

    2.若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。

    有向无环图(DAG)才有拓扑排序,非DAG图没有拓扑排序一说。

    一般用有向边指示顺序关系,运用于顺序关系。

    例如,下面这个图:

    e54d13601a423a90f00c6f65e09e96d9.png

    显然是一个DAG图,1→4表示4的入度+1,4是1的邻接点,

    代码表示:前者deg[4]++;后者用vector[1].push(4)

    如何写出拓扑排序代码?

    1.首先将边与边的关系确定,建立好入度表和邻接表。

    2.从入度为0的点开始删除,如上图显然是1的入度为0,先删除。

    19332a827deb054d32997e88d38592db.png

    3.于是,得到拓扑排序后的结果是 { 1, 2, 4, 3, 5 }。通常,一个有向无环图可以有一个或多个拓扑排序序列。因为同一入度级别的点可以有不同的排序方式。

    4.拓扑排序可以判断图中有无环,如下图

    d629e0da68d1b220603200310b338461.png

    显然4,5,6入度都是1,不存在入度为0的点,无法进行删除操作。判断有无环的方法,对入度数组遍历,如果有的点入度不为0,则表明有环。

    例题+代码

    拓扑排序(一)-Hiho-Coder1174

    描述

    由于今天上课的老师讲的特别无聊,小Hi和小Ho偷偷地聊了起来。

    小Ho:小Hi,你这学期有选什么课么?

    小Hi:挺多的,比如XXX1,XXX2还有XXX3。本来想选YYY2的,但是好像没有先选过YYY1,不能选YYY2。

    小Ho:先修课程真是个麻烦的东西呢。

    小Hi:没错呢。好多课程都有先修课程,每次选课之前都得先查查有没有先修。教务公布的先修课程记录都是好多年前的,不但有重复的信息,好像很多都不正确了。

    小Ho:课程太多了,教务也没法整理吧。他们也没法一个一个确认有没有写错。

    小Hi:这不正是轮到小Ho你出马的时候了么!

    小Ho:哎??

    我们都知道大学的课程是可以自己选择的,每一个学期可以自由选择打算学习的课程。唯一限制我们选课是一些课程之间的顺序关系:有的难度很大的课程可能会有一些前置课程的要求。比如课程A是课程B的前置课程,则要求先学习完A课程,才可以选择B课程。大学的教务收集了所有课程的顺序关系,但由于系统故障,可能有一些信息出现了错误。现在小Ho把信息都告诉你,请你帮小Ho判断一下这些信息是否有误。错误的信息主要是指出现了"课程A是课程B的前置课程,同时课程B也是课程A的前置课程"这样的情况。当然"课程A是课程B的前置课程,课程B是课程C的前置课程,课程C是课程A的前置课程"这类也是错误的。

    输入

    第1行:1个整数T,表示数据的组数T(1 <= T <= 5)

    接下来T组数据按照以下格式:

    第1行:2个整数,N,M。N表示课程总数量,课程编号为1..N。M表示顺序关系的数量。1 <= N <= 100,000. 1 <= M <= 500,000

    第2..M+1行:每行2个整数,A,B。表示课程A是课程B的前置课程。

    输出

    第1..T行:每行1个字符串,若该组信息无误,输出"Correct",若该组信息有误,输出"Wrong"。

    Sample Input

    2

    2 2

    1 2

    2 1

    3 2

    1 2

    1 3

    Sample Output

    Wrong

    Correct

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    using namespace std;

    const int maxa=;

    vectorvec[maxa];

    queueq;

    int rudu[maxa];

    int t,n,m,x,y,now;

    bool tuopu(){

    int cnt=;

    while(!q.empty()) q.pop();

    for(int i=;i<=n;i++)

    if(rudu[i]==) q.push(i);

    while(!q.empty()){

    now=q.front();

    cnt++;

    q.pop();

    for(size_t i=;i

    if(--rudu[vec[now][i]]==)

    q.push(vec[now][i]);

    }

    if(cnt==n) return true;

    else return false;

    }

    int main(){

    cin>>t;

    while(t--)

    {

    cin>>n>>m;

    memset(rudu,,sizeof(rudu));

    for(int i=;i<=n;i++) vec[i].clear();

    while(m--)

    {

    cin>>x>>y;

    vec[x].push_back(y);

    rudu[y]++;//入度+1

    }

    if(tuopu()) cout<

    else cout<

    }

    return ;

    }

    C&num;实现有向无环图&lpar;DAG&rpar;拓扑排序

    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在 ...

    判断有向无环图&lpar;DAG&rpar;

    1.拓扑排序 bfs 所有入度为0的先入选. 2.tarjan 1个点1个集合 3.暴力 一个点不能重新到达自己

    【模板整合计划】图论—有向无环图 &lpar;DAG&rpar; 与树

    [模板整合计划]图论-有向无环图 (DAG) 与树 一:[拓扑排序] 最大食物链计数 \(\text{[P4017]}\) #include #include

    【拓扑】【宽搜】CSU 1084 有向无环图 &lpar;2016湖南省第十二届大学生计算机程序设计竞赛&rpar;

    题目链接: http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1804 题目大意: 一个有向无环图(DAG),有N个点M条有向边(N,M<=105 ...

    javascript实现有向无环图中任意两点最短路径的dijistra算法

    有向无环图 一个无环的有向图称做有向无环图(directed acycline praph).简称DAG 图.DAG 图是一类较有向树更一般的特殊有向图, dijistra算法 摘自 http://w ...

    有向无环图的应用—AOV网 和 拓扑排序

    有向无环图:无环的有向图,简称 DAG (Directed Acycline Graph) 图. 一个有向图的生成树是一个有向树,一个非连通有向图的若干强连通分量生成若干有向树,这些有向数形成生成森林 ...

    图-&gt&semi;有向无环图-&gt&semi;拓扑排序

    文字描述 关于有向无环图的基础定义: 一个无环的有向图称为有向无环图,简称DAG图(directed acycline graph).DAG图是一类较有向树更一般的特殊有向图. 举个例子说明有向无环图 ...

    CSU 1804&colon; 有向无环图 拓扑排序 图论

    1804: 有向无环图 Submit Page   Summary   Time Limit: 5 Sec     Memory Limit: 128 Mb     Submitted: 716    ...

    第十二届湖南省赛 (B - 有向无环图 )(拓扑排序&plus;思维)好题

    Bobo 有一个 n 个点,m 条边的有向无环图(即对于任意点 v,不存在从点 v 开始.点 v 结束的路径). 为了方便,点用 1,2,…,n 编号. 设 count(x,y) 表示点 x 到点 y ...

    随机推荐

    Jsp 错题分析

    ArrayList删除元素通过RemoveAt(int index)来删除指定索引值的元素 运行时异常都是RuntimeException类及其子类异常,如NullPointerException.I ...

    python框架&lpar;flask&sol;django&sol;tornado&rpar;比较

    一.对外数据接口 三者作为web框架,都是通过url映射对外的接口 flask:以decorator的形式,映射到函数中 django:以字典形式,映射到函数 tornado: 以字典形式,映射到类中 ...

    WPF 基础到企业应用系列索引

    转自:http://www.cnblogs.com/zenghongliang/archive/2010/07/09/1774141.html WPF 基础到企业应用系列索引 WPF 基础到企业应用系 ...

    &lpar;medium&rpar;LeetCode 207&period;Course Schedule

    There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prer ...

    配置Nginx服务

    一,安装之前准备1.nginx依赖: gcc openssl-devel pcre-devel zlib-devel    安装依赖:yum install gcc openssl-devel pcr ...

    javascript语言学习笔记。

    js类创建方法 var DogKing = function(dogName){ this.dogName = dogName; }; var myDogKing = new DogKing(&quo ...

    bzoj 2212&colon; &lbrack;Poi2011&rsqb;Tree Rotations

    Description Byteasar the gardener is growing a rare tree called Rotatus Informatikus. It has some in ...

    《深入理解Java虚拟机》-----第8章 虚拟机字节码执行引擎——Java高级开发必须懂的

    概述 执行引擎是Java虚拟机最核心的组成部分之一.“虚拟机”是一个相对于“物理机”的概念 ,这两种机器都有代码执行能力,其区别是物理机的执行引擎是直接建立在处理器.硬件.指令集和操作系统层面上的,而 ...

    APICloud Studio2新建应用报错和检出错误

    今天心血来潮,闲暇时间想做个移动应用app,听一哥们说APICloud开发app很方便,就查询了一下,看了之后简直就是热血沸腾,我感觉正是我一直要找的工具 信心满满的开始着手使用,看了一下介绍我选择了 ...

    展开全文
  • 工作流如下所示,要求每一个任务只执行一次,不重复执行,要求任务的所有前置任务必须完成才能往后执行,例如任务7必须在任务13,2,3三个任务完成之后才能执行,而任务13,2,3属于独立的任务,可以并发执行 根据多...

    工作流如下图所示,要求每一个任务只执行一次,不重复执行,要求任务的所有前置任务必须完成才能往后执行,例如任务7必须在任务13,2,3三个任务完成之后才能执行,而任务13,2,3属于独立的任务,可以并发执行

     

    根据多线程求得出6个路线数据

    每个线程可以独立执行,所有线程相同的任务不能重复执行,当前任务必须在前置任务完成之后才能执行,

    路线:[1, 2, 7, 10, 12]
    路线:[1, 13, 7, 10, 12]
    路线:[1, 3, 7, 10, 12]
    路线:[1, 4, 8, 10, 12]
    路线:[1, 4, 9, 11, 12]
    路线:[1, 5, 6, 9, 11, 12]

    路线不能出现回环,出现即死循环,需要提前排除

     

     

    实现代码如下(JDK1.8)

    数据结构类NetWork

    import java.util.*;
    
    /**
     * 图解网络数据结构
     */
    public class NetWork {
    
        //记录两份网络节点,使用空间换时间,提升反向查询效率
    
        //网络初始化,x_k,y_k
        private Map<String, Map<String, String>> xMapMap;
        //网络初始化,y_k,x_k
        private Map<String, Map<String, String>> yMapMap;
    
        //回环路径
        private List<String> loopbackList;//回环地址
        //节点深度路径
        private List<List<String>> deepPathList;//深度路径
    
        private Map<String, String> jobMapStatus;//map任务状态
    
        enum TYPE {X,Y}
    
    
        public NetWork() {
            xMapMap = new HashMap();//X点集
            yMapMap = new HashMap();//Y点集
            loopbackList = new LinkedList<>();//回环地址
            deepPathList = new LinkedList<>();//深度路径
        }
    
        /**
         * 初始化任务
         */
        public void initJob() {
            jobMapStatus = new HashMap<>();
            Set<String> allPoint = getAllPoint();
            allPoint.forEach(job -> jobMapStatus.put(job, "0"));//0,1  0表示未执行,1表示执行
        }
    
    
        /**
         * 获取任务的转状态
         *
         * @param job
         * @return
         */
        public String getJobMapStatus(String job) {
            String status = jobMapStatus.get(job);
            return status;
        }
    
        /**
         * 更新任务的状态
         *
         * @param job    任务名称
         * @param status 任务状态
         */
        public void setJobMapStatus(String job, String status) {
            jobMapStatus.put(job, status);
        }
    
    
        public List<String> getLoopbackList() {
            return loopbackList;
        }
    
        public List<List<String>> getDeepPathList() {
            return deepPathList;
        }
    
        /**
         * 网络添加节点
         *
         * @param xPoint   x位
         * @param yPoint   y位
         * @param distance 位移
         */
        public void addPoint(String xPoint, String yPoint, String distance) {
            if (!xMapMap.containsKey(xPoint)) {//记录x的索引
                xMapMap.put(xPoint, new HashMap<>());
            }
            xMapMap.get(xPoint).put(yPoint, distance);
            if (!yMapMap.containsKey(yPoint)) {//记录y的索引
                yMapMap.put(yPoint, new HashMap<>());
            }
            yMapMap.get(yPoint).put(xPoint, distance);
        }
    
        /**
         * 根据坐标获取某点
         *
         * @param xPoint
         * @param yPoint
         * @return
         */
        public String getPoint(String xPoint, String yPoint) {
            Map<String, String> linePoints = xMapMap.get(xPoint);
            String point = linePoints.get(yPoint);
            return point;
        }
    
        public String getPoint(String point1, String point2, TYPE type) {
            if (type == TYPE.X) {
                Map<String, String> linePoints = xMapMap.get(point1);
                String point = linePoints.get(point2);
                return point;
            } else {
                Map<String, String> linePoints = yMapMap.get(point1);
                String point = linePoints.get(point2);
                return point;
            }
        }
    
        /**
         * 获取X轴的一列数据
         *
         * @param xPoint
         * @return
         */
        public List<Map<String, String>> getLinePoint(String xPoint) {
            List<Map<String, String>> linePointList = new ArrayList<Map<String, String>>();
            Map<String, String> linePoints = xMapMap.get(xPoint);
            if (linePoints != null) {
                for (Map.Entry<String, String> pointUnit : linePoints.entrySet()) {
                    Map<String, String> pointMap = new HashMap<String, String>();
                    pointMap.put("X", xPoint);
                    pointMap.put("Y", pointUnit.getKey());
                    pointMap.put("D", pointUnit.getValue());
                    linePointList.add(pointMap);
                }
            }
            return linePointList;
        }
    
        /**
         * 根据类型获取某轴的一列数据
         *
         * @param point 索引点
         * @param type  类型
         * @return
         */
        public List<Map<String, String>> getLinePoint(String point, TYPE type) {
            List<Map<String, String>> linePointList = new ArrayList<Map<String, String>>();
            if (type == TYPE.X) {
                Map<String, String> linePoints = xMapMap.get(point);
                if (linePoints != null) {
                    for (Map.Entry<String, String> pointUnit : linePoints.entrySet()) {
                        Map<String, String> pointMap = new HashMap<String, String>();
                        pointMap.put("X", point);
                        pointMap.put("Y", pointUnit.getKey());
                        pointMap.put("D", pointUnit.getValue());
                        linePointList.add(pointMap);
                    }
                }
            } else {
                Map<String, String> linePoints = yMapMap.get(point);
                if (linePoints != null) {
                    for (Map.Entry<String, String> pointUnit : linePoints.entrySet()) {
                        Map<String, String> pointMap = new HashMap<String, String>();
                        pointMap.put("X", pointUnit.getKey());
                        pointMap.put("Y", point);
                        pointMap.put("D", pointUnit.getValue());
                        linePointList.add(pointMap);
                    }
                }
            }
            return linePointList;
        }
    
    
        /**
         * @param netWork    网络节点
         * @param startPoint 起始节点
         * @param pathList   当前任务的路径
         */
        public void recursive(NetWork netWork, String startPoint, ArrayList<String> pathList) {
            if (pathList.contains(startPoint)) {netWork.getLoopbackList().add(pathList.toString() + "->" + startPoint);return;}
            pathList.add(startPoint);
            List<Map<String, String>> linePoint = netWork.getLinePoint(startPoint, NetWork.TYPE.X);
            if (linePoint.size() == 0) {
                ArrayList<String> descList = new ArrayList<>(pathList.size());
                pathList.forEach(path -> descList.add(path));
                netWork.getDeepPathList().add(descList);
            }
            for (Map<String, String> map : linePoint) {recursive(netWork, map.get("Y"), pathList);}
            pathList.remove(startPoint);
        }
    
    
        /**
         * 获取所有的点,合并key
         *
         * @return
         */
        public Set<String> getAllPoint() {
            Set<String> allSet1 = xMapMap.keySet();
            Set<String> allSet2 = yMapMap.keySet();
            Set<String> allSet = new HashSet<>();
            allSet.addAll(allSet1);
            allSet.addAll(allSet2);
            return allSet;
        }
    
    
        /**
         * 显示路径
         */
        public void show() {
            int placeholder = 3;
            String placeholderSrting = "";
            for (int i = 0; i < placeholder; i++) {placeholderSrting = placeholderSrting + "-";}
            Set<String> allSet = getAllPoint();//获取所有的点,用于遍历
            System.out.print(String.format("%-" + placeholder + "s", ""));
            System.out.print(" ");
            for (String x : allSet) {
                System.out.print(String.format("%-" + placeholder + "s", x));
            }
            System.out.println();
            System.out.print(String.format("%-" + placeholder + "s", "X\\Y"));
            System.out.print(" ");
            for (String ignored : allSet) {System.out.print(placeholderSrting);}
            System.out.println();
            for (String x : allSet) {
                System.out.print(String.format("%-" + placeholder + "s|", x));
                for (String y : allSet) {
                    Map<String, String> linePoints = xMapMap.get(x);
                    String point = "0";
                    if (linePoints != null && linePoints.get(y) != null) {
                        point = linePoints.get(y);
                    }
                    System.out.print(String.format("%-" + placeholder + "s", point));
                }
                System.out.println();
            }
        }
    }

     

    测试类TestMain

    import java.util.ArrayList;
    import java.util.List;
    import java.util.Map;
    import java.util.concurrent.ConcurrentHashMap;
    import java.util.concurrent.ConcurrentMap;
    
    /**
     * 网络计算
     */
    public class TestMain {
    
        public static ConcurrentMap<String, List<String>> println = new ConcurrentHashMap<>();
        public static List<String> strings = new ArrayList<>();
    
        public static void main(String[] args) throws InterruptedException {
            NetWork netWork = new NetWork();
            netWork.addPoint("1", "2", "1");
            netWork.addPoint("1", "3", "1");
            netWork.addPoint("1", "4", "1");
            netWork.addPoint("1", "5", "1");
            netWork.addPoint("1", "13", "1");
            netWork.addPoint("2", "7", "1");
            netWork.addPoint("3", "7", "1");
            netWork.addPoint("13", "7", "1");
            netWork.addPoint("4", "8", "1");
            netWork.addPoint("4", "9", "1");
            netWork.addPoint("5", "6", "1");
            netWork.addPoint("6", "9", "1");
            netWork.addPoint("7", "10", "1");
            netWork.addPoint("8", "10", "1");
            netWork.addPoint("9", "11", "1");
            netWork.addPoint("10", "12", "1");
            netWork.addPoint("11", "12", "1");
            netWork.initJob();//初始化所有节点任务
            //netWork.addPoint("6", "1", "1");netWork.addPoint("4", "6", "1");//回环的两条数据
            netWork.show();
            //获取起点,如图起点为1
            String startPoint = "1";
            netWork.recursive(netWork, startPoint, new ArrayList<>()); //递归计算所有节点的路径
            if (netWork.getLoopbackList().size() != 0) {
                System.out.println("出现回环地址,回环地址的路径为:" + netWork.getLoopbackList());
                return;
            }
            //开始计算任务
            for (List<String> pathJobList : netWork.getDeepPathList()) {
                new Thread(() -> {
                    System.out.println("路线:" + pathJobList);
                    for (int i = 0; i < pathJobList.size(); i++) {
                        String job = pathJobList.get(i);
                        List<String> linePoint = new ArrayList<>();//获取任务前置条件
                        netWork.getLinePoint(job, NetWork.TYPE.Y).forEach(jobLine -> linePoint.add(jobLine.get("X")));
                        /*System.out.println("任务" + job + "的前置条件:" + linePoint);*/
                        execJob(job, linePoint, netWork);//执行任务
    
                    }
                }).start();
            }
            Thread.sleep(1000);//这里使用的休眠进行下一次判断,也可以使用锁同步数据,使用锁实现较为复杂
            for (Map.Entry<String, List<String>> entry : println.entrySet()) {
                System.out.println(entry);
            }
            System.out.println("执行顺序:" + strings);
        }
    
        /**
         * 执行任务
         *
         * @param job
         */
        private static void execJob(String job, List<String> linePoint, NetWork netWork) {
            List<String> tmp = new ArrayList<>();
            while (true) {
                for (String precondition : linePoint) {
                    String jobMapStatus;
                    synchronized (String.class) {jobMapStatus = netWork.getJobMapStatus(precondition);}
                    if (!"1".equals(jobMapStatus)) {tmp.add(precondition);}//未执行
                }
                if (tmp.size() == 0) {break;}
                linePoint.clear();
                tmp.forEach(jobTmp -> linePoint.add(jobTmp));
                tmp.clear();
                /*此处可以随机数休眠模拟任务执行所需的时间*/
            }
            String jobMapStatus;
            Boolean status = false;//是否需要执行任务
            synchronized (String.class) {
                jobMapStatus = netWork.getJobMapStatus(job);
                if ("1".equals(jobMapStatus)) {return;}//任务已经完成
                if ("0".equals(jobMapStatus)) {netWork.setJobMapStatus(job, "-1");status = true;}//立即执行
            }
            if (status) {
                synchronized (String.class) {
                    if (!println.containsKey(Thread.currentThread().getName())) {
                        println.put(Thread.currentThread().getName(), new ArrayList<>());
                    }
                    println.get(Thread.currentThread().getName()).add(job);strings.add(job);
                    netWork.setJobMapStatus(job, "1");
                }
            }
        }
    }

    测试结果如下

     

     

    实现原理是使用矩阵,X轴表示起始点,Y轴表示结束点,起始点与结束点对应的值为1 即表示起始点与结束点之间是一条通线,如果值为0 即表示这两点之间不通

    根据矩阵原理开发

        起始点对应的一行中所有值为1的结束点为起始点可到达的结束点

        结束点对应的一列中所有值为1的起始点是结束点所表示任务的前置任务

     

    所以数据结构NetWork类中已经封装好了通过x,y坐标获取一个值和通过x或者通过y获取一行或者一列数据的方法

     

     

    展开全文
  • 主要介绍了邻接表无向图Java语言实现完整源码,具有一定借鉴价值,需要的朋友可以参考下。
  • 最近想写一个识别线程死锁的算法,在网上找了半天没有合适的代码,自己写了个查找有向图中的的代码(可以将死锁的资源依赖建模成含有向图)。本代码经过充分测试,内部详细说明,可以放心下载。
  • 文章目录无环图拓扑排序AOV-网AOE-网关键路径的概念事件的最早/晚...将这些子工程之间的先后关系用有向图表示,其中顶点表示活动,向边表示活动之间的优先制约关系,称这种有向图为顶点表示活动的网,简称AOV网。

    有向无环图

    在这里插入图片描述

    拓扑排序

    在这里插入图片描述

    AOV-网

    在这里插入图片描述
    由于有向无环图可以用一种自然的方式对优先关系或依赖关系进行描述,因此在工程计划与管理方面有广泛而重要的应用。一个大的工程往往可以分解为若干相对独立的子工程(活动),子工程之间在进行的时间上有一定的相互制约关系。将这些子工程之间的先后关系用有向图表示,其中顶点表示活动,有向边表示活动之间的优先制约关系,称这种有向图为顶点表示活动的网,简称AOV网。

    AOE-网

    在这里插入图片描述

    表示一个实际工程计划的AOE网应当是无环且存在唯一的源点和汇点的。如果途中存在多个入度为0的顶点,那么可以添加一个虚拟源点,使这个虚拟源点到原来各个入度为0的顶点都有一条权值为0的边。对多个出度为0的顶点的情况可做类似的处理。
    (这里其实不是很懂)

    关键路径的概念

    在这里插入图片描述
    在这里插入图片描述

    在AOE网中有些活动可以并行地进行。因此,完成整个工程的最短时间应该是从源点到汇点的最长路径的长度(路径长度等于路径上各边权值之和)。

    需要注意的是:AOE网中可能有不止一条的关键路径

    分析关键路径的目的是找出关键活动,即不按期完成就会影响整个工程的完成时间的活动,从而为决策者提供调度依据。应当投入较多的人力和物力在关键活动上,以保证整个工程按期完成,并可争取提前完成。

    在这里插入图片描述
    由于关键路径由关键活动组成,因此只要找出AOE网中的关键活动,就可以找到关键路径。

    在这里插入图片描述
    在这里插入图片描述
    (这里看不懂可以看下面)

    事件是有向图中的顶点。活动的最早开始时间和最晚开始时间可以直接由事件的最早开始时间和最晚开始时间求得。因此,算法的核心在于求事件的最早开始事件和最晚开始时间。

    由活动和事件的关系可知:求解过程有正推和反推两个过程:先正推,才能找到耗时最长的路径;再反推,就可找出关键活动(即l(ai)=e(ai)的活动);由关键活动就找到了关键路径

    在这里插入图片描述
    求解步骤:

    1. 求拓扑排序
    2. 从始点v0出发,令ve[0]=0,按拓扑有序求ve[j](对j来说,取所有进来的边的最大值:ve(j)=Max{ve(i)+dut(<i,j>)})
    3. 从终点vn-1出发,令vl[n-1]=ve[n-1],按逆拓扑有序求vl[i](对j来说,取所有出去的边的最小值:vl(i)=Min{vl(j)-dut(<i,j>)})
    4. 根据各顶点的ve和vl值,求每条弧(活动)aj的最早开始时间e[aj]和最迟开始时间l[aj]。e(aj)=ve(j); l(aj)=vl(k)-dut(<j,k>) j—aj-k
    5. 如果e[aj]=l[aj],则ai为关键活动

    事件的最早/晚开始时间

    好了看到这里你会说这说的什么玩意 , 下面我用人话解释一下:
    事件(顶点)的最早开始时间:
    某个顶点的最早开始时间就是指这个工程最早什么时候能开工?也就是所有的前置工程什么时候完成了,就可以开工了。也就是所有前置工程的最早的开工时间,再加上那个工程所需的时间中,最大的值,(这样才能保证所有前置工程都开工了。)

    选取所有前置工程的最早开始时间加上工程时间的最大值,这就是最早开始时间。

    事件(顶点)的最晚开始时间:
    比如我不想那么早开干,能拖一天是一天 ,但是要保证不会影响后面的工程,那么此时就是找到后一个工程的最晚开始时间,(也就是后一个懒狗 ),意思就是我再懒再拖,也不能影响我后面的懒狗导致他不能及时开工。
    比如同学A交给我一个任务,我做完后要交给他继续完成,他最晚5号要开始做,那我要做两天的话,那我最晚3号就要交给他。
    多人运动的情况就是:
    比如同学AB交给我一个任务,我做完后要交给他们继续完成,同学A最晚5号要开始做,那我要做两天的话,那我最晚3号就要交给他,但是同学B最晚4号要开始做,那我只能2号就开始做了。

    所以选取所有后置工程的最晚开始时间减去工程时间的最小值就是我的最晚开始时间了

    事实上当一个顶点连了多个边的时候,当到达了最晚开始时间,事实上这个顶点所指向的所有边中,可能并不是所有边都必须得立马开工的,有些边也还是可以继续偷懒的,只要让最紧迫的那个边开工就行了,其他的边是存在冗余时间的

    而最晚开始时间减去最早开始时间等于冗余时间。
    但是需要注意一点,初始的顶点和最后一个顶点,由于大家所有人都希望工程尽早完工,所以不会给最开始的点和最后的点偷懒的机会,也就意味着没有冗余时间。(最前面和最后面的顶点注定做不了懒狗

    所以最早的顶点和最晚的顶点他们的最晚开始时间只能等于最早开始时间。

    事件和活动的区分

    这里要注意区分上面和下面的情况:

    一个顶点是一个事件,一条边是一个活动。或者可以这么说,这样可能更好理解,在游戏里,一个公会有很多玩家,一个公会达成一个称号,或者取得某个成就,或者建房子(也就是事件),他需要各个玩家去做事才能完成。当A玩家和B玩家都达成了“取得排名第一”的成就时,公会就达成了“有两个玩家达成第一”的成就。
    所以事件和活动是这样的一个关系。

    一个事件需要一些活动来作为前置,那些活动完成之后,事件(成就)才可以达成。而达成了这个成就后,就可以再安排公会里的其他成员去做其他事情来达成新的成就。

    因此一个事件连着多个活动,有前置活动和后置活动,而一个活动只连接了两个顶点。

    由于一个顶点(一个成就)涉及到多个活动(各个玩家的努力),因此需要在多个活动直接选择最值。
    但是活动只涉及到两个顶点的事,不需要考虑最值。

    活动的最早/晚开始时间

    活动(边)的最早开始时间
    一个事件什么时候可以开始,或者说一个成就什么时候达成之后,就可以开始做“因为有了这个成就就可以做新的事”这样的事情了。

    所以活动的最早开始事件等于事件的最早开始时间。意思就是某个成就达成后就可以做新的活动了。

    活动(边)的最晚开始时间
    这里需要注意,一个活动(边)的最晚开始时间并不是顶点的最晚开始时间,这是因为一个顶点需要考虑多个活动,让多个活动都不能延误,因此顶点需要在所有活动的最晚开始时间中选择最早的那个。而一个活动只需要考虑本身就行了。
    因此活动的最晚开始时间等于其所指向的那个点的最晚时间减去工程的长度

    在这里插入图片描述
    在这里插入图片描述
    然后我们找到冗余时间为零的点连起来即为关键路径:
    在这里插入图片描述
    其次要注意:

    若AOE网中有多条关键路径,那么仅提高一条关键路径上的关键活动的速度并不能导致整个工程缩短工期,而必须提高同时在几条关键路径上的关键活动的速度才能有效

    展开全文
  • public void topoSort(){//仅仅针对有向图,基本思路是找到一个无后继的结点,将其删除,并放到排序数组的尾端,依次循环。直到没有结点。 int originalVertex = nVertex; while(nVertex > 0){ int ...
  • NULL 博文链接:https://128kj.iteye.com/blog/1717469
  • 简单实现有向无环图思路

    千次阅读 2019-05-13 15:59:47
    给一部分带from和to的节点组织成一个有向无环图,给from与to路径找到他们之前的连线轨迹。实现思路:遍历所有的节点,该节点如果不包含from或者to的内容且周围只有一个节点这样的节点从我们总的节点中删除,最终...
  • 本代码实现java实现带权无环图关键路径的查找,使用者可根据自身需要进行修改
  • NULL 博文链接:https://128kj.iteye.com/blog/1720196
  • Java 判断有向图是否有环 拓扑排序

    千次阅读 2020-03-13 22:32:27
    拓扑排序 import java.util.*; public class Demo1{ public static void main(String[] args) { Scanner sc=new Scanner(System.in); while (sc.hasNext()){ int point=Inte...
  • 算法: 有向无环图(DAG)的拓扑排序

    万次阅读 2015-10-22 15:25:38
    定义: 拓扑排序是对有向无环图(DAG)的顶点的一种排序, 使得如果存在一条从v到w的路径,那么在排序中w就出现在v的后面。 如果含有,那么拓扑排序是不可能的。试想3个正整数,a比b大,b比c大,c比a大,我们...
  • java 无向图所有最短路径算法的实现

    热门讨论 2012-04-19 11:23:45
    本资源来自MyEclipse,其中的项目对其中的题目进行了解答。仅供学习参考。不足之处请批评指正。
  • Java数据结构之有向图

    千次阅读 2019-04-30 23:20:04
    术语 向完全图:把所有顶点都用边连起来的图,共n(n-1)条边。...基本和无向图相同,其中邻接表存储边的时候只需要存储一次,而addEdge(int v,int w)参数前后之分,前一个表示起点,后一个为终点。 /...
  • 双数组Trie树高效构建有向无环图

    千次阅读 2018-07-19 08:33:13
    图 图是很常见的一种结构了,不管是数据结构算法...无环图,即 Directed Acyclic Graph,属于有向图,图结构中不存在,可用来表示事件之间依赖关系。 Trie树 Trie 是一种搜索树,它的 key 都为字符串,...
  • 主要介绍了Java简单实现约瑟夫算法,简单描述了约瑟夫问题,并结合实例形式分析了Java实现约瑟夫的具体操作技巧,需要的朋友可以参考下
  • 判断有向图是否有环

    千次阅读 2021-03-15 02:40:32
    方法一:拓扑排序时间复杂度O(n^2)比较常用的是用拓扑排序来判断有向图中是否存在。什么是拓扑排序呢?我们先定义一条u到v的边e=,u生成拓扑序列的算法就叫拓扑排序啦~算法流程描述while(节点个数次(N)循环)1.找出...
  • 如何使用有向无环图(dag-diagram)1、自定义右击事件偶现问题2、节点删除再添加反复操作几次会出现,删除一个节点多个节点一起消失3、检测是否成环 关于有向无环图在vue项目中的使用和安装,已经很多的文章过...
  • 第一次写博客,不太会用,话不多说 直接上代码 详细可以看注释,... * @Description:判断无向图是否有环 深度优先遍历 * 需要保存父节点 * @Create 2020-04-03 21:04 * @Email:1173748742@qq.com */ public clas...
  • java实现简单的Dag

    2020-12-17 12:03:03
    基于java进行的实现简单Dag;附件中包含java根据配置的dagJson。1实现了filter过滤,返回指定的字段;2实现了按指定字段排序,返回指定的字段;可以自己添加mysql、Oracle、redis、hive、es、sparksql、clickhouse...
  • 判断有向无环图(DAG) 其实,这篇博文是前面两篇的应用,并不算是一个基础操作。看起来可能会有点重复,但是作为巩固复习一下也不错。我感觉最近可能代码贴太多了,我有时间的时候,多加入一些注解吧。可能会适当...
  • Spark有向无环图DAG图解与演示

    千次阅读 2018-11-12 19:21:44
    目录:1、无环图 2、代码结构 3、代码学习步鄹及方法 4、重点代码讲解 5、代码展现 ...因为有向图中一个点经过两种路线到达另一个点未必形成,因此无环图未必能转化成树,但任何有向树...
  • Java实现有向图得到DAG

    千次阅读 2018-05-14 12:20:08
    import java.util.HashSet; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Set; import java.util.Stack; public class DAG { static int ...
  • 定时任务是软件开发中经常遇到的问题。简单的定时任务只需要在固定时间触发它的...例如下面这幅中任务的依赖关系为: 任务1:依赖2,5 任务2:依赖3,4 任务3:依赖 任务4:依赖 任务5:依赖 ...
  • 有向图的定义及Java实现

    千次阅读 2020-11-21 18:17:52
    定义:有向图是具有方向性的图,由一组顶点和一组方向的边组成,每条方向的边都连着一对有序的顶点。 2 相关术语 出度:由某个顶点指出的边的个数; 入度:指向某个顶点的边的个数; 向路径:由一系列顶点组成...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 155,204
精华内容 62,081
关键字:

java 有向无环图

java 订阅