3.3 KiB
3.3 KiB
图
网
带权的图就是网
图的存储结构
邻接矩阵(顺序存储)
- 顶点数组：存储顶点信息
- 边数组:存储顶点数组中2个顶点关系和权
- 图{顶点数组，边数组，顶点数，边数，图类型}
不适合:查找顶点的度，需要扫描整张边数组，效率低，对顶点的相关操作 适合:对边依次进行处理的操作，
邻接表(链式存储)
- 表头结点：存储顶点信息(data)和第一个邻接点地址(firstarc)，一般顺序存储在一个数组中
- 表中结点：存储表头结点在数组中的位置和下一个结点的指针，可存储权值
- 图{表头结点数组，顶点数，边数，图类型}
特点:
- 出度为各自链表中的结点数，入度需要遍历整个表的结点，还有一种方法，求入度，建立一个逆邻接表
- 稀疏图存储时，比使用邻接矩阵节省空间
十字链表(链式存储)
- 顶点结点:存储顶点信息(data) 一个弧头结点指针(firstin) 一个弧尾结点指针(firstout)
- 弧结点:tailvex 和 headvex 分别存储的是弧尾和弧头对应的顶点在数组中的位置下标； hlink 和 tlink 为指针域，分别指向弧头相同的下一个弧和弧尾相同的下一个弧； info 为指针域，存储的是该弧具有的相关信息，例如权值等
- 图{顶点结点数组，弧数，顶点数}
特点:
- 存储的是有向图或者有向网
- 求入度出度方便，入度为弧头的数量，出度为弧尾的数量
- 程序中构建链表对于每个新初始化的结点采用头插法进行插入
邻接多重表(链式存储)
邻接多重表可以看做是邻接表和十字链表的结合体
使用邻接表解决在无向图中删除某两个结点之间的边的操作时，由于表示边的结点分别处在两个顶点为头结点的链表中，所以需要都找到并删除，操作比较麻烦。处理类似这种操作，使用邻接多重表会更合适。
- 表结点构成：
mark 为标志域，作用是标记某结点是否已经被操作过，例如在遍历各结点时， mark 域为 0 表示还未遍历；mark 域为 1 表示该结点遍历过； ivex 和 jvex 分别表示该结点表示的边两端的顶点在数组中的位置下标； ilink 指向下一条与 ivex 相关的边； jlink 指向下一条与 jvex 相关的边； info 指向与该边相关的信息。
- 顶点结点构成：
data 为该顶点的数据域； firstedge 为指向第一条跟该顶点有关系的边。
总结
- 邻接表适用于所有的图结构，无论是有向图（网）还是无向图（网），存储结构较为简单，但是在存储一些问题时，例如计算某顶点的度，需要通过遍历的方式自己求得
- 十字链表适用于有向图（网）的存储，使用该方式存储的有向图，可以很容易计算出顶点的出度和入度，只需要知道对应链表中的结点个数即可
- 邻接多重表适用于无向图（网）的存储，该方式避免了使用邻接表存储无向图时出现的存储空间浪费的现象，同时相比邻接表存储无向图，更方便了某些边操作（遍历、删除等）的实现