2025年单向链表结构图（单向链表数据结构）

大家好，我是讯享网，很高兴认识大家。

^{计算机考研择校咨询}

^{请添加清华姚哥微信}

讯享网

基本定义

图(Graph)：由两个集合V(G)和E(G)组成,记为G=(V,E)

其中：

V(G)是顶点的非空有限集；

E(G)是边的有限集合，边是顶点的有序对或无序对，E（G）可以是空集，如果为空则图没有边。

有向图(Digraph)：由两个集合V(G)和E(G)组成

 其中：

V(G)是顶点的非空有限集；

E(G)是有向边（即弧）的有限集合，弧是顶点的有序对，记<v,w>，v为弧尾(Tail)，w为弧头（head）。

无向图(Undigraph)：由两个集合V(G)和E(G)组成

 其中：

V(G)是顶点的非空有限集；

E(G)是边的有限集合，边是顶点的无序对，记（v,w）或（w,v)，并且（v,w)=(w,v)。

相关术语

有向完全图：n个顶点的有向图最大边数是n(n-1)；

无向完全图：n个顶点的无向图最大边数是n(n-1)/2；

权：每条边都可以标上具有某种含义的数值该数值称为该边的权值；

网：边上带有权值的图；

子图：设有两个图G = （V,E）和G’ = (V’,E’)，若V’是V的子集，且E’是E的子集，则称G’是G的子图。若有满足V(G’)=V(G)的子图G’,则称其为G的生成子图。(注意：并非V和E的任何子集都能构成G的子图，这样的子集首先要满足图的定义)；

邻接点：顶点v和顶点w之间存在一条边，则称v和w互为邻接点；边(v,w)和顶点v和w相关联；

顶点的度：无向图中，顶点的度为与每个顶点相连的边数；有向图中，顶点的度分成入度与出度；入度：以该顶点为头的弧的数目；出度：以该顶点为尾的弧的数目；

路径——若从顶点vi经过若干条边能到达vj，称顶点vi和vj是连通的，又称顶点vi到vj有路径。

路径长度——沿路径边的数目或沿路径各边权值之和。

回路——第一个顶点和最后一个顶点相同的路径。

简单路径——序列中顶点不重复出现的路径。

简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。

连通——从顶点V到顶点W有一条路径，则说V和W是连通的。

连通图——图中任意两个顶点都是连通的图。

连通分量——非连通图的每一个连通部分。

强连通图——有向图中，如果对每一对Vi,Vj，从Vi到Vj 和从Vj到 Vi都存在路径，则称G是强连通图。

邻接矩阵法

定义：图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组来存储图中顶点的信息，一个二维数组（称为邻接矩阵）用来存储图中的边或弧的信息。我们先来看无向图的邻接矩阵存储方式。

有向图和无向图的邻接矩阵法

无向图的邻接矩阵存储方式

设图有 n 个顶点，则邻接矩阵就是一个𝑛 × 𝑛的矩阵。

有向图的邻接矩阵

注意：

在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点信息等均可省略）；

无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储。

图的邻接矩阵存储有以下特点：

无向图的邻接矩阵一定是对称矩阵（并且唯一）。因此，在实际存储邻接矩阵时只需存储上（或下）三角矩阵的元素；

对于无向图，邻接矩阵的第i行(或第i列)非零元素(或非无穷元素)的个数正好是顶点 i 的度；

对于有向图,邻接矩阵的第i行非零元素(或非无穷元素)的个数正好是顶点 i 的出度；第i列非零元素(或非无穷元素)的个数正好是顶点的入度；

用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大；

稠密图适合使用邻接矩阵的存储表示；

设图G的邻接矩阵为A，A^n的元素A^n[i][j]等于由顶点 i 到顶点 j 的长度为 n 的路径的数。

邻接矩阵表示法的优缺点：

优点：

便于判断两个顶点之间是否有边；

便于计算各个顶点的度。

缺点：

不便于增加和删除顶点；

不便于统计边的数目，需要扫描邻接矩阵所有元素才能统计完毕，时间复杂度为0(n^2)；

空间复杂度高；

对于稀疏图而言尤其浪费空间。

邻接表法

邻接表(Adjacency List)是图的一种链式存储结构。对图中每个顶点v,建立一个单链表，把与v相邻接的顶点放在这个链表中。邻接表中每个单链表的第一个结点存放有关顶点的信息，把这一结点看成链表的表头，其余结点存放有关边的信息。

无向图

有向图

邻接表法存储结构

// 弧结点typedef struct Arcnode { int adjvex;  struct Arcnode *nextarc; } ArcNode; //顶点节点typedef struct Vnode{ VertexType data;  ArcNode *firstarc;  } VNode, AdjList[Max_Vertex_Num];  //图的定义typedef struct { AdjList vertices;  int vexnum, arcnum; //顶点及弧的数目 } ALGraph;

讯享网

注意：

若G为无向图，则所需的存储空间为O(V+2E)；若G为有向图，则所需的存储空间为 O(V+E)；

对于稀疏图，采用邻接表表示将极大地节省存储空间；

在邻接表中，给定一顶点，能很容易地找出它的所有邻边，但是，若要确定给定的两个顶点间是否存在边，在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低；

在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表；

图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

优缺点

优点：

便于增加和删除顶点。  

便于统计边的数目。

空间效率高。

缺点：

不便于判断顶点之间是否有边。

不便于计算有向图各个顶点的度。

广度优先（BFS）——类似于树的层次遍历

方法：

从图的某一顶点V0出发，访问该顶点后，依次访问V0的所有未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到。

广度优先搜索遍历的过程如下：

1、从图中某个顶点V出发，访问V。

2、依次访问v的各个未曾访问过的邻接点。

3、分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于 “后被访问的顶点的邻接点”被访问。重复步骤3,直至图中所有已被访问的顶点的邻接点都被访问到。

广度优先生成树由广度优先遍历过程确定、由于邻接表的表示方式不唯一，因此基于邻接表的广度生成树也不唯一。

代码实现：

讯享网void BFS( ALGraph G, int v){ int Q[MAX],f=0,r=0,x;  ArcNode *w; printf(”%d\t”,v); visited[v]=1; Q[r++]=v;  while(f&lt;r) { x=Q[f++]; w=G.vertices[x].firstarc;  while(w)  { x=w-&gt;adjvex;  if(visited[x]==0) { visited[x]=1; printf(”%d\t”,x);  Q[r++]=x; } w=w-&gt;nextarc;  } }}

深度优先（DFS）——类似于树的先根遍历

对于一个连通图，深度优先搜索遍历的过程如下：

1、从图中某个顶点V出发，访问V。

2、找出刚访问过的顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至刚访问过的顶点没有未被访问的邻接点为止。

3、返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。

4、重复步骤(2)和(3),直至图中所有顶点都被访问过，搜索结束。

代码实现：

void DFS(ALGraph G, int v) { ArcNode *w; int i; printf(”%d\t”,v); visited[v]=1; w=G.vertices[v].firstarc;  while(w)  { i=w-&gt;adjvex;  if(visited[i]==0) DFS(G,i); else w=w-&gt;nextarc; } }