本文共 1074 字，大约阅读时间需要 3 分钟。

线性表中，数据元素叫做元素，仅有线性关系，每个元素之间只有一个前驱和一个后继。树形结构中，数据元素叫做结点，结点之间有明显的层次关系，结点只有一个父节点，但是可以有多个子结点。图是一种比线性结表和树更加复杂的数据结构，可以表示多对多的数据关系。

一、基本概念：

1.图的定义：图是由顶点的有穷非空集合和顶点之间边的集合组成。通用表示为G(V,E)，其中G表示一个图（graph），V是图中2顶点集合，E是边的集合。所以图结构不允许没有顶点，边集可以是空的。

2.无向边：顶点Vi到Vj之间的边没有方向，这条边就是无向边，记作（Vi,Vj）或者（Vj,Vi）。注意是小括号，是无序偶对。

3.有向边：从顶点Vi到Vj的边有方向，这条边就是有向边，记作<Vi,Vj>，其中Vi是狐尾，Vj是狐头。注意是尖括号，是有序偶对。

4.无向图：图中任一边都是无向边，特别的，如果任意两个顶点之间都有边，称为无向完全图。对于完全图有性质如下：若有n个顶点，那么完全图有条边，因为每个顶点都要和剩下的n-1个顶点相连，总共有n个顶点，但是整体的边重复了一遍，所以除以2。

5.有向图：图中任一边都是有向边，特别的，如果任意两个顶点之间都有边，称为有向完全图。对于完全图有性质如下：若有n个顶点，那么完全图有条边。

6.网：带权值的图。

7.图的顶点和边之间的关系：

（1）对于无向图，顶点v的度（和v相关联的边的数目）记作TD(v)，那么图的边的数目为：

（2）对于有向图，顶点v的入度记为ID(v)，出度记为OD(v)，则TD(v)=ID(v)+OD(v)，那么图的边的数目为：

8.图的存储结构有两种：

邻接矩阵：空间复杂度和时间复杂度都为O(n^2)，对于无向图的邻接矩阵是一个对称矩阵，对角线为0.

邻接表：空间复杂度和时间复杂度都为O(n+e)

9.拓扑排序算法：时间复杂度O(n+e)

拓扑排序就是对一个有向图构造拓扑序列的过程，拓扑序列就是若从vi到vj有一条路经，则定点序列中的顶点i必须在顶点j之前。

不存在回路的图叫做AOV网，对AOV网进行拓扑排序的基本思路是：从AOV网中选择一个入度为0的顶点输出，然后删除此点同时删除以此点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

整个算法，对一个具有n个顶点e条弧的AOV网来说，首先扫描顶点表，将入度为0的顶点入栈的时间复杂度为O(n)，而之后的while循环中，每个顶点入一次栈，出一次栈，入度减1的操作共执行了e次。所以整个算法的时间复杂度为O(n+e)

转载地址：https://blog.csdn.net/zz2230633069/article/details/103259415 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！