圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台第5章图5.1知识要点总结一、图的基本概念1．图的定义和术语一个图（G）定义为一个偶对（V，E），记为G=（V，E）。其中：V是顶点（Vertex）的非空有限集合，记为V（G）；E是边的集合，记为E（G），其元素是图的弧（Arc）。图的形式化定义为：G=（V，E）V={v|v?dataobject}E={|v，w?V∧p（v，w）}（P（v，w）表示从顶点v到顶点w有一条直接通路）（1）弧（Arc）：表示两个顶点v和w之间存在一个关系，用顶点偶对表示。通常根据图的顶点偶对将图分为有向图和无向图。（2）有向图（Digraph）：若图G的关系集合E（G）中，顶点偶对的v和w之间是有序的，称图G是有向图。在有向图中，若∈E（G），表示从顶点v到顶点w有一条弧。其中：v称为弧尾或始点，w称为弧头或终点。（3）无向图（Undigraph）：若图G的关系集合E（G）中，顶点偶对的v和w之间是无序的，称图G是无向图。在无向图中，若∈E（G），有∈E（G），即E（G）是对称，则用无1/131圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台序对（v，w）表示v和w之间的一条边（Edge），因此（v，w）和（w，v）代表的是同一条边。（4）完全无向图：对于无向图，若图中顶点数为n，用e表示边的数目，则e∈[0，n（n-1）/2]。具有n（n-1）/2条边的无向图称为完全无向图。完全无向图另外的定义是：对于无向图G=（V，E），若vi，vj∈V，当vi≠vj时，有（vi，vj）∈E，即图中任意两个不同的顶点间都有一条无向边，这样的无向图称为完全无向图。（5）完全有向图：对于有向图，若图中顶点数为n，用e表示弧的数目，则e∈[0，n（n-1）]。具有n（n-1）条边的有向图称为完全有向图。完全有向图另外的定义是：对于有向图G=（V，E），若vi，vj∈V，当vi≠vj时，有∈E∧∈E，即图中任意两个不同的顶点间都有一条弧，这样的有向图称为完全有向图。（6）权（Weight）：与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的距离或耗费。（7）子图和生成子图：设有图G=（V，E）和G’=（V’，E’），若V’?V且E’?E，则称图G’是G的子图；若V’=V且E’?E，则称图G’是G的一个生成子图。（8）顶点的邻接（Adjacent）：对于无向图G=（V，E），若边（v，w）∈E，则称顶点v和w互为邻接点，即v和w相邻接。边（v，w）依附（incident）与顶点v和w。对于有向图G=（V，E），若有向弧∈E，则称顶点v“邻接到”顶点w，顶点w“邻接自”顶点v，弧与顶点v和w“相关联”。（9）顶点的度、入度、出度对于无向图，依附于该顶点的边的数目称为顶点的度。2/131圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台对于有向图，以顶点作为起点的有向边的数目称为该顶点的出度；以顶点作为终点的有向边的数目称为该顶点的入度。顶点的出度与入度之和称为该顶点的度。（10）路径、路径长度、回路对无向图G=（V，E），若从顶点vi经过若干条边能到达vj，称顶点vi和vj是连通的，又称顶点vi到vj有路径。对有向图G=（V，E），从顶点vi到vj有路径，指的是从顶点vi经过若干条有向边（弧）能到达vj。路径是图中连接两顶点之间所经过的顶点序列。路径上边或有向边（弧）的数目称为该路径的长度。在一条路径中，若没有重复相同的顶点，该路径称为简单路径；第一个顶点和最后一个顶点相同的路径称为回路（环）；在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的回路称为简单回路（简单环）。（11）连通图、图的连通分量对无向图G=（V，E），若vi，vj∈V，vi和vj都是连通的，则称图G是连通图，否则称为非连通图。若G是非连通图，则极大的连通子图称为G的连通分量。对有向图G=（V，E），若vi，vj∈V，都有以vi为起点，vj为终点以及以vj为起点，vi为终点的有向路径，称图G是强连通图，否则称为非强连通图。若G是非强连通图，则极大强连通子图称为G的强连通分量。“极大”的含义：指的是对子图再增加图G中的其它顶点，子图就不再连通。（12）生成树和生成森林一个连通图的生成树是一个极小连通子图，它含有图中全部n个顶点和构成一棵树的n-1条边，成为图中的生成树。3/131圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台有向图的生成森林是这样一个子图，由若干棵有向树组成，含有图中全部顶点。有向树是只有一个顶点的入度为0，其余顶点的入度均为1的有向图。（13）网：每个边都附加一个权值的图，称为带权图。带权的连通图称为网或网络。【例】以下关于图的说法正确的是（）。Ⅰ．图G的生成树是该图的一个极小连通子图Ⅱ．生成树中最长路径韵起点和终点的度均为1Ⅲ．对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点A．Ⅰ、ⅡB．Ⅱ、ⅢC．Ⅰ、ⅢD．仅有Ⅱ【答案】D【解析】①说法Ⅰ是错误的，图G的生成树是该图的一个极小连通子图，但必须包含全部顶点。②说法Ⅱ是正确的，可用反证法证明。设V1，v2，…，vk是生成树的一条最长路径，其中，v1为起点，vk为终点，若vk的度为2，取vk的另一个邻接点v，由于生成树中无回路。v在最长路径上，显然v1，v2，…，vk，v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。同理可证起点v1，的度不能大于1，只能为1。③说法Ⅲ是错误的，只有连通图从某个顶点出发进行一次遍历，可访问图的所有顶点。2．图的基本操作图的基本操作主要包括：4/131圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台Neighbors（G，x）：列出G中与结点x邻接的边。Adjacent（G，x，y）：判断图G中是否存在边或。InsertVertex（G，x）：在图G中插入顶点x。DeleteVertex（G，x）：从图G中删除顶点x。AddEdge（G，x，y）：如果边不存在，则向图G中插入该边。RemoveEdge（G，x，y）：如果边存在，则从图G中删除该边。FirstNeighbor（G，x）：求图G中顶点x的第一个邻接顶点，存在则返回该顶点，不存在则返回0。NextNeighbor（G，x，y）：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接顶点，如果没有，则返回0。GetEdgeValue（G，x，y）：获取图G中边（x，y）或对应的权值。SetEdgeValue（G，x，y，v）：设置图G中边（x，y）或对应的权值为v。二、图的存储及基本操作图的存储结构比较复杂，其复杂性主要表现在：任意顶点之间可能存在联系，无法以数据元素在存储区中的物理位置来表示元素之间的关系。图中顶点的度不一样，有的可能相差很大，若按度数最大的顶点设计结构，则会浪费很多存储单元，反之按每个顶点自己的度设计不同的结构，又会影响操作。图的常用的存储结构有：邻接矩阵、邻接链表、十字链表和邻接多重表。1．邻接矩阵法5/131
