考研笔记-计算机之数据结构:网状结构-图(基础知识)
- 2026-11-10 08:33:14
——如阅读体验不佳，可转为横屏阅读；如微信无法横屏，可尝试文末方法。
图的定义
抽象数据类型图：
1）数据对象V：V为具有相同特性的数据元素的集合，称为顶点集。
2）数据关系R：R={VR}，VR={
|
且
，
表示从v到w的弧，谓词
定义了弧
的意义或信息}（集合{VR}中的各个元素VR是由与其对应的各个不同的谓词P定义的弧的集合）。
3）基本操作P：关键操作为遍历（即每个结点均被“访问”一次，且仅被“访问”一次，访问不仅仅是到达，而是在到达的基础上有其他操作，如插入新结点）。
弧头：弧的终点。
弧尾：弧的始点。
无向图顶点的度：某顶点的度等于依附于该顶点的边的数目。
有向图顶点的度：某顶点的度等于该顶点的入度加该顶点的出度，即TD(v)=ID(v)+OD(v)。
（具有n个顶点，e条边或弧的图，满足如下关系：
，即图的每条边或弧贡献2度——入度和出度；树中每个分支贡献1度——出度，树结点的度为出度，因为除根结点外的任意结点的入度均固定为1）。
子图：设有两个图G=(V,{E})和G’=(V’,{E’})，若
且
，则称G’为G的子图。
完全图：有n(n-1)/2条边的无向图称为完全图。（即任意两个顶点之间均有边。）
有向完全图：有n(n-1)条弧的有向图称为有向完全图。（即任意两个顶点之间均有双向的弧。）
连通图：无向图中任意两个顶点均连通。
强连通图：有向图中任意两个顶点均强连通（双向连通）。
连通分量：指无向图中的极大连通子图。
强连通分量：指有向图中的极大强连通子图。
连通图的生成树：指连通图的极小连通子图。（只有连通图才有生成树）
无向图的生成森林：无向图的各个连通分量的生成树的集合。
有向树：恰有一个顶点的入度为0，其余顶点的入度均为1的有向图。
有向图的生成森林：含有有向图中的全部顶点，但只有足以构成若干棵不相交的有向树的弧。（强连通图必有生成树，非强连通图也可能有生成树）
权：与图的边或弧相关的数称为权。
网：带权的图称为网。
二部图：若能将无向图G=<V,E>的顶点集V划分成两个子集V1和V2（V1∩V2=∅），使得G中任意一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图。（二部图的存储矩阵必为分块对称。）
顶点是图的数据（逻辑）结构中的术语；结点是图的存储（物理）结构中的术语。
图的存储结构
图中顶点和顶点间的关系是分开存储的，不像表和树中结点间的关系通过结点之间的相对位置隐含表示（多对多的关系无法通过结点之间的相对位置表示）。
图中的顶点的存储均是采用顺序存储，关系的存储均是链式存储，共有4种关系存储结构：
（1）邻接矩阵
用于无向图、有向图。（无向图的邻接矩阵为对称矩阵，可压缩存储。对有向无环图的顶点适当地编号，可使其邻接矩阵为上（或下）三角形且主对角线为全0。）
顶点用顶点结点的一维数组表示。
边/弧用邻接矩阵表示（对于有向图，行号对应弧尾，列号对应弧头）。（可以将存储关系的邻接矩阵看作数据元素的“指针”，每个数据元素有n个“指针域”。）
顶点：Vexs[MAX_VERTEX_NUM]
边/弧：Arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]
（2）邻接表
用于无向图、有向图。（对于无向图来说，每条逻辑边同时存在于两个链表中。有向图有邻接表和逆邻接表两种，且两种表中的结点总数相等）
每个顶点用一个头结点表示。
每条边/弧用两个结点（头结点+表结点）表示。
头结点：
表结点：
（3）十字链表
用于有向图。（十字链表可看作是将有向图的邻接表和逆邻接表结合起来得到的表。）
每个顶点用一个顶点结点表示。
每条弧用一个弧结点表示，弧结点中表示弧头和弧尾的序号域不等同（即只有弧头序号域和弧尾序号域分别相同的两个弧结点才表示同一弧结点）。
顶点结点：
（FirstIn所引导的链表中的各弧结点具有相同的弧头HeadVex，且HeadVex即为FirstIn所在的顶点结点在顶点结点顺序表中的位置索引号；FirstOut所引导的链表中的各弧结点具有相同的弧尾TailVex，且TailVex即为FirstOut所在的顶点结点在顶点结点顺序表中的位置索引号。（十字链表中“十”字也可理解为，由于每个顶点结点连接两个链表——弧头链表和弧尾链表，即以该顶点结点为弧头和弧尾的链表，故两个链表在该顶点结点处实现交接，从而形成“十”字。））
弧结点：
（具有相同弧尾TailVex的各弧结点由TailLink域链接成一个线性表，具有相同弧头HeadVex的各弧结点由HeadLink域链接成一个线性表。每个弧结点既是某个弧头链表中的一个结点，又是某个弧尾链表中的一个结点，整个有向图构成了一个十字交叉的链表，故称这样的存储结构为十字链表）
（4）邻接多重表
用于无向图。
每个顶点用一个顶点结点表示。
每条边用一个边结点表示，边结点中表示边依附的两顶点的序号域等同（即两个边结点只要其两个顶点序号域的集合相同，则这两个边结点即为同一边结点，与顺序无关）。
顶点结点：
（FirstEdge所引导的链表中的各边结点具有相同的顶点IVex或JVex，且IVex或JVex即为FirstEdge所在的顶点结点在顶点结点顺序表中的位置索引号）
边结点：
（Mark为标志域，可用于标记该边是否被搜索过。依附于同一顶点（即边依附的两顶点的集合{IVex,JVex}的交集非空）的各个边结点由ILink域或JLink域链接成一个线性表，每个边结点同时在两个链表中。）
图的性质
(1) 设A为无向图的邻接矩阵，则Am中的元素aij不等于0表示无向图中顶点Vi和Vj之间存在长度为m的路径；
