FTD几种图的存储结构的比较.ppt

几种图的存储结构的比较 FTD小组制作 图的几种主要存储结构 邻接矩阵邻接表十字链表邻接多重表 无向图的邻接矩阵实现方法 二维数组优点 1 易判断两点间的关系2容易求得顶点的度 有向图的邻接矩阵 网的邻接矩阵 邻接矩阵 实现方法 二维数组优点 1 易判断两点间的关系2容易求得顶点的度缺点 占用空间大 边数比顶数小得多 时间复杂度 O n n2 e n个顶点e条边 无向图的邻接表 数据域指针域邻接点域实现方法 链表优点 1 节省空间2容易求得顶点的度 有向图的邻接表 网的邻接表 邻接表 实现方法 链表优点 1 节省空间2 易得到顶点的出度缺点 1 不易判断两点间的关系2 不易得到顶点的入度时间复杂度 O n m 或O n m 十字链表 它是有向图的另一种链式存储结构 思路 将邻接矩阵用链表存储 是邻接表 逆邻接表的结合 1 开设弧结点 设5个域 每段弧是一个数据元素 2 开设顶点结点 设3个域 每个顶点也是一个数据元素 弧结点 顶点结点 tailvex 弧尾顶点位置headvex 弧头顶点位置hlink 弧头相同的下一弧位置tlink 弧尾相同的下一弧位置info 弧信息 data 顶点信息firstin 以顶点为弧头的第一条弧结点firstout 以顶点为弧尾的第一条弧结点 十字链表 实现方法 链表优点 1 空间要求较小2 易求得顶点的出度和入度缺点 结构较复杂时间复杂度 O n m 或O n m 邻接多重表 这是无向图的另一种链式存储结构 当对边操作时建议采用此种结构存储 1 设立边结点 6个域 每条边是一个数据元素 2 设立顶点结点 2个域 每个顶点也是一个数据元素 边结点 mark 标志域 标记该边是否被搜索过 ivex jvex 边依附的两个顶点位置ilink 指向下一条依附顶点i的边位置Jlink 指向下一条依附顶点j的边位置info 边信息 顶点结点 data 存储顶点信息firstedge 依附顶点的第一条边结点 邻接多重表 实现方式 链表优点 1 节省空间2 易判断两点间的关系缺点 结构较复杂时间复杂度 O n m 或O n m 谢谢观赏