文章目录邻接表法顺序链式存储度的求法对比邻接矩阵 VS 邻接表数组实现的顺序存储邻接矩阵法空间复杂度高O(n2),不适合存储稀疏图适合存储稠密图。邻接表法顺序链式存储邻接表是一种“顺序存储 链式存储” 的混合体顶点表顺序/数组用一个一维数组存储所有顶点每个顶点带一个 “指向第一条边的指针”。边弧表链式/链表每个顶点后面挂一个单链表链表中每个结点存储邻接点的下标或指针和 指向下一条边的指针。#defineMaxVertexNum100// 最大顶点数// 1. 边(弧)表结点链表中存的是什么存的是【邻接点的位置】typedefstructArcNode{intadjvex;// 该弧所指向的顶点的位置数组下标structArcNode*next;// 指向下一条弧的指针// 若带权图这里加一个 int weight;}ArcNode;// 2. 顶点表结点数组中的元素是什么typedefstructVNode{VertexType data;// 顶点信息如 A, BArcNode*first;// 指向第一条依附于该顶点的弧的指针}VNode,AdjList[MaxVertexNum];// AdjList 是顶点数组类型// 3. 图结构包含顶点数组和顶点/边计数typedefstruct{AdjList vertices;// 顶点数组里面存了 VNode 和 指针intvexnum,arcnum;// 图的当前顶点数和边数弧数}ALGraph;无向图边结点的数量是2|E|整体空间复杂度为O( |V|2|E| )有向图边结点的数量是|E|整体空间复杂度为O( |V||E| )度的求法无向图顶点的度遍历该顶点相关的边链表有多少个边结点就有几度边数所有顶点度数和÷ 2因为每条边被存了两次。有向图顶点的出度OD遍历该顶点相关的边链表反映从当前结点出去的弧。顶点的入度(ID)指向当前顶点的弧计算麻烦需要全部遍历。弧数所有顶点出度之和即所有边表结点总数。对比邻接矩阵 VS 邻接表对比邻接矩阵邻接表空间复杂度O ( ∣ V ∣ 2 ) O(\vert V \vert^2)O(∣V∣2)有向图O ( ∣ V ∣ ∣ E ∣ ) O(\vert V \vert\vert E \vert)O(∣V∣∣E∣)无向图O ( ∣ V ∣ 2 ∣ E ∣ ) O(\vert V \vert2\vert E \vert)O(∣V∣2∣E∣)适用场景稠密图边多空间利用率高稀疏图边少节省空间有向图求入度O ( ∣ V ∣ ) O(\vert V \vert)O(∣V∣)扫描对应一列O ( ∣ V ∣ ∣ E ∣ ) O(\vert V \vert\vert E \vert)O(∣V∣∣E∣)需要遍历全部边为主要缺陷存储唯一性唯一顶点编号顺序确定矩阵就确定不唯一链表结点插入顺序不固定计算度 /出度 /入度必须遍历对应行或列计算有向图的度、入度不方便其余很方便找相邻的边必须遍历对应行或列找有向图的入边不方便其余很方便