- 1【编程实践】Google Guava 极简教程
- 2Python下使用OpenCV_opencv-python 版本与numpy 关系对应
- 3在Idea中使用git_idea git窗口
- 4关于Anaconda3安装的tensorflow-gpu使用时出现报错Could not find ‘cudart64_100.dll解决方法_could not found cudart
- 5【机器学习-14】K-means聚类算法：原理、应用与优化_改成随机化初始聚类中心_kmeans推荐算法可以使用余弦相似度吗
- 6东方通TongWeb结合Spring-Boot使用_tongweb springboot
- 7Phoenix启动过程出现的问题_phoenix启动后没有master
- 8如何给自己的网站添加 https ssl 证书_如何给网站添加证书
- 9Could not extract response: no suitable HttpMessageConverter found for ..content type [text/html...]
- 10如何理解李彦宏说的“不要卷模型，要卷应用？
有向图和无向图以及拓扑的复习_拓扑 有向循环图
赞
踩
备注：大一学了图后，一段时间没用就还给老师了，如今重新复习一下，理解有误的地方请指教。
有向图和无向图的定义
1）关于有向图，百科中是这样描述的：一个有向图D是指一个有序三元组(V(D)，A(D)，ψD)，其中ψD为关联函数，它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对。
理解：如图D，如果e是D的一条边，而这时候存在这样的一个关系，ψD，有A，B两点，使得，ψD（A，B）=e（到底是怎样的关系？我觉得在应用中，需要我们自己制定，就像在预算100元的条件下，你选择怎样的交通工具快速到达目的地），通俗理解：边有方向的图。即AB ！= BA。
（2）平行边：在图中，如果起点和终点相同则称为平行边，平行边的条数则称为重数。如图：e2和e3为平行边，B和C之间的重数为2。
（3）关于无向图：了解了有向图，那它就好理解了，就是有向图中去掉所有的方向，AB=BA，如图，就是去掉D中的所有箭头（此时，又称为基础图，反之给无向图添上箭头的有向图又称为定向图）。
（4）出度和入度：如图D，以点A为例子，在所有与A关联的边中，以A为起点的边的条数称为出度。而入度则刚好相反，以A为终点的边的条数则称为入读。其中，入度+出度，我们称为A的度。注意特殊情况：如图：A有一个自环，起点和终点都是自己，此时出度算一度，入度也算一度。如图：A的出度为3，入度也为2，A的度的5。
（5）邻接矩阵和关联矩阵定义：设D（V,E）是有向图，其中V={v1,v2,v2…vn},E={e1,e2,e3,…em}称A(D)=(aij)nxn是D的领接矩阵，其中aij是以vi为起始点，以vj为终点的边的条数。若图D中无环，则称M(D)=（mij）nxm为关联矩阵。[i，j是下标，n是点的个数，m是边的数量注意：1.关联矩阵是针对边来说的，所以矩阵大小为n*m，它的取值如下：
例子：
（6）补充：对于无向图而言：邻接矩阵则是对称的，且只有0和1，因为没有方向的区别后，要么有边，要么没边：
从图我们可以看到，它是关于对角线对称的一个矩阵，我们在编程中，遍历和存储是只需要关注上半部分或者下半部分即可。
（7）跟邻接矩阵一样，用来存储图中信息的，还有邻接表：如果学过链表了，就很好理解了，首先在一个数组中存储各个点（对象或者成为链），而每个对象又保存着一个next引用指向连接的点在数组中的坐标，如图：A到E在数组中存储后，坐标依次排列，A连B，B的坐标为1，所以指向的地方标记为1，代表A连着B，接着，B连着E，E的坐标为4，这1的引用指向4。
从图我们就可以得出邻接表的存储方式了：即链表加数组，这存储结构比起纯粹用数组（邻接矩阵）要节约很多空间。邻接矩阵，我们需要一个n*n维的数组，复杂度为O（n^2），而邻接表是根据点和边来保存数据的，当一个起点决定后，就采用深度搜索的方法沿着边，保存连接点的信息，复杂度为O(n+m）
另外，若果是有向图，我们在保存下一个顶点时，还需要保存边的权值，看图中每个格子都分成两小格了吗，第二个小格子就是用来存储权值的。
图来自百度词条，好难画
拓扑排序
百度词条这样描述：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
理解:（1）根据定义，我们可以知道它是针对有向图而言的.（2）它是一个包含有向图的所有点的线性序列，且满足两个条件：a.有向图的每个顶点只出现一次。b.若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 应该出现在顶点 B 的前面。
备注：图来源于百度，之前都没发现，它的786，应该是678，C0是连着C2和C6的
[外链图片转存失败(img-q5yfBWrf-1567908307464)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539485618410_F203E6F40B767104E9635E84C103CA7C “图片来源于百科”)]
（2）注意，拓扑排序并不是唯一的，它的排序方式：以上图为例子：a.首先我们从有向图图中选择一个没有前驱（即入度为0）的顶点并输出，这里我们可以选择c0或者c1。b.从图中删除输出的顶点和所有以它为起点的有向边。c.循环 a步骤 和 b步骤，终止条件为当前的有向图为空或当前图中不存在无前驱的顶点为止。备注：若当前图中不存在无前驱的顶点，说明有向图中必然存在环。
