资源描述：
《【精品数据结构】图结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第6章图结构若干个结点与若干条边构成的结构结点是一些具体对象的抽象边是对象间的关系图是一种复杂的非线性结构，它有极强的表达能力图中结点可有多个前趋和多个后继这里着重讨论图的存贮结构与基本操作的实现1§6.1图的基本概念§6.1.1图的概念1．图图是由若干个结点和若干条边构成的结构，每个结点具有任意多个前驱和后继。结点集合：结点代表对象边集合：两结点之间的边表示它们代表的对象之间的关系在具体应用中，结点与边要被赋予具体的含意,如结点代表城市边代表城市之间的行程。12543abcd2§6.1.1图的概念1．图图是形为G=(V,R)的数据结构，其中，V={x
2、x属于
3、数据对象}R={VR}VR={
4、p(x,y)∧x∈V∧y∈V}这里，p(x,y)是V上的一个谓词，p(x,y)为真当且仅当x与y存在问题世界中的关系。图的形式化定义3§6.1.1图的概念2．有向/无向图若二元关系VR是对称的（即对任意x与y，若有∈VR，则必有∈VR），则称图G是无向图，否则称有向图。对无向图，我们用(x,y)表示。12543abcd4§6.1.1图的概念3．结点、边、弧图中的数据元素称为结点（或顶点）有时为了强调，对有向图，称为弧，x与y分别为弧尾与弧头，称x与y分别为的始点与终点，
5、称y为x的出点/可达邻接点，称x为y的入点，称为x的出边/出弧，为y的入边/入弧。对无向图，称为边。在讨论图中，一般用自然数串给结点编号。12543abcd5【例6‑1】设有两个二元组G1=(V1,R1)与G2=(V2,R2)，其中，V1={1,2,3,4,5}R1={VR1}VR1={<1,2>,<1,5>,<2,1>,<2,4>,<3,5>,<4,1>}V2={a,b,c,d}R2={VR2}VR2={(a,b),(a,d),(b,d),(d,c)}12543abcd(a)有向图(a)无向图【图‑】图示例6§6.1.1图的概念
6、4．邻接、关联对图中任意结点x与y，若它们之间存在边的关系（即有，或），则称x与y邻接，它们互为邻接点。同时称x或y与边（或或(x,y)）关联。12543abcd7§6.1.1图的概念5．度对任一结点x，称以它为头的弧的个数为它的入度称以它为尾的弧的个数为它的出度称它的入度与出度之和为它的度。对无向图，无出度入度之分，直接称与它关联的边的个数为它的度。12543abcd8§6.1.1图的概念6．权权是一个数值量，是某些信息的数字化抽象。权分边权与结点权，分别是边与结点的问题世界所关心的信息的数值化表示。例如，若结点代表城
7、市，则边权可代表城市之间的交通费用。12543607020017070909§6.1.1图的概念7．路径（通路）对有向图，若存在弧序列，，…，且n≥1，则称从x0到xn有通路（路径）。上列序列称为x0到xn的路径。该路径也可表示为(x0,x1,…,xn)1254310§6.1.1图的概念7．路径（通路）（续）对无向图，若有边序列(x0,x1)，(x1,x2)，…，(xn-1,xn)且n≥1，则称x0与xn之间有路径（通路），该路径可用上列边序列表示，亦可用下列结点序列表示(x0,x1,…,xn)abcd11§6.1
8、.1图的概念7．路径（通路）（续）路径中边的数目称为路径长。若x0=xn，则称相应的路径为回路/环路。若在路径(x0,x1,…,xn)中，除x0与xn外，任意其它结点均不相同，则称该路径为简单路径。起点与终点重合的简单路径称为简单回路。abcd1254312§6.1.1图的概念8．子图/生成图若某图G'的结点集合与边集合分别是另一图的G的结点集合和边集合的子集，则称G'为G的子图。设有两个图G与G'，若它们的结点集合相同，但G'的边集合是G的边集合的子集，则称G'是G的生成图。显然，生成图一定是子图，但反之未必。abcd1254313§6.1.1图的概念9．连
9、通若图中任意两结点间均有通路（x到y与y到x），则称该图是（强）连通的。若图中某子图是连通的，则称该子图为一个连通分量。若G的某子图G'是连通的，并且，若有G的另一子图G''包含图G'，则G''必不连通,则称G'是极大连通分量。abcd1254314§6.1.1图的概念9．连通（续）对于有向图，若任意两结点间至少有单向通路，但有些结点无双向通路，则称该图为弱连图。类似地，也有弱连通分量的概念。1254315§6.1.1图的概念10．生成树无回路的连通的无向图的生成图，称为该无向图的生成树。【定理6‑1】生成树中边的个数为结点个数减1.abcdabcdabcd1
10、6§6.1.2图的基本操作①检索：·按
