图的基本概念及术语汇总

第 7章 图
第7 章
7．2 图的存储结构
7．3 图的遍历 7．4 图的应用
图
7．1 图的基本概念及术语
7．5 应用举例及分析 习题
上一页 下一页 返 回
7．1 图的基本概念及术语
一、基本概念：
图：图G（Graph）由两个集合构成，记作G=（V，E），V 是顶点的有穷非空集合；E是用顶点对表示的边（Edge）的 有穷集合。 顶点：图中的数据元素通常称为顶点（vertex）。 无向图：若G中表示边的顶点对是无序的，则称为无向图。
上一页
下一页
返 回
7、 权、网
在一个图的每条边或弧上，标上具有某
种含义的数值，这种与图的边相关的数值称 为权（weight），这种边或弧上带权的图称 为网（network）。
上一页
下一页
返 回
7 ．2
图的存储结构
7.2.1 邻接矩阵表示法：
1、定义：设G=（V，E）是N个顶点的图（顶
点序号依次为0，1，2，3，……n-1）。G的
G1.arc=
G2.arc=
上一页
下一页
返 回
3、邻接矩阵表示法的性质：
对于无向图：
1．邻接矩阵一定是对称的 2．第i行（或第i列）非0元素个数正好是第i个顶点的度TD （Vi）
对于有向图：
1．邻接矩阵不一定对称 2．第i行非0元素的个数是顶点i的出度OD（Vi），第i列非 0元素的个数是顶点i的入度ID（Vi） 3. 结构说明如下
上一页 下一页 返 回
5、 路径，回路 无向图G=（V，E）中，路径是从顶点V到 顶点V′间的一个顶点序列（V=Vi0，Vi1，Vi2， Vi3，……，Vim=V′），其中，（Vij-1，Vij） ∈E（1≤j≤m）。 若是有向图，路径也是有向的。 路径的起点和终点相同（即V=V），则称此 路径为回路或环（cycle） 简单路径：序列中顶点不重复出现的路径。 ★ 路径上边或弧的数目称为路径长度
上一页 下一页 返 回
#define VEXTYPE int #define ADJTYPE int #define MAXLEN 40 type struct {LOXTYPE vex[MAXLEN] ; //顶点信息 ADJTYPE arc[MAXLEN][MAXLEN] //邻接矩阵相 邻关系 int vexnum , arcnum ; //顶点数，边数 int kind ; } MGRAPH [matrix]
表头结点组成一个二维数组。
上一页 下一页 返 回
表结点的结构为： Adjvex Next
★其中，Adjvex域存放与顶点Vi相邻接的顶点在二 维数组中的序号， Next域为指针，指向与顶点Vi相 邻接的下一个顶点的表结点。
上一页
下一页
返 回
无向图G2的邻接链表示意图如下：
上一页 下一页 返 回
V1
V1
V2
V4
V2
V4
V3
V3
G1 有向图和无向图
G2
n个顶点的有向图中，边e的取值范围为0～n(n-1)条，
n个顶点的无向图中，边e的取值范围为0～n(n-1)/2条
上一页 下一页 返 回
二．图的基本术语： 1、邻接点，相关边
对于无向图G=（V，E），若边（Vi，Vj）∈E，则称Vi 和Vj互为邻接点（Adjacetnt），而边（Vi，Vj）则是与顶点 Vi和Vj相关联的边。 对于有向图G=（V，E），若弧<Vi，Vj>∈A，则称顶 点Vi邻接到顶点Vj，顶点Vj邻接自顶点Vi，而弧<Vi，Vj>和 顶点Vi，Vj相关联。 例如在上页的图中：G1中V3邻接到V1，V1邻接自V3。与V3相 关联的弧有：<V2，V3>、<V3，V1>、<V3，V4>。G2中，与V2 相关联的边有：<V1，V2> <V2，V3>。邻接ຫໍສະໝຸດ 阵是表示图中顶点之间相邻关系的n阶
方阵。适用于有向图和无向图。
上一页
下一页
返 回
2、n阶方阵A具有如下性质：
1 若（Vi，Vj）或（Vi，Vj）∈E
列出图示的邻接矩阵
A[i][j]=
0 其他情况 例如，前述G1、G2的邻接矩阵如下：
0 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0
上一页 下一页 返 回
6、 连通，强连通
若从顶点Vi到Vj(i≠j)有路径，则称Vi和Vj是连通的。
如果无向图中任意两个顶点Vi和Vj都是连通的，则称该
无向图是连通图。无向图中极大连通子图称为连通分量。 在有向图中，若任意两个顶点Vi和Vj都连通，即从Vi到 Vj和Vj到Vi都有路径，则称该有向图为强连通图。有向图中 的极大连通子图称为该有向图的强连通分量。
上一页 下一页 返 回
2、 完全图 在无向图中，若每对顶点之间都连有一条边， 则称该图为无向完全图。n个顶点的图具有n(n-1) 条弧的有向图称为有向完全图。 3、 子图 对于图G=（V，E），G′=（V′，E′），若有 V′∈V，E′∈E，则称图G′是G的子图。
上一页
下一页
返 回
4、 顶点的度（degree） 顶点的度是图中和Vi相关联的边的数目，记为 TD（Vi）。 在有向图中，要区别顶点的入度与出度。 入度(indegree)指以Vi为头的弧的数目,记为ID(Vi); 出度(outdegree)指以Vi为尾的弧的数目,记为 OD(Vi)； 故顶点的度TD（Vi）=ID（Vi）+OD（Vi） 有n个顶点，e条边的弧的图中，有2e=∑TD(Vi)
通常用（Vi，Vj）表示顶点Vi和Vj间相连的边，(Vi，Vj)与（Vj， Vi）同边。
有向图：若图中表示边的顶点是有序的，则称G为有向图。 弧：有向边通常称为弧（Arc），用<Vi，Vj>表示从顶点Vi到 顶点Vj的一条弧，并称Vi为弧尾（始点），Vj是弧头（终 点）。在有向图中，<Vi，Vj><Vj，Vi>表示两条不同的弧。
上一页 下一页 返 回
7.2.2 邻接链表表示法
邻接链表是图的一种链式存储结构。适用于无向图， 也适于有向图。在邻接链表中，对图中的每个顶点建立一
个单链表。单链表中的结点称为表结点。单链表有一个表
头结点。 表头结点的结构为:
Vertex
Link
★其中，Vertex域存放图中顶点Vi的信息，Link域为 指针，指向对应的单链表中的结点。邻接链表将所有