图的逻辑结构特征就是其结点(顶点)的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。
图GraphG=(V,E)，V是顶点的有穷非空集合，E是顶点偶对的有穷集。
有向图Digraph：每条边有方向；无向图Undigraph：每条边没有方向。
有向完全图：具有n*(n-1)条边的有向图；无向完全图：具有n*(n-1)/2条边的无向图；
有根图：有一个顶点有路径到达其它顶点的有向图；简单路径：是经过顶点不同的路径；简单回路是开始和终端重合的简单路径；
网络：是带权的图。
图的存储结构：·邻接矩阵表示法：用一个n阶方阵来表示图的结构是唯一的，适合稠密图。 ·无向图：邻接矩阵是对称的。
·有向图：行是出度，列是入度。
建立邻接矩阵算法的时间是O(n+n^2+e),其时间复杂度为O(n^2)
·邻接表表示法：用顶点表和邻接表构成不是唯一的，适合稀疏图。·顶点表结构 vertex | firstedge，指针域存放邻接表头指针。
·邻接表：用头指针确定。 ·无向图称边表；
·有向图又分出边表和逆邻接表；
·邻接表结点结构为 adjvex | next，
时间复杂度为O(n+e).，空间复杂度为O(n+e).。
图的遍历： ·深度优先遍历：借助于邻接矩阵的列。使用栈保存已访问结点。
·广度优先遍历：借助于邻接矩阵的行。使用队列保存已访问结点。
生成树的定义：若从图的某个顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图称作该图的生
成树。
最小生成树：图的生成树不唯一，从不同的顶点出发可得到不同的生成树，把权值最小的生成树称为最小生成树(MST)。
构造最小生成树的算法： ·Prim算法的时间复杂度为O(n^2)与边数无关适于稠密图。
·Kruskal算法的时间复杂度为O(lge),主要取决于边数，较适合于稀疏图。
最短路径的算法：·Dijkstra算法，时间复杂度为O(n^2).·类似于prim算法。
拓扑排序：是将有向无环图G中所有顶点排成一个线性序列，若∈E(G)，则在线性序列u在v之前，这种线性序列称为拓扑序列。
拓扑排序也有两种方法：·无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列。
·无后继的结点优先：每次输出一个无后继的结点并删去此结点及其入边，最后得到的序列是逆拓扑序列。
⊙小编提示：添加【山东自考网】招生老师微信，即可了解2023年山东自考政策资讯、自考报名流程、准考证打印方法、成绩查询时间以及领取历年真题资料、个人专属备考方案等相关信息！
（添加“山东自考网”招生老师微信，在线咨询报名报考等相关问题）
《山东自考网》免责声明：
（一）由于考试政策等各方面情况的不断调整与变化，本网站所提供的考试信息仅供参考，请以省考试院及院校官方发布公布的正式信息为准。
（二）本站文章内容信息来源出处标注为其他平台的稿件均为转载稿，免费转载出于非商业性学习目的，版权归原作者所有。如您对内容、版权等问题存在异议请与本站联系，我们会及时进行处理解决，联系邮箱：812379481@qq.com。
