-
简单方法查找邻接矩阵有向图的有序集合
2020-04-06 11:31:08简单方法查找邻接矩阵有向图的有序集合求解思路实现代码测试用例知识背景 求解思路 1.统计所有节点的出度及其前序节点,初始化一个空的访问集合; 2.将出度为零的节点放入访问集合,并将其前序节点的出度数减1; 3....求解思路
1.统计所有节点的出度及其前序节点,初始化一个空的访问集合;
2.将出度为零的节点放入访问集合,并将其前序节点的出度数减1;
3.重复第2步骤,直到所有节点从头到尾完整遍历一遍;
4.判断已访问节点个数是否等于节点个数,是则有向图无环,否则有向图有环。实现代码
方法一:
import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.stream.Collectors; public class AlgorithmUtil { /** * 查找有向图的有序集合,如果有环返回空数组 * 根据每个节点的入度和出度计算,把出度为零的依次去掉并更改其前序节点的出度个数,统计最后访问过的节点 */ public static int[] findSequence(int[][] graph) { int nodeNum = graph.length; // 记录每个有入度的节点,及其所有的前序节点 Map<Integer, List<Integer>> inEdge = new HashMap<>(nodeNum); // 记录每个节点的出度个数 int[] outEdgeNum = new int[nodeNum]; // 初始化数据 for (int i = 0; i < nodeNum; i++) { for (int j = 0; j < nodeNum; j++) { if (graph[i][j] != Integer.MAX_VALUE) { outEdgeNum[i]++; if (inEdge.get(j) == null) { List<Integer> list = new ArrayList<>(); list.add(i); inEdge.put(j, list); } else { inEdge.get(j).add(i); } } } } // 已访问的节点个数 List<Integer> visitedList = new ArrayList<>(nodeNum); // 循环遍历所有节点的出度 while (visitedList.size() < nodeNum) { for (int i = 0; i < nodeNum; i++) { if (outEdgeNum[i] == 0 && !visitedList.contains(i)) { visitedList.add(i); for (int temp = 0; inEdge.get(i) != null && temp < inEdge.get(i).size(); temp++) { outEdgeNum[inEdge.get(i).get(temp)]--; } break; } if ((i == nodeNum - 1) && visitedList.size() != nodeNum) { return new int[] {}; } } } // 反转集合元素 Collections.reverse(visitedList); int[] result = visitedList.stream().mapToInt(Integer::valueOf).toArray(); return result; } }
性能优化
方法一虽好但是使用集合太多,性能有瓶颈。优化方法是减少集合使用。
import java.util.HashMap; import java.util.Map; import java.util.HashSet; import java.util.Set; public class AlgorithmUtil { /** * 查找有向图的有序集合,如果有环返回空数组 * 根据每个节点的入度和出度计算,把出度为零的依次去掉并更改其前序节点的出度个数,统计最后访问过的节点 */ public static int[] findSequence(int[][] graph) { int nodeNum = graph.length; // 记录每个有入度的节点,及其所有的前序节点 Map<Integer, List<Integer>> inEdge = new HashMap<>(nodeNum); // 记录每个节点的出度个数 int[] outEdgeNum = new int[nodeNum]; // 初始化数据 for (int i = 0; i < nodeNum; i++) { for (int j = 0; j < nodeNum; j++) { if (graph[i][j] != Integer.MAX_VALUE) { outEdgeNum[i]++; if (inEdge.get(j) == null) { List<Integer> list = new ArrayList<>(); list.add(i); inEdge.put(j, list); } else { inEdge.get(j).add(i); } } } } int[] visited = new int[nodeNum]; int index = 0; Set<Integer> visitedSet = new HashSet<>(nodeNum); while (index < nodeNum) { for (int i = 0; i < nodeNum; i++) { if (outEdgeNum[i] == 0 && !visitedSet.contains(i)) { visited[index++] = i; visitedSet.add(i); for (int temp = 0; inEdge.get(i) != null && temp < inEdge.get(i).size(); temp++) { outEdgeNum[inEdge.get(i).get(temp)]--; } break; } if ((i == nodeNum - 1) && visitedSet.size() != nodeNum) { return new int[] {}; } } } reverseArray(visited); return visited; } /** * 数组反转 * @param array 数组 */ private static void reverseArray(int[] array) { for (int i = 0; i < array.length / 2; i++) { int temp = array[i]; array[i] = array[array.length - 1 - i]; array[array.length - 1 - i] = temp; } } }
测试用例
import org.junit.Test; public class AlgorithmUtilTest { @Test public void findSequence() { int[][] graph = new int[][] {{NAN, 1, 1, NAN}, {NAN, NAN, NAN, 1}, {NAN, NAN, NAN, 1}, {NAN, NAN, NAN, NAN}}; int[] resp = AlgorithmUtil.findSequence(graph); int[] goal = new int[] {0, 1, 2, 3}; int[] goal2 = new int[] {0, 2, 1, 3}; assert isEqual(resp, goal) || isEqual(resp, goal2); } @Test public void findSequence2() { int[][] graph = new int[][] {{NAN, 1, 1, NAN}, {1, NAN, NAN, 1}, {NAN, NAN, NAN, 1}, {NAN, NAN, NAN, NAN}}; int[] resp = AlgorithmUtil.findSequence(graph); int[] goal = new int[] {}; assert isEqual(resp, goal); } @Test public void findSequence3() { int[][] graph = new int[][] {{NAN, 1, 1, NAN}, {NAN, NAN, NAN, 1}, {NAN, NAN, NAN, 1}, {1, NAN, NAN, NAN}}; int[] resp = AlgorithmUtil.findSequence(graph); int[] goal = new int[] {}; assert isEqual(resp, goal); } @Test public void findSequence4() { int[][] graph = new int[][] {{NAN, 1, NAN, NAN, NAN, NAN, NAN}, {NAN, NAN, NAN, NAN, NAN, NAN, NAN}, {1, NAN, NAN, 1, NAN, NAN, NAN}, {1, NAN, NAN, NAN, NAN, NAN, NAN}, {NAN, NAN, 1, NAN, NAN, NAN, NAN}, {NAN, NAN, 1, NAN, 1, NAN, NAN}, {NAN, NAN, NAN, NAN, NAN, 1, NAN}}; int[] resp = AlgorithmUtil.findSequence(graph); int[] goal = new int[] {6, 5, 4, 2, 3, 0, 1}; assert isEqual(resp, goal); } private boolean isEqual(int[] numA, int[] numB) { if (numA.length == numB.length) { for (int i = 0; i < numA.length; i++) { if (numA[i] != numB[i]) { return false; } } return true; } return false; } }
知识背景
leetcode 210. 课程表 II
简单方法判断邻接矩阵的有向图是否有环如有不同见解,欢迎留言讨论
-
378.有序矩阵中第k小的元素(力扣leetcode) 博主可答疑该问题
2021-01-25 23:40:171.二维有序矩阵寻找值都是从右端到左端,和上端到下端 2.先定位在那两行,然后再寻找具体位置,下面一排的与上一排的最后一个比较,如果小于那就是上一排的最后一个,如果大于那就是下面那排的那个数 直接...一、笔记部分
思路:
1.二维有序矩阵寻找值都是从右端到左端,和上端到下端
2.先定位在那两行,然后再寻找具体位置,下面一排的与上一排的最后一个比较,如果小于那就是上一排的最后一个,如果大于那就是下面那排的那个数
直接暴力二分:
直接两端开始找,小于中间值所对应的次数,然后判断K与这个次数,确定在那个区间,然后直到找到那个数。
这样是错的: 返回的值 之前不能有任何的改变数据。 所以上图当count=k的时候,执行了Left加了1,肯定不行的。所以返回也应该是right,当等于的情况应该是right操作,left返回,因为条件是left小于等于right一直执行,所以left是不能动的!
1.二分法的:递归的条件,Left为枢纽
2.既然Left是枢纽,所以当等于的时候不能改变Left的值
3.所以等于的时候是变化right的值,Left是一直保持着值的。
4.返回Left
二、数组与矩阵类型的高频面试题汇总:
https://blog.csdn.net/qq_40262372/article/details/113150843
三、各种类型的高频面试题汇总:
https://blog.csdn.net/qq_40262372/article/details/112556249
四、如有疑问可加QQ群讨论:725936761 博主免费答疑
-
一个有向图具有拓扑序列,那么他的邻接矩阵必为 一个有向图具有有序拓扑序列,那么他的邻接矩阵必为
2020-12-15 11:27:09写在前边的话:你的支持是我写作的动力,有帮助到你的话麻烦点赞加收藏呦。感激不尽!...一个有向图具有有序拓扑序列,那么他的邻接矩阵必为(C) A.对称矩阵 B.系数矩阵 C.三角矩阵 D.一般矩阵 ...写在前边的话:你的支持是我写作的动力,有帮助到你的话麻烦点赞加收藏呦。感激不尽!如有错误也请留言指正。
考研数据结构练习,欢迎订阅我的专辑《考研数据结构题型分类讲解练习》
下边这两个题很具有混淆性,我也说不明白为啥,记住吧。
一个有向图具有拓扑序列,那么他的邻接矩阵必为(D)
A.对称矩阵
B.系数矩阵
C.三角矩阵
D.一般矩阵一个有向图具有有序拓扑序列,那么他的邻接矩阵必为(C)
A.对称矩阵
B.系数矩阵
C.三角矩阵
D.一般矩阵 -
二元关系的矩阵和图表示
2015-08-05 17:03:04两个事物之间的关系称之为二元关系。在数学上,二元关系指的是这样的一个集合S,它的所有元素都为二元有序对。它反映的是有序对中第一个...而除此之外,还可以用其他数学工具来描述它——矩阵和图。矩阵的基本元素是数两个事物之间的关系称之为二元关系。在数学上,二元关系指的是这样的一个集合S,它的所有元素都为二元有序对。它反映的是有序对中第一个元素组成的集合与第二个元素组成的集合之间的关系。举个例子,集合S={<天秤座,libra>,<狮子座,leo>} 就表示了中文集合{天秤座,狮子座}与英文集合{libra,leo}之间的对应关系。
二元关系可以用集合表示,就像我们上面提到的。而除此之外,还可以用其他数学工具来描述它——矩阵和图。矩阵的基本元素是数字及其所处的位置。直觉上,我们很自然的想到用它的下标来体现两个集合中的元素,用数字体现它们是否具有关系。这便得出了以下定义:
【定义】设集合A={x1,x2,…,xm},B={y1,y2,…,yn},R为A,B之间的二元关系。称矩阵M(R)=(rij)m×n为R的关系矩阵,其中
这样我们定义了一个映射,把集合R映射为一个矩阵M。如此定义,首先保证了R的集合表达式和R的关系矩阵是一一对应的。其次,这样的定义会带来很多好的性质。我们可以应用矩阵的语言把整个二元关系的理论重新叙述一遍:
- 关系R的逆,记作R-1,表示的是集合{<x,y>|<y,x>εR},我们有 M(R-1)=(M(R))T. 这样,我们求关系的逆就转化为了求一个矩阵的转置矩阵。
- 两个关系的合成(复合),记作R2•R1,表示的是集合
为了用矩阵表示关系的合成,我们可以定义{0,1}中元素的加法为逻辑加法(0+0=0,0+1=1,1+0=1,1+1=1),于是便有
M(R2•R1)=M(R1)•M(R2)
这样,关系的合成这一运算就转化为了矩阵的相乘。
- R在D上的限制就等价于找M(R)中相应行中为1的元素;D在R下的象就等价于M(R)中相应行为1的元素的列坐标。
- 关系R是单根的,指的是对任意的yεranB,存在唯一的xεdomR,使得<x,y>εR。这意味着M(R)的每一列有且仅有一个1
- 关系R是单值的,指的是对任意的xεdomR,存在唯一的yεranB,使得<x,y>εR。这意味着M(R)的每一行有且仅有一个1
特殊的,集合A上的二元关系R指的是A×A={<x,y>|xεA,yεA}。这样像前面第二条性质就有M(R2)=(M(R))2
- 自反的二元关系R相应的关系矩阵主对角线元素都为1
- 反自反的二元关系R相应的关系矩阵主对角线元素都为0
- 对称的二元关系R相应的关系矩阵也是对称的
- 反对称的二元关系R相应的关系矩阵也是反对称的(这里定义1的反为0)
- 对传递的二元关系R,相应的关系矩阵R中若rij=1,rjk=1,则rik=1
等价关系R(同时具有自反,对称,传递性质的二元关系)可以确定集合A上的一个划分,那么如何从关系矩阵中找出相应的等价类?如下图所示:
如何用图来表示等价关系呢?由于关系中的元素是有序对,直觉上,我们很自然的想到用有向图。于是定义如下:
【定义】设集合A={x1,x2,…,xm},B={y1,y2,…,yn},R为A,B之间的二元关系。以A,B中的元素为顶点,若<xi,yj>εR,则从顶点xi向yj引有向边,称所画出的图G(R)为R的关系图。
这样,我们就可以用图论的语言把整个二元关系的理论重新叙述一遍:- R的逆:只需把图中的箭头反向
- 两个关系的合成:通过过渡集合把两个图拼接为一个图,然后把长为2的有向通路变为起点指向终点的长为1的有向通路
- R在D上的限制就等价于找G(R)中起点包含在集合D中的部分;D在R下的象就等价于G(R)中包含在集合D中的起点所指向的终点
- 关系R是单根的,指B中顶点的入度均为1
- 关系R是单值的,指A中顶点的出度均为1
特殊的,集合A上的二元关系R对应的关系图将为多重图(有重边和环的出现)。
- 自反的二元关系R相应的关系图每个顶点处都有环
- 反自反的二元关系R相应的关系图每个顶点处都无环
- 对称的二元关系R相应的关系图中两个顶点间如果存在有向边,必有两条反向的有向边
- 反对称的二元关系R相应的关系图中两个顶点间的有向边必是单重的
- 对传递的二元关系R,相应的关系图中长度为2的有向通路的起点和终点间必存在由起点指向终点的有向线段
如何从关系图中找出一个等价关系所确定的划分?
对于二元关系中的其他一些理论(如闭包和序关系),用关系矩阵和关系图描述一下试试。我们经常把一件事物抽象为数学模型来表达。有时换一种数学工具可能在处理某些运算时给我们带来方便。用不同的工具思考,能更深刻的理解数学各个分支之间的联系。关于Discrete Mathematics更多讨论与交流,敬请关注本博客和新浪微博songzi_tea.
- 关系R的逆,记作R-1,表示的是集合{<x,y>|<y,x>εR},我们有 M(R-1)=(M(R))T. 这样,我们求关系的逆就转化为了求一个矩阵的转置矩阵。
-
【顺时针有序螺旋矩阵扭起来】Python 正整数矩阵中任意数到1的曼哈顿距离 小练习系列第三弹
2020-03-07 03:52:17在某人工智能培训班看到这个预热练习,继续...矩阵如下图: 原题目:【再次吐槽。。】 Spiral Memory You come across an experimental new kind of memory stored on an infinite two-dimensional grid. Each sq... -
图的邻接矩阵
2016-03-16 21:39:41在有向图中,结点对,y>是有序的,结点对,y>称为从结点x到结点y的一条有向边,因此,,y>与,x>是两条不同的边。有向图中的结点对,y>用一对尖括号括起来,x是有向边的始点,y是有向边的终点,有向图中的边也称作弧... -
搜索有序二维矩阵(从右上角开始)
2020-05-07 21:44:55如下图所示,右上角的值 ,是它所在行的最大值,也是它所在列的最小值。 所以如果 target 大于右上角的值,那么 target 比右上角所在行的值都要大,这一行就排除了。 如果 target 小于右上角的值,那么 target 比右... -
java邻接图_java 图的邻接矩阵
2021-02-12 14:47:12有向图 在有向图中,结点对,y>是有序的,结点对,y>称为从结点x到结点y的一条有向边,因此,,y>与,x>是两条不同的边。有向图中的结点对,y>用一对尖括号括起来,x是有向边的始点,y是有向边的终点,有向图中的边... -
java 图的邻接矩阵
2017-11-14 14:42:00有向图 在有向图中,结点对,y>是有序的,结点对,y>称为从结点x到结点y的一条有向边,因此,,y>与,x>是两条不同的边。有向图中的结点对,y>用一对尖括号括起来,x是有向边的始点,y是有向边的终点,有向图中的边... -
螺旋矩阵II与合并两个有序数组
2018-11-17 00:00:00leetcode攀登之旅(19)【今日知图】选中文本(可视模式)v可视模式从光标位置开始按照正常模式选择文本 V可视行模式选中光标经过的完整行 ctrl+v可视... -
Practice1+将无序图像重命名为有序图像+将图像保存到指定文件夹
2020-07-13 10:27:09算法 使用cv::glob函数将path下所有文件...定义一个图像矩阵src,将原路径下图像逐张赋值给src 使用sprintf为每张图像重命名,根据i命名,赋给Rename 使用imwrite保存地址和图像名称 代码 #include <iost -
Java之图的邻接矩阵
2019-05-04 09:13:34有向图 在有向图中,结点对,y>是有序的,结点对,y>称为从结点x到结点y的一条有向边,因此,,y>与,x>是两条不同的边。有向图中的结点对,y>用一对尖括号括起来,x是有向边的始点,y是有向边的终点,有向图中的边... -
数据结构的数组、矩阵、图、查找,排序
2020-05-18 14:05:51现在先来认识一下矩阵和数组,一些矩阵的日常应用。首先来看一下数组,所谓的数组是有序的元素序列,而数组是我们日常常见的,而数组的元素要怎样去理解呢,数组元素简单来说就是存放在每个格中的内容值,而在一些C... -
opencv矩阵转eigen_分别用Eigen和C++(OpenCV)实现图像(矩阵)转置
2021-01-15 07:53:47git(3)、矩阵(matrix):矩阵是一个二维数组,其中的每个元素被两个索引而非一个所肯定。github(4)、张量(tensor):在某些状况下,咱们会讨论坐标超过两维的数组。通常地,一个数组中的元素分布在若干维坐标的规则... -
初识图,图的存储(邻接矩阵,邻接链表)和深搜遍历
2015-12-01 17:25:131.图的基本概念(1)图是由顶点集合与顶点间的关系集合组成的一种数据结构 ... (2)有序图:顶点对(v1, v2)是有序的;无序图:顶点对(v1, v2)是无序的。 (3)无向边:若顶点vi, 到vj之间的 -
论文研究-基于有序数据聚类的图像自适应分条算法.pdf
2019-07-22 19:48:59为了将图像中内容特征相近的像素尽可能分割到同一区块,提高图像分割的针对性和自适应性,提出了一种基于有序数据聚类的图像自适应分条算法。该算法首先计算图像中所有像素点的梯度值,相加每列像素梯度值得到列累积... -
图的简单认识及邻接矩阵及邻接表存储
2018-05-05 18:36:33如果点对是有序的(每一个点的下一个点是固定的),那么图被称为有向图,否则就是无向图。与图的边相关的数值叫做权值,带权的图称为网(network). 与图有关的简单概念: (1)如果图中含有一条从一个顶点到他... -
数据结构—无向图创建邻接矩阵、深度优先遍历和广度优先遍历(C语言版)
2020-12-19 17:25:49无向图创建邻接矩阵、深度优先遍历和广度...如果E中的顶点对是有序的,即E中的每条边都是有方向的,则称G是有向图。如果顶点对是无序的,则称G是无向图 (2)邻接矩阵: 邻接矩阵主要由:二维数组 实现 如图 转 -
无向无权图的邻接矩阵和邻接表的输出
2019-10-04 21:29:421.1向邻接表中插入一个数据,并保证邻接表的有序性 void insertIntoAdjVertics(struct vNode** adjVertics, int start, int end)//向邻接表中插入一个数据,并保证邻接表的有序性 { struct vNode* node = (struct ... -
算法练习day9——190327(“之” 字形打印矩阵、在行列都排好序的矩阵中找数、打印两个有序链表的公共部分...
2019-03-27 19:54:291.“之” 字形打印矩阵 【题目】 给定一个矩阵matrix, 按照“之” 字形的方式打印这个矩阵, 例如: 1 2 3 4 5 6 7 8 9 10 11 12“之” ...1.设置两个点A,B,起始位置如图: A每次向右走,走到最右边的时候... -
数据结构之图(C++)--邻接矩阵表示(一)
2016-11-18 23:06:32数据结构之图(C++)–邻接矩阵表示(一)基本概念简单地说,图是一个用线或边链接爱一起的顶点或节点的集合。严格地说,图是有限集V和E的有序对,即G=(V,E),其中V的元素称为顶点(也称节点或点),E的元素称为... -
数据结构与算法(Java描述)-20、图、图的邻接矩阵、有向图的广度优先遍历与深度优先遍历
2018-07-14 15:22:58有向图: 在有向图中,结点对,y>是有序的,结点对,y>称为从结点x到结点y的一条有向边,因此,,y>与,x>是两条不同的边。有向图中的结点对,y>用一对尖括号括起来,x是有向边的始点,y是有向边的终点,有向图中的... -
邻接矩阵画最小生成树普里姆_离散数学第七章图与树
2020-11-21 09:01:53图与树图的基本概念图及其图解表示 一个图 G 是一个有序二元组(V, E),记作 G = (V, E)V是一个非空的有限集合,V 中的元素称为图 G 的结点或顶点V 称为图 G 的结点集,记作 V(G)E是一个由 V 中元素构成的对偶的... -
数据结构-图的创建(邻接矩阵,邻接表)C语言实现
2020-06-04 18:54:59图的定义: 图(Graph)G由两个集合V和E组成,记为:G=(V,E)...是有序的,表示它从V到W的一条有向边。所以,<W,V>表示的和<V,W>不同的边,顶点的指向不同。有向图中顶点对用尖括号表示<>,<x,y> -
数组与矩阵
2020-05-08 10:40:17一、数组:是有序的元素序列 有序:存储方式 元素:数组当中的内容或者值 序列:有多个值 一维数组:a[1],a[2],…a[n]; 二维数组释义:一维数组的每个元素都是一维数组(一张纸) 三维数组释义:一维数组的每个元素... -
稀疏矩阵的压缩存储
2021-01-31 19:58:23如图是一个三元组顺序表,三元组顺序表又称有序的双下标法 三元组的优点:非零元在表中按行列有序存储,因此便于进依行顺序处理的矩阵运算。 缺点:不能随机存取。若要按行号存取某一行中的非零元,需要从头开始进行...
-
关于java环境变量总是指向旧地址的问题
-
人力资源管理为什么需要自动化审批?
-
建立学生信息管理系统.doc
-
Docker从入门到精通
-
DHCP 动态主机配置服务(在Linux环境下,配置单网段或跨网段提)
-
干货:计算机网络知识总结
-
PxCook.zip
-
Windows系统管理
-
第1单元 电子课件.ppt
-
vue 基础知识点
-
log4日志j的使用
-
华为数据中心认证 HCIE-DC LAB实验考试配置2-v2
-
阴影效果
-
Python爬取唐人街探案3豆瓣短评并生成词云
-
使用 Linux 平台充当 Router 路由器
-
shenjirizhi.zip
-
Liunx 优化思路与实操步骤
-
357.至少有K个重复字符的最长子串
-
MySQL 高可用(DRBD + heartbeat)
-
MaxScale 实现 MySQL 读写分离与负载均衡