文章目录
  1. 图的定义
  2. 图的表示
  3. 拓扑排序

图的定义

一个图由顶点集与边集组成，边就是一个点对；

图分为有向图和无向图，若无向图中任意两个点均存在一条路径，则称它是连通的；对于有这种性质的有向图，称为强连通的，否则，若其对应的无向图是连通的，则该有向图称为弱连通的。若每一对顶点之间均存在一条边，则该图称为完全图。

图的表示

第一种表示方式为使用一个二维数组，称为邻接矩阵；对每条边(u,v)，置A[u][v]=1，其余元素为0；若要对边赋权，则可以用很大或很小的权，如$\infty$代表不存在的航线。这种表示方式简单，但是在图的边比较稀疏时，这种表示方式代价很大；于是，有了特意为稀疏图准备的表示方式——邻接表。

邻接表对每个顶点，用一个链表存储其相邻的顶点。

拓扑排序

拓扑排序是对有向无环图的一种排序：若存在一条从u到v的路径，则在排序中u应该出现在v之前。

拓扑排序的算法如下。

初始时：先遍历图中所有顶点求其入度，并将入度为0的顶点存入集合S，所有节点的入度存入一个数组A用来记录；

循环：每轮删除S中的一个顶点，并将该顶点指向的顶点的入度减1，即更新数组A，然后将入度刚成为0的顶点存入S中；

直到图中所有顶点删除完毕，各顶点按照删除的顺序为序。