精华内容
下载资源
问答
  • 简单方法查找邻接矩阵有向有序集合求解思路实现代码测试用例知识背景 求解思路 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
    简单方法判断邻接矩阵的有向图是否有环

    如有不同见解,欢迎留言讨论

    展开全文
  • 1.二维有序矩阵寻找值都是从右端到左端,和上端到下端 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 博主免费答疑

    展开全文
  • 写在前边的话:你的支持是我写作的动力,有帮助到你的话麻烦点赞加收藏呦。感激不尽!...一个有向具有有序拓扑序列,那么他的邻接矩阵必为(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.



    展开全文
  • 在某人工智能培训班看到这个预热练习,继续...矩阵如下: 原题目:【再次吐槽。。】 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是有向边的终点,有向中的边也称作弧...
  • 如下所示,右上角的值 ,是它所在行的最大值,也是它所在列的最小值。 所以如果 target 大于右上角的值,那么 target 比右上角所在行的值都要大,这一行就排除了。 如果 target 小于右上角的值,那么 target 比右...
  • 有向 在有向中,结点对,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是有向边的终点,有向中的边...
  • leetcode攀登之旅(19)【今日知】选中文本(可视模式)v可视模式从光标位置开始按照正常模式选择文本 V可视行模式选中光标经过的完整行 ctrl+v可视...
  • 算法 使用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是有向边的终点,有向中的边...
  • 现在先来认识一下矩阵和数组,一些矩阵的日常应用。首先来看一下数组,所谓的数组是有序的元素序列,而数组是我们日常常见的,而数组的元素要怎样去理解呢,数组元素简单来说就是存放在每个格中的内容值,而在一些C...
  • git(3)、矩阵(matrix):矩阵是一个二维数组,其中的每个元素被两个索引而非一个所肯定。github(4)、张量(tensor):在某些状况下,咱们会讨论坐标超过两维的数组。通常地,一个数组中的元素分布在若干维坐标的规则...
  • 1.的基本概念(1)是由顶点集合与顶点间的关系集合组成的一种数据结构 ... (2)有序图:顶点对(v1, v2)是有序的;无序:顶点对(v1, v2)是无序的。 (3)无向边:若顶点vi, 到vj之间的
  • 为了将图像中内容特征相近的像素尽可能分割到同一区块,提高图像分割的针对性和自适应性,提出了一种基于有序数据聚类的图像自适应分条算法。该算法首先计算图像中所有像素点的梯度值,相加每列像素梯度值得到列累积...
  • 如果点对是有序的(每一个点的下一个点是固定的),那么被称为有向,否则就是无向。与的边相关的数值叫做权值,带权的称为网(network). 与有关的简单概念: (1)如果中含有一条从一个顶点到他...
  • 无向创建邻接矩阵、深度优先遍历和广度...如果E中的顶点对是有序的,即E中的每条边都是有方向的,则称G是有向。如果顶点对是无序的,则称G是无向 (2)邻接矩阵: 邻接矩阵主要由:二维数组 实现 如
  • 1.1向邻接表中插入一个数据,并保证邻接表的有序性 void insertIntoAdjVertics(struct vNode** adjVertics, int start, int end)//向邻接表中插入一个数据,并保证邻接表的有序性 { struct vNode* node = (struct ...
  • 1.“之” 字形打印矩阵 【题目】 给定一个矩阵matrix, 按照“之” 字形的方式打印这个矩阵, 例如: 1 2 3 4 5 6 7 8 9 10 11 12“之” ...1.设置两个点A,B,起始位置如: A每次向右走,走到最右边的时候...
  • 数据结构之(C++)–邻接矩阵表示(一)基本概念简单地说,是一个用线或边链接爱一起的顶点或节点的集合。严格地说,是有限集V和E的有序对,即G=(V,E),其中V的元素称为顶点(也称节点或点),E的元素称为...
  • 有向: 在有向中,结点对,y>是有序的,结点对,y>称为从结点x到结点y的一条有向边,因此,,y>与,x>是两条不同的边。有向中的结点对,y>用一对尖括号括起来,x是有向边的始点,y是有向边的终点,有向中的...
  • 与树图的基本概念及其图解表示 一个 G 是一个有序二元组(V, E),记作 G = (V, E)V是一个非空的有限集合,V 中的元素称为 G 的结点或顶点V 称为 G 的结点集,记作 V(G)E是一个由 V 中元素构成的对偶的...
  • 的定义: (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
    是一个三元组顺序表,三元组顺序表又称有序的双下标法 三元组的优点:非零元在表中按行列有序存储,因此便于进依行顺序处理的矩阵运算。 缺点:不能随机存取。若要按行号存取某一行中的非零元,需要从头开始进行...

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 248
精华内容 99
关键字:

有序矩阵图