一. 图的基本概念
1. 完全图
由n个顶点组成的无向图，如果有n * (n – 1) / 2 条边，也就是每个顶点都与其余的（n – 1）个顶点相邻，则称之为无向完全图
由n个顶点组成的无向图，如果有n * (n – 1) 条边，也就是每个顶点都与其余的（n – 1）个顶点相邻，则称之为有项完全图
2. 权
在某些图中，边具有与之相关的数值，称为权重，带权图又叫网络（network）
3. 邻接顶点
若两个顶点之间有一条边连接，则称这两个顶点相邻，为邻接顶点
4. 子图
设有两个图G＝(V, E) 和G’＝(V’, E’)。若V ‘被 V包含，且E’被E包含, 则称图G’是图G的子图。
5. 度
无向图中，称顶点v作为边的端点的次数为v的度数，简称度
有向图中，入度 + 出度 = 度数，入度就是顶点v作为边的终点的次数，出度就是顶点v作为边的始点的次数
6. 路径
在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, …, vpm，到达顶点vj。则称顶点序列 (vi vp1 vp2 … vpm vj) 为从顶点vi 到顶点 vj 的路径
7. 简单路径
若路径上各顶点v1，v2……vm均不重复，则称这样的路径为简单路径
8. 回路
若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。
9. 连通图
在无向图中，任意两个顶点之间都是连通的，称此图为连通图
10. 连通分量
非连通图的极大连通子图叫做连通分量
11. 强连通图
在有向图中，每对顶点之间都存在互相可达的路径，称为为强连通图
12. 强连通分量
非强连通图的极大强连通子图叫做强连通分量
13. 生成树
一个无向连通图的生成树是它的极小连通子图，若图中有n个顶点，则其生成树由n – 1条边构成
二. 图的存储结构
图的存储结构有多种，这里我们分别介绍用邻接矩阵表示和用邻接表表示
三. 邻接矩阵表示
1. 将所有的顶点的信息组织成一个顶点表，然后利用一个矩阵来表示各顶点之间的邻接关系，称为邻接矩阵
2. 无向图的邻接矩阵是对称的，第i行或者列的元素之和，就是顶点i的度数
3. 有向图的邻接矩阵不一定对称，第i行的元素之和，就是顶点的出度，第i列的元素之和，就是顶点的入度
4. 邻接矩阵的构建方法：
5. 无向图的邻接矩阵
我们分别将下图的四个顶点标号为0,1,2,3，对应矩阵的四行四列，可以看出，从0到1有一条边，因为是无向图，所以从1到0的边数也是1，则在矩阵中将（0,1）和（1,0）这两个元素分别等于1，（注意这里的矩阵行和列都是从0开始）剩下的顶点依次类推，另外我们可以看出，这四个顶点到自身的边数都是0，所以对角线的元素全部为0
6. 有向图的邻接矩阵
我们分别将下图的四个顶点标号为0,1,2，对应矩阵的三行三列，
在下图中，0到1有一条边，则（0,1） = 1（注意这里的矩阵行和列都是从0开始），1到0也有一条边，则（1,0） = 1，1到2有一条边，则（1,2） = 1，但是2到1是没有边，因为有向图是有方向的，所以（2,1） = 0，这里和无向图要注意区分
7. 对于网络（就是带权图）的邻接矩阵的定义如下：
我们分别将下图的四个顶点，标号为0,1,2,3，对应矩阵的四行四列
则顶点2到顶点3的权重为8，则（2,3） = 8（注意这里的矩阵行和列都是从0开始）
顶点3到顶点2的权重为6，则（3,2） = 6
每个顶点到自身的权重为0，所以矩阵对角线元素都为0
而顶点0到顶点2没有权重，则（0,2） = 无穷
剩下的以此类推
四. 邻接表
1. 在邻接表中，从一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边（边结点），结点中有另一顶点的下标 dest 和指针 link，对于带权图，边结点中还要保存该边的权值cost。如果想知道顶点i的度，只需统计顶点i的边链表中边结点的数目
2. 无向图
下图中可以看出，A到B的这条边在邻接表中出现了两次，因为这是无向图，AB和BA都是同一条边
2. 有向图
有向图需要构建两个邻接表，分别表示出度和入度
在出度表中，顶点i对应的链表所含结点的个数，就是该顶点的出度
在入度表中，顶点i对应的链表所含结点的个数，就是该顶点的入度
有向图的每条边在邻接表中只出现一次
3. 网络
对于带权图，需要在邻接表的边结点中增加一个cost域，用于存放各边的权值
五. 参考资料
《数据结构》殷人昆版
请登录之后再进行评论