资源描述：
《图的基本概念及基本操作》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构与算法---第十八讲北方民族大学计算机科学与工程学院王伦津研究员图的基本概念及基本操作118、图的基本概念、图的基本操作，以及图的对象抽象模型掌握图的定义、结点、边、弧、邻接、关联、度、权、路径、子图、连通等有关术语及其图的检索、插入、删除、求邻接点、关联边、图的遍历等基本操作，了解图结点抽象模型、图的边对象抽象模型和图对象的抽象模型2目录18.1图结构18.2图的基本概念18.2.1图的概念18.2.2图的基本操作18.3图的对象抽象模型18.3.1图结点抽象模型18.3.2图的边对象抽象模型18.3.
2、3图抽象对象模型3这里的图，有时也称网络，是指由若干个结点与若干条边构成的结构，其中每个结点可有多个前趋和多个后继，结点是一些具体对象的抽象，而边是对象间的关系的抽象。值得注意的是，与一般意义下的图不同，这里的图只涉及图的拓扑结构，与图的几何性质无关。图论重点讨论图的数学性质，而这里的重点是图结点间的关系以及图的存贮结构与基本操作的实现。图是一种复杂的非线性结构，它有极强的表达能力，现实世界中许多问题均可用图结构描述。18.1图结构418.2.1图的概念1．图图(Graph)是由若干个结点和若干条边构成的结构，每
3、个结点具有任意多个前驱和后继。这种结构的含意为：结点集合V：结点代表对象Vertex边集合R：两结点之间的边表示它们代表的对象之间的关系18.2图的基本概念5形式化地讲，图是形为G=(V,R)的数据结构，其中，V={x
4、x属于数据对象}R={VR}VR={
5、p(x,y)∧x∈V∧y∈V}这里，p(x,y)是V上的一个谓词，p(x,y)为真当且仅当x与y存在问题世界中的关系。在具体应用中，结点与边要被赋予具体的含意。如结点代表城市，而边代表城市之间的行程。6若二元关系VR中的每个型如的成员中的x
6、与y是次序无关的，则称该图为无向图(undirecyedgraph)，否则称为有向图(directedgraph)。无向图也可以看作VR对称的图，即对任意x与y，若有∈VR，则必有∈VR。对无向图，我们用(x,y)表示。2有向/无向图73．结点、边、弧图中的数据元素称为结点（或顶点）(vertice/node/point)，有时为了强调，对有向图，称为弧(arc)，x与y分别为弧尾与弧头，或始点与终点，称y为x的出点/可达邻接点，称x为y的入点称为x的出边/出弧，
7、为y的入边/入弧。对无向图，泛称为边(edge)。在讨论图中，为了方便，一般给结点编号，用它们的编号代表它们。结点编号一般用自然数。12543abcd(a)有向图(b)无向图图18‑1图示例8例18‑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)}显然，它
8、们不满足线性结构、广义表和树的定义，而满足图的定义。12543abcd94．邻接、关联对图中任意结点x与y，若它们之间存在边（即有，或），则称x与y邻接(adjacent)，它们互为邻接点。同时称x或y与边（或或(x,y)）关联(incident)。5．度对任一结点x，称以它为头的弧的个数为它的入度(Indegree)；称以它为尾的弧的个数为它的出度(outdegree)；称它的入度与出度之和为它的度(degree)。对无向图，无出度入度之分，直接称与它关联的边的个数为它的
9、度。例如，图6-1(a)中的结点1的出度与入度都为2，结点3的出度入度分别为1和0，(b)中的结点a、b、度均为2，而d的度为3，c的度为1。106．权权(Weight)与哈夫曼树中的概念相同，即权是一个数值量，是某些信息的数字化抽象。权分边权与结点权，分别是边与结点的问题世界所关心的信息的数值化表示。例如，若结点代表城市，则边权可代表城市之间的交通费用。7．路径（通路）对有向图，若存在弧序列，，…，且n≥1，则称从x0到xn有通路（路径）(Path)。上列序列称为x
10、0到xn的路径。该路径也可表示为(x0,x1,…,xn)11对无向图，若有边序列(x0,x1)，(x1,x2)，…，(xn-1,xn)且n≥1，则称x0与xn之间有路径（通路），该路径可用上列边序列表示，亦可用下列结点序列表示(x0,x1,…,xn)路径中边的数目称为路径长。若x0=xn，则称相应的路径为回路/环路(loop)。若在路径(x0,x1,…,xn)中，除x0与
