本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!