有向图和无向图以及拓扑的复习
备注：大一学了图后，一段时间没用就还给老师了，如今重新复习一下，理解有误的地方请指教。
有向图和无向图的定义
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.不管是关联矩阵还是领接矩阵都是针对有向图而言的。2.关联矩阵是针对边来说的，所以矩阵大小为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 的前面。
（2）注意，拓扑排序并不是唯一的，它的排序方式：以上图为例子：a.首先我们从有向图图中选择一个没有前驱（即入度为0）的顶点并输出，这里我们可以选择c0或者c1。b.从图中删除输出的顶点和所有以它为起点的有向边。c.循环 a步骤 和 b步骤，终止条件为当前的有向图为空或当前图中不存在无前驱的顶点为止。备注：若当前图中不存在无前驱的顶点，说明有向图中必然存在环。