图-存储结构-邻接矩阵

使用邻接矩阵存储图时需要两个数组，一个数组存放图中顶点本身的数据（一维数组），另外一个数组用于存储各顶点之间的关系（二维数组）。

存储图中各顶点本身数据，使用一维数组就足够了；存储顶点之间的关系时，要记录每个顶点和其它所有顶点之间的关系，所以需要使用二维数组。
不同类型的图，存储的方式略有不同， 根据图有无权，可以将图划分为两大类：图和网 。
图，包括无向图和有向图；网，是指带权的图，包括无向网和有向网。存储方式的不同，指的是：在使用二维数组存储图中顶点之间的关系时，如果顶点之间存在边或弧，在相应位置用 1 表示，反之用 0 表示；如果使用二维数组存储网中顶点之间的关系，顶点之间如果有边或者弧的存在，在数组的相应位置存储其权值；反之用 0 表示。（这里对于网我们用0只是因为这样表示两个顶点之间没有关系起来非常方便，习惯上我们平时都是用正无穷大来表示）。
对于无向图：顶点vi的度是邻接矩阵第i行或第i列的元素的和。对于有向图：第i行元素的和是顶点vi的出度，第j列元素的和是顶点vj的入度。

生成树与生成森林

  • 对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树。
  • 一个连通图的生成树是极小连通子图,它含有图中全部顶点。但只有足以构成一棵树的n-1条边。
  • 一棵有n个顶点的生成树有且仅有n-1条边。如果一个图有n个顶点和n-1条边，则是非连通图；如果它多于n-1条边，则一定有环。但是，有n-1条边的图不一定是生成树。
  • 连通图中，由于任意两顶点之间可能含有多条通路，遍历连通图的方式有多种，往往一张连通图可能有多种不同的生成树与之对应。
  • 生成树是对应连通图来说，而生成森林是对应非连通图来说的。

拓扑排序的时间复杂度

如果AOV网络有n个顶点，e条边，在拓扑排序的过程中，搜索入度为零的顶点所需的时间是O(n)。在正常情况下，每个顶点进一次栈，出一次栈，所需时间O(n)。每个顶点入度减1的运算共执行了e次。所以总的时间复杂为O(n+e)。