第六章 图

6.1 图的基本概念

图是一种非线性结构

图的特点：

• 顶点之间的关系是任意的
• 图中任意两个顶点之间都可能相关
• 顶点的前驱和后继个数无限制

1. 定义：图是一种数据元素间存在多对多关系的数据结构加上一组基本操作构成的抽象数据类型。

• 定义：图G由顶点集V和边集E组成，记为G=(V,E),其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系(边)集合。若V={V1,V2,……Vn}，则用|V|表示图G中顶点的个数，也称图G的阶，E={(u,v)|u∈V,v∈V}，用|E|表示图G中边的条数。
• 注意：线性表可以是空表，树可以是空树，但图不可以为空，即V一定是非空集。
• 弧头和弧尾
  <x,y>表示从顶点到顶点y的一条弧，并称x为弧尾或起始点，称y为弧头或终端点

2. 无向图，有向图：有向图<u,v>，其中u表示弧尾，v表示弧头。
3. 简单图：简单图：①不存在重复边，② 不存在顶点到自身的边。
4. 多重图：图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图。
5. 度，入度，出度：① 无向图：在具有n个顶点，e条边的无向图中，全部顶点的度的和等于边数的2倍（一条边连两个顶点，所以一条边两个度）。②有向图：度之和入度＋出度（一条边一个出度一个入度），在具有n个顶点，e条边的有向图中，入度=出度=e。
6. 路径，简单路径，路径长度：① 在路径序列中，顶点不重复出现的路径称为简单路径。②路径长度：路径上边的数目（简单就意味着顶点不重复）。
7. 回路，简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
8. 点到点到距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为u到v的距离。若u到v根本不存在路径，则记该距离为无穷（∞）。
9. 连通图，强连通图：①若图G中任意两个顶点都是连通的，则称图G为连通图（无向图中的连通就是两个顶点之间路径存在；有向图中的强连通是两个顶点之间存在往返的路径，就是w到v和v到w都有路径，强连通是有向图独有的概念），否则称为非连通图。对于n个顶点的无向图G，若G是连通图，则至少有n-1条边（就是把每个顶点都连线一个顶点，就存在路径了），若G是非连通图，则最多可能有$C_{n-1}^2$,（就是除去一个顶点，其他顶点两两相连，只要不连接最后一个顶点，这个图就是不连通的最极端情况）。②若图中任何一项顶点都是强连通的，则称为图为强连通图。对于n个顶点的有向图G，若G是强连通图，则最少为n条边（形成回路）。
10. 连通的补充图解：

• 连通的最少边数：
  
• 不连通的最多边数：
  
• 强连通的最少边数
  

11. 子图（不用包含所有顶点）、生成子图：若包含所有顶点的子图，就称为生成子图。并不是任意几个点，任意几条边都能构成子图（例如不构成图的情况）。
    

12. 连通分量：无向图中极大连通子图(子图必须连通，且包含尽可能多的顶点和边）称为连通分量。
    

13. 强连通分量：有向图中有极大强连通子图（子图必须强连通，同时保留尽可能多的边）称为有向图的强连通分量。
    

14. 生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图（边尽可能的小，但要保持连通）若图中顶点数是n，则它的生成树含有n-1条边，对于生成树而言，若砍去一条边，则会变成非连通图，若加上一条边则会形成一个回路（环）。

15. 生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林。
    

16. 边的权，带权图（网）
    

17. 无向完全图：无向图中任意两个顶点之间都存在边。

18. 有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧。
    

19. 稀疏图，稠密图：这二者是相对的
    

20. 树：不存在回路，且连通的无向图，n个顶点的树，必有n-1条边。

21. 有向树：一个顶点的入度为0，其余顶点的入度均有1的有向图，称为有向树。
    n个顶点的图，若|E|>n-1,则一定有回路。
    

知识回顾

6.2 图的储存结构（邻接矩阵法）

1. 数组表示法

(1) 有向图，无向图的邻接矩阵

① 对于无向图，顶点vi的度是邻接矩阵中第i行（或第i列）的元素之和， TD（vi）= ∑ a[i][j]。
② 对于有向图，顶点VI的出度OD（vi）是邻接矩阵中第i行的元素之和，顶点vi的出度ID（vi）是邻接矩阵中第j列）的元素之和。
③ 邻接矩阵法求顶点的度。入度。出度的时间复杂度为O(|V|)。

2. 定义邻接矩阵的结构

#define INFINITY INT_MAX
#define MAX_VERTEXT_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind;
typedef struct ArcCell{VRType adj;//对无向图，用0,1表示是否相邻，对于带权图，为权值InfoType *info;//该弧相关信息的指针}RrcCell,AdjMatrix[MAX_VERTEXT_NUM][MAX_VERTEXT_NUM];//邻接矩阵

3. 定义图的结构

（1）代码：

//定义图的结构
typedef struct {VertextType exs[MAX_VERTEXT_NUM]; //顶点AdjMatrix arcs[MAX_VERTEXT_NUM][MAX_VERTEXT_NUM]; //边的邻接矩阵int vexnum,arcnum; //个数GraphKind kind;//有向图？无向图？
}MGraph;

4. 构造图G

status CreateGraph(MGraph &G)
{scanf(&G.kind){case DG:return CreateDG(G);case DN:return CreateDN(G);case UDG:return CreateUDG(G);case UDN:return CreateDGN(G);default:return ERROR;}
}
//用无向图为例status CreateUDN(MGraph &G)
{scanf(&G.arcnum,&G.vexnum,&IncInfo);//输入点数和边数//给顶点进行数字化编号for(i=0;i<G.vexnum;i++){ scanf(&G.exs[i]);//定义顶点数组（如果顶点本身就是1~n的数字无需这一步）}//初始化邻接矩阵for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){G.arcs[i][j]={ININITY,NULL};}}//通过边数进行遍历for(k=0;k<G.arcnum;K++){scanf(&V1,&V2,&W);//输入邻接的连个顶点i=locatteVex(G,V1);j=locateVex(G,V2);//查找V1,V2的位置G.arcs[i][j].adj=w;//给邻接矩阵赋值if(IncInfo){INPUT(*G.arcs[i][j].info);}G.arcs[j][i]=G.arcs[i][j];//由于是无向图，对称}return ok;
}

5. 特点

优点：

• 无向图邻接矩阵是对称矩阵，同一条边表示了两次
• 顶点v的度：等于二维数组对应行(或列)中1的个数
• 判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1
• 在图中增加、删除边：只需对二维数组对应分量赋值1或清0
• 占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图
• 对有向图的数组表示法可做类似的讨论’‘

缺点：

• 不便于删除和增加顶点（增删边简单）
• 不便于统计边的数目，需要扫描邻接矩阵所有元素才能统计完毕，时间复杂度为O($n^2$ )
• 空间复杂度高，对于有向图，n个顶点需要$n^2$ 个单元存储边，对于无向图，n(n-1)/2个单元，空间复杂度为O($n^2$ )