问题:在有向图 ( 只有1 个开始节点, 1 个结束节点) 中判断任意两个节点是否为相同层次,不考虑环的情况,
A,B为相同层次可以理解为经过A的数据流必然经过B,经过B的数据流也必然经过了A
例
a>b
a>c
b>d
c>d
其中 b ,c 节点为并行节点,都完成之后到达 d 节点,其中a , d为相同层次 ,a,b;b,d;b,c 都不是相同层次
另外一个例子
a>b
a>c
b>c
c>d
b>d
其中 a,d 为相同层次,其他都不是
/** * 算法核心思想: * a的数据流必经过b的深刻含义为,a的数据流无论从哪条路走都必须经过b,这就要求a的相邻节点也具有该特性; * 同理将有向图反向,b的数据流也必经过a */ public class SameLevel { //n为节点个数,e为有向边个数 private static int n,e; //有向图正向临接表 private static Map<Character,LinkedList<Character>> adjacencyMap = new HashMap<Character,LinkedList<Character>>(); //有向图反向临接表 private static Map<Character,LinkedList<Character>> adjacencyReverseMap = new HashMap<Character,LinkedList<Character>>(); /* * 创建正向与反向临接表 * 输入格式参考如下: * 4 4 //输入节点个数与有向边数 * a b c d //输入各个节点 * a b // 以下四行有输入的有向边 * a c * b d * c d * a d //输入需要判断层次的任意两个节点 */ public static boolean createGraph(Scanner sc){ n = sc.nextInt(); e = sc.nextInt(); if(n == 0 || e == 0) return false; for(int i=0;i<n;i++){ char c = sc.next().toCharArray()[0]; adjacencyMap.put(c,new LinkedList<Character>()); adjacencyReverseMap.put(c,new LinkedList<Character>()); } for(int i=0;i<e;i++){ char c = sc.next().toCharArray()[0],d = sc.next().toCharArray()[0]; LinkedList<Character> list = adjacencyMap.get(c), rlist = adjacencyReverseMap.get(d); list.addFirst(d); rlist.addFirst(c); } return true; } /* * 判断a是否从任意路径可达b */ public static boolean DFSTraverseAtoB(char a ,char b , boolean []visited){ if(a == b) return true; boolean ret = true; LinkedList<Character> adjacentList = adjacencyMap.get(a); for(char c : adjacentList){ Arrays.fill(visited,false); if(!DFS(c,b,visited) || !DFSTraverseAtoB(c,b,visited)){ ret = false; break; } } return ret; } /* * 深度优先遍历算法 */ public static boolean DFS(char a , char b , boolean[] visited){ if(a == b){ return true; } visited[a] = true; LinkedList<Character> adjacentList = adjacencyMap.get(a); for(char c : adjacentList){ if(!visited[c]){ if(DFS(c,b,visited)){ return true; } } } return false; } /* * 判断两个节点是否是同一层次 */ public static boolean isSameLevel(char a ,char b){ boolean ret = false,ret1 = false; if(!adjacencyMap.containsKey(a) || !adjacencyMap.containsKey(b)){ throw new RuntimeException("Node Doesn't exist!"); } boolean[] visited = new boolean[256]; ret = DFSTraverseAtoB(a ,b ,visited); adjacencyMap = adjacencyReverseMap; //有向图反向再判断一次 ret1 = DFSTraverseAtoB(b,a ,visited); return ret && ret1; } public static void main(String[]args){ Scanner sc = new Scanner(System.in); boolean created = createGraph(sc); if(!created){ throw new RuntimeException("Create graph failed!"); } Character a = sc.next().toCharArray()[0],b = sc.next().toCharArray()[0]; boolean ret = isSameLevel(a,b); System.out.println(ret); } }
由于上述代码不够灵活,效率不高,且不好测试,重构后的代码如下:
public class SameLevel { //n为节点个数,e为有向边个数 private static int n,e; //有向图正向临接表 private static Map<Character,LinkedList<Character>> adjacencyMap = new HashMap<Character,LinkedList<Character>>(); //有向图反向临接表 private static Map<Character,LinkedList<Character>> adjacencyReverseMap = new HashMap<Character,LinkedList<Character>>(); //填充正向与反向临接表 private static void fullMap(Map<Character,LinkedList<Character>> map,Character a,Character b){ if(!map.containsKey(a)){ map.put(a,new LinkedList<Character>()); } map.get(a).add(b); if(!map.containsKey(b)){ map.put(b,new LinkedList<Character>()); } } /* * 根据输入的map创建图 */ public static boolean createGraph(Set<Edge<Character>> set){ if(set == null || set.size() == 0) return false; for(Edge<Character> edge : set){ Character key = edge.getStart(),value = edge.getEnd(); fullMap(adjacencyMap,key,value); fullMap(adjacencyReverseMap,value,key); } return true; } /* * 判断a是否从任意路径可达b */ public static boolean DFSTraverseAtoB(char a ,char b){ if(a == b) return true; boolean ret = false; LinkedList<Character> adjacentList = adjacencyMap.get(a); for(char c : adjacentList){ if(!DFSTraverseAtoB(c,b)){ return false; } ret = true; } return ret; } /* * 判断两个节点是否是同一层次 */ public static boolean isSameLevel(char a ,char b, Set<Edge<Character>> set){ if(set == null || set.size() == 0) return false; boolean ret = false,ret1 = false,created = createGraph(set); if(!created || !adjacencyMap.containsKey(a) || !adjacencyMap.containsKey(b)){ throw new RuntimeException("Error!"); } ret = DFSTraverseAtoB(a ,b); adjacencyMap = adjacencyReverseMap; //有向图反向再判断一次 ret1 = DFSTraverseAtoB(b,a); return ret && ret1; } /* * */ public static void main(String[]args){ Set<Edge<Character>> set = new HashSet<Edge<Character>>(); set.add(new Edge<Character>('a','b')); set.add(new Edge<Character>('b','c')); set.add(new Edge<Character>('b','d')); set.add(new Edge<Character>('d','e')); set.add(new Edge<Character>('c','d')); System.out.println(isSameLevel('a','d',set)); } /* * 定义有向图的边对象 * @start 为边的起点 * @end 为边的终点 */ static class Edge<T>{ private T start; private T end; public T getStart() { return start; } public void setStart(T start) { this.start = start; } public T getEnd() { return end; } public void setEnd(T end) { this.end = end; } public Edge(T start,T end){ this.start = start; this.end = end; } } }
https://gist.github.com/narutolby/8348153#file-gistfile1-java
相关推荐
《你必须知道的495个C语言问题》结构清晰,讲解透彻,是各高校相关专业C语言课程很好的教学参考书,也是各层次C程序员的优秀实践指南。 -----------------------------------------------------------------------...
本软件是专业化立体相机模拟软件,将对分层图的每个图层以及整体图像,模拟从不同角度拍照,生成不同角度的多张照片,如果图中有变画,也能包含其中,一起生成,互不影响。然后在三立立体实拍合成软件(3D之星IV)中...
本系统就是在基于以上原因,开发了一款利用Visio进行二次开发,将C#与Visio想结合,能绘制电气接线图,并能打开已有的电气接线,保存所绘制的接线图等功能,并能在接线图的基础上,进行潮流计算。 1 绪论 1.1 课题的...
需求模型的表现形式有自然语言、半形式化(如图、表、结构化英语等)和形式化表示等三种。需求概念模型的要求包括实现的独立性:不模拟数据的表示和内部组织等;需求模拟技术又分为企业模拟、功能需求模拟和非功能需求...
该方法对现有本体匹配方法进行扩展,综合编辑距离、层次关系等特征,计算本体的结构级相似性,以点、边有序交替匹配来判断实体的有向图近似同构问题,实现本体匹配判定。演示算法处理过程,给出算法时间复杂度理论...
1.5 这样的声明有什么问题?char *p1, p2; 我在使用p2的时候报错了。 1.6 我想声明一个指针,并为它分配一些空间,但却不行。这样的代码有什么问题?char *p; *p=malloc(10); 声明风格 1.7 怎样声明和定义全局变量和...
无论您是初入此领域的小白,还是寻求更高层次进阶的资深人士,这里都有您需要的宝藏。不仅如此,它还可以作为毕设项目、课程设计、作业、甚至项目初期的立项演示。 【人工智能的深度探索】 人工智能——模拟人类...
系统分析侧重于从业务全过程的角度进行分析,确定分析结果,提出信息系统的各种设想和方案,并对所有的设想和方案进行分、研究、比较、判断和选择,获得一个最优的新系统的逻辑模型,并在用户理解计算机系统的工作...
3种方式由于应用层次的差异,使得效率由低到高,独立性由高到低。对于相连数据库的数据处理,也有2种方式,即一种是通过DataSet来隔离异构的数据源,另一种是以流方式从数据源读取(DataReader方式)。 传统的应用程序...
= 1 * 2 * 3 * … * r 所有计算连乘积的程序都使用一个积单元,有类似图4.35的程序模式。这里用后判 断条件的 循环,当然也可以采用先判断条件的循环。其中: P是积单元; 开始进入循环之前积单元P必须置"1"; 在...
4、用邻接矩阵或邻接图实现一个有向图的存储,并实现单源最短路径算法的实现(这个类的一个成员函数),并能输出该图的关键路径。 注:1、要用面向对象的方法设计代码; 2、一个图是一个类的实例; 3、类...
= 1 * 2 * 3 * … * r 所有计算连乘积的程序都使用一个积单元,有类似图4.35的程序模式。这里用后判 断条件的 循环,当然也可以采用先判断条件的循环。其中: P是积单元; 开始进入循环之前积单元P必须置"1"; 在...
系统前期分析过程中经常使用的图形模型有系统框架图和系统流程图。其中,系统框架图用于说明系统的基本构造框架,而系统流程图则用于表现系统的基本加工流程。 2.项目可行性分析 (1)意义 •以少量的费用对项目能否...
译者: 李洋[同译者作品] 郑龑 出版社:机械工业出版社 目录 第一部分 绪 论 第1章 面向对象分析和设计 1.1 本书的主要内容 1.2 最重要的学习目标 1.3 什么是分析和设计 1.4 什么是面向对象分析和设计 ...
3.2 系统层次模块图 停车场管理系统 停车场管理系统 退出系统查看车位使用状况计算停车费用车辆离开信息车辆到达信息 退出系统 查看车位使用状况 计算停车费用 车辆离开信息 车辆到达信息 车牌号到达时间离开时间该...
该方法对现有本体匹配方法进行扩展,综合编辑距离、层次关系等特征,计算本体的结构级相似性,以点、边有序交替匹配来判断实体的有向图近似同构问题,实现本体匹配判定。演示算法处理过程,给出算法时间复杂度理论...
拿到的这个数也就只能做做折线图,同⽐环⽐两组数对⽐⼀下!业务当中发⽣了什么数据好像不能看出来! 不知道⼀个函数得出的结果代表什么!还有可能我根本不会⽤⼀些⼯作等等。。。 那为什么很多伙伴都想学数据分析呢...
或着是磁力打造,一个好的理论一定对现实素材有吸引力,向磁铁一般;这也是在矛盾中建造现实的方法,只要是具体的就肯定是可以分析出潜在矛盾、不完美的,问题不仅仅是分析、认识现实,还要能够构造现实;不存在完美...
并不是所有问题都有合理的解决办法,事实上许多问题不可能在预定的系统规模之内解决。如果问题没有可行的解决,那么花费在这项开发工程上的任何时间、资源、人力和经费都是无谓的浪费。 对于软件设计而言,可行性...
逻辑结构设计 逻辑结构设计是在概念结构设计的基础上进行的数据模型设计,一般有层次、网状模 型和关系模型,现在绝大多数DBMS都是基于关系模型的,此阶段的主要任务有确定数据 模型、将E-R图转换为指定的数据模型、...