本文共 3448 字，大约阅读时间需要 11 分钟。

一、图的基本概念

• 这部分的理论，若想深入学习，请前往学习《离散数学》。

1、图的定义

• 图（ Graph)G由两个集合和E组成，记为G=(V,E)，其中是V顶点的有穷非空集合，E是中顶点偶对的有穷集合，这些顶点偶对称为边。V(G)和E(G）通常分别表示图G的顶点集合和边集合，E(G)可以为空集。若E(G)为空，则图G只有顶点而没有边。
• |V| 表示图顶点数，也称为图的阶；|E|表示图的边数。|V|>=1，|E|>=0，即图可以只有一个点，也可以一条边也没有，就是不能一个点也没有，这与之前的线性表和树完全不一样的。

2、图的有向与无向

• 若构成一个图的边集为有向边，那么这个图就称为有向图；与此相反的，若构成图的边集是无向边，则图就是无向图。

3、几种重要的图类：

• 1）简单图：一个图若不存在自环和平行边，则称为简单图。
• 2）多重图：若图中某两个节点之间存在多对平行边，且顶点存在自环边，则称该图为多重图。
• 3）完全图：图中任意两顶点之间存在边，则称为完全图。
• 4）子图：有图G，A 两个，若 A 的边集是 G 的边集的子集，A 的点集是 G 的点集的子集，则称 A 是 G 的子图。特别的，当 A 的顶点集与 G 的顶点集相等，则称 A 为 G 的生成子图。
• 5）稀疏图：图中边数很少的图，与此相反的称为稠密图。

4、图的连通性

• 无向图中，点 v 和 w 之间若存在路径，则称这两点是连通的。
• 无向图 G 中任意两点之间都是连通的，则称图是连通，否则就是非连通图。
• 无向图中的极大连通子图称为图的连通分量。
• 若图中两顶点存在双向路径，则称这两个点是强连通的；若图中任意两点之间都是强连通的，则称该图是强连通图。

5、图与树、森林的关系

• 连通图可以转为树，非连通图可以转化为森林。
• 连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有nー1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。

6、图的度

• 对于无向图中任意一点，与其相连接的边的总数称为该点的度。
• 对于有向图中任意一点，从自身发出的边的数目称为点的出度，与自身为终点的边的数目称为点的入度，入度和出度的和称为点的度。

7、其他

• 在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。
• 顶点v_p到顶点v_q之间的一条路径是指顶点序列v_p,v_i1,…v_im,v_q，当然关联的边也可以理解为路径的构成要素。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有n个顶点，并且有大于n-1条边，则此图一定有环。
• 在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
• 从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到ν的距离。若从u到v根本不存在路径，则记该距离为无穷（∞)

二、图的存储结构

• 图的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表四种结构，其中邻接矩阵是顺序存储结构，十字链表和邻接多重表是链式存储结构，邻接表是顺序存储结构和链式结构的结合。

1、邻接矩阵

1.1、基本概念

• 所谓邻接矩阵，是指用一个一维数组存储图的顶点信息，用一个二维数组存储点与点之间的邻接关系即边的信息。
• 对于无权图，n 阶图G(V, E) 与 n 维矩阵之间有如下关系：
  
• 对于带权图，则是如下关系：
  
• 示例如下：
  
  

1.2、特点

• 图的邻接矩阵有如下特点：
  ① 无向图的邻接矩阵一定是一个对称矩阵且唯一，故而实际存储中只需存储上三角的元素。
  ② 对于无向图，邻接矩阵中第 i 行的非零元素的个数正好是第 i 个顶点的度。
  ③ 对于有向图，行的非零元素个数对于点的出度，列的非零元素个数对应点的入度。
  ④ 要确定图中有多少条边，必须按行、按列对每个元素进行检测，时间代价大。
  ⑤ 邻接矩阵适合存储稠密图。

1.3、抽象数据类型

• 邻接矩阵的存储结构定义如下：

  #define Maxsize 50typedef struct Graph{
       	int vex[Maxsize]; // 顶点集	int edge[Maxsize][Maxsize]; //边集	int vexnum, arcnum; //顶点数目和边数};

2、邻接表

2.1、基本概念

• 为了改进邻接矩阵对稀疏图的存储缺陷，出现了邻接表。
• 所谓邻接表，是指对图中每个顶点建立一个单链表，链表节点由数据域和指针域构成。第 i 个单链表的节点表示依附于顶点 V_i 的边，这个单链表就叫 V_i 的边表，这是针对无向图而言，对于有向图则分别是表示以 V_i为尾的弧，单链表则称为出边表。
• 边表的头指针和顶点的数据信息采用顺序存储，称为顶点表（表头结点表），因此邻接表中存在顶点表节点和边表节点两种节点。
  
• 顶点表结点由顶点域（data）和指向第一条邻接边的指针（ firstarc）构成，边表（邻接表）结点由邻接点域（ adjvex）和指向下一条邻接边的指针域（ nextarc）构成。
  
  

2.2、特点

• 邻接表有如下特点
  ① 若G为无向图，则所需的存储空间为O（|V|+2|E|)；若G为有向图，则所需的存储空间为O（|V|+|E|)。前者的倍数2是由于无向图中，每条边在邻接表中出现了两次.
  ② 对于稀疏图，采用邻接表表示将极大地节省存储空间。
  ③ 在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为O(n)。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。
  ④ 在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然，这实际上与邻接表存储方式是类似的。
  ⑤ 图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

2.3、抽象数据类型

• 邻接表的抽象数据类型如下：

#define Maxsize 50typedef struct Arcnode{
   	int adjvex; //该弧所指向的顶点的位置	Arcnode* next;};typedef struct Vnode{
   	int data;  //顶点信息	Arcnode* first; // 指向第一条依附于该顶点的弧的指针}AdjList[Maxsize];typedef struct Graph{
   	AdjList vertices; //邻接表	int vexnum, arcnum;};

3、十字链表

• 十字链表是在邻接表的基础上发展形成的，与邻接表不同的是，十字链表只采用链式存储，并且针对有向图设计的。
• 弧结点中有5个域：尾域（ tailvex）和头域（ headvex）分别指示弧尾和弧头这两个顶点在图中的位置；链域 hlink指向弧头相同的下一条弧；链域tlink指向弧尾相同的下一条弧info域指向该弧的相关信息。这样，弧头相同的弧就在同一个链表上，弧尾相同的弧也在同个链表上。
• 顶点结点中有3个域：data域存放顶点相关的数据信息，如顶点名称； firstin和 firstout两个域分别指向以该顶点为弧头或弧尾的第一个弧结点。
• 在十字链表中，既容易找到V_i为尾的弧，又容易找到V_i为头的弧，因而容易求得顶点的出度和入度。图的十字链表表示是不唯一的，但一个十字链表表示确定一个图。
  
  

4、邻接多重表

• 这是针对无向图设计的采用纯链式存储结构的。
• 邻接多重表的边节点结构如下：
  
  ① mark：标志域，用于标记该边是否被搜索过；
  ② ivex/jvex：为依附某条边的两个顶点；
  ③llink：指向下一条依附于顶点ivex的边；
  ④jlink：指向下一条依附于顶点jvex的边；
  ⑤ info：指向和边相关的各种信息的指针域；
• 顶点节点的数据结构如下：
  
• data 存储该顶点的相关信息，firstedge 指向第一条依附该顶点的边。
  

转载地址：http://rqqgn.baihongyu.com/