第7章-1-(7.1-7.2图的定义及存储结构)

1、第7章 图本章教学目的与要求：掌握图的基本概念、存储方法、基本操作。掌握与图相关的一些算法，如遍历、最短路径、最小生成树等。7.1图的定义和术语图的实例其中用圆圈标示的是数据元素，在图中称为其中用圆圈标示的是数据元素，在图中称为顶点顶点。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345图图G1图图G2图图G37.1图的定义和术语顶点之间的连线，表示数据元素之间的顶点之间的连线，表示数据元素之间的关系关系。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345图图G1图图G2图图G32022-4-304v图图(Graph)图图G是由两个集合是由两

2、个集合V(G)和和E(G)组成组成 的的,记为记为G=(V,E)其中：其中：V(G)V(G)是顶点的非空有限集是顶点的非空有限集 E(G)E(G)是是关系关系的有限集合，的有限集合，关系关系是顶点的无序对或有序对是顶点的无序对或有序对v有向图有向图有向图有向图G是由两个集合是由两个集合V(G)和和E(G)组成组成 V(G)V(G)是顶点的非空有限集，是顶点的非空有限集，E(G)E(G)是是有向边有向边（也称（也称弧弧）的有限）的有限集合，弧是顶点的有序对，记为集合，弧是顶点的有序对，记为，vi,vjvi,vj是顶点，是顶点，vi vi为为弧尾，弧尾，vjvj为弧头为弧头v无向图无向图无向图无向

3、图G是由两个集合是由两个集合V(G)和和E(G)组成组成 V(G)V(G)是顶点的非空有限集，是顶点的非空有限集，E(G)E(G)是是边边的有限集合，边是顶的有限集合，边是顶 点的无序对，记为（点的无序对，记为（vi,vjvi,vj）或（或（vj,vivj,vi) )，并且并且（vi,vjvi,vj)=()=(vj,vivj,vi) )图图的概念的概念v1v2v3v4v1v2v3v4v5图图G1图图G2G1=(V1,A1)其中，其中，V1=v1,v2,v3.v4 A1=,G2=(V2,E2)其中，其中，V2=v1,v2,v3.v4,v5 E2=(v1,v2),(v1,v4),(v2,v3),(

4、v2,v5),(v3,v4),(v3,v5)7.1图的定义和术语在在G1中，连线上有箭头表示方向，则该连线称为中，连线上有箭头表示方向，则该连线称为弧弧。我们。我们可以用可以用表示一条弧，表示一条弧，v1称为称为弧尾弧尾，v2称为称为弧头弧头。相应的，图相应的，图G1称为称为有向图有向图。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345图G1图G2图G37.1图的定义和术语在在G2中，没有箭头的连线称为中，没有箭头的连线称为边边。图。图G2称为称为无向图无向图。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345图图G1图图G2图图G37.1

5、图的定义和术语在在G3中，连线上标有与之相关联的数值（称为权），这种中，连线上标有与之相关联的数值（称为权），这种形式的图通常称为形式的图通常称为网网。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345图图G1图图G2图图G37.1图的定义和术语有有n个顶点，且每两个顶点之间均有边的无向图，称为个顶点，且每两个顶点之间均有边的无向图，称为完完全图全图。完全图共有。完全图共有n*（n-1）/ 2条边。条边。几个完全图的例子如下：几个完全图的例子如下：v1v2v3v4v1v1v2v1v2v37.1图的定义和术语有有n个顶点，且每两个顶点之间均有边的有向图，称为个顶点，且每

6、两个顶点之间均有边的有向图，称为有有向完全图向完全图。有向完全图共有。有向完全图共有n*（n-1）条边。条边。几个几个有向完全图有向完全图的例子如下：的例子如下：v1v2v3v4v1v1v2v1v2v3v子图子图如果图如果图G(V,E)G(V,E)和图和图G G(V(V,E,E), ),满足：满足：V V V V，E E E E 则称则称G G为为G G的子图的子图24513635621v1v3v4v2v1v3v2v3v47.1图的定义和术语7.1图的定义和术语在无向图中，若在无向图中，若(v,w)是一条边，是一条边， (v,w) E则则v,w互为互为邻接点邻接点uvw7.1图的定义和术语在无

7、向图中，顶点在无向图中，顶点v的的度度是指与是指与v相连的边的条数。相连的边的条数。uvw7.1图的定义和术语在有向图中，顶点在有向图中，顶点v的的出度出度是指是指v作为弧尾的作为弧尾的弧的条数。记为弧的条数。记为OD(v)uvw7.1图的定义和术语在有向图中，顶点在有向图中，顶点v的的入度入度是指是指v作为弧头的作为弧头的弧的条数。记为弧的条数。记为ID(v)uvw7.1图的定义和术语在有向图中，顶点在有向图中，顶点v的的度度是指是指v的入度和出度的入度和出度之和。记为之和。记为TD(v)TD(v)=ID(v)+OD(v)uvw7.1图的定义和术语顶点顶点v到顶点到顶点w的的路径路径指从指从

8、v出发沿着边或者弧到达出发沿着边或者弧到达w所经过的顶点序列。所经过的顶点序列。如上图中如上图中 v-v2-w 是从是从v到到w的一条路经的一条路经路径上边或者弧的数目称为路径上边或者弧的数目称为路径的长度路径的长度。序列中顶点不重复的路径称为序列中顶点不重复的路径称为简单路径简单路径vv2v3v4w7.1图的定义和术语第一个顶点和最后一个顶点相同的路径称为第一个顶点和最后一个顶点相同的路径称为回路回路或者或者环。环。路径路径 v-v2-v3-v4-v 就是一条回路就是一条回路除第一个顶点和最后一个顶点之外，其余顶点不重复出现除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为的回路

9、，称为简单回路或者简单环简单回路或者简单环vv2v3v4w7.1图的定义和术语在无向图中，如果从在无向图中，如果从v到到w之间有路径，则称顶点之间有路径，则称顶点v和顶点和顶点w是是连通的连通的。如果图中任意两个顶点都是连通的，则称该图为如果图中任意两个顶点都是连通的，则称该图为连通图连通图。vv2v3v4w连通图连通图7.1图的定义和术语上图看作一个整体，不是上图看作一个整体，不是连通图连通图。v1v2v3v4v5v6v77.1图的定义和术语无向图中的一个无向图中的一个极大连通子图极大连通子图，称为该图的，称为该图的连通分量连通分量。v1v2v3v4v5v6v3v6v1v2v4v52个连通分

10、量个连通分量G0上图上图G0不是连通图，有两个不是连通图，有两个连通分量连通分量.v强连通图强连通图有向图中，如果对每一对有向图中，如果对每一对Vi,VjVi,Vj V V, , ViVi VjVj, ,从从ViVi到到VjVj 和从和从VjVj到到 ViVi都存在路径，则称都存在路径，则称G G是是强连通图强连通图强连通图强连通图356245136非强连通图非强连通图7.1图的定义和术语v1v2v3v4v5v1v2v3v47.1图的定义和术语上图上图G1不是强连通图，有两个不是强连通图，有两个强连通分量强连通分量 ：G1-1和和G1-2v1v2v3v4图图G1v1v3v4图图G1-1v2图图

11、G1-2有向图中的有向图中的极大极大强连通子图称为有向图的强连通子图称为有向图的强连通分量强连通分量。7.1图的定义和术语连通图的连通图的生成树生成树是一个是一个极小连通子图极小连通子图。生成树中包含图的全部顶点（假定为生成树中包含图的全部顶点（假定为n个），包含能够连接个），包含能够连接起起n个顶点的个顶点的n-1条边，使得生成树也是一个连通图。条边，使得生成树也是一个连通图。如上面图如上面图G2-1为图为图G2的一棵的一棵生成树生成树。v1v2v3v4v5图G2v1v2v3v4v5图G2-12022-4-3025一个连通图的一个连通图的生成树生成树是一个是一个极小连通子图极小连通子图，它含

12、有图中它含有图中全部顶点全部顶点，但只有足以构成一棵，但只有足以构成一棵树的树的n-1条边条边。一棵有一棵有n个顶点的生成树有且仅有个顶点的生成树有且仅有n-1条边。条边。15732461573246连通图连通图生成树生成树26抽象数据类型-图ADT Graph 数据对象数据对象 V：V是具有相同特性的数据元素的集合，称为顶点集。是具有相同特性的数据元素的集合，称为顶点集。 数据关系数据关系 R：R=VR VR= |v,wv,w V V且且P(v,wP(v,w), 表示从表示从v v到到w w的弧，的弧， 谓词谓词P(v,wP(v,w)定义了弧定义了弧 的意义或信息的意义或信息 基本操作基本操

13、作P： GraphCreat(G,，V，VR)；/创建图创建图 GraphDestory(G)；/销毁图销毁图 GraphLocateVertex(G，v)；/寻找顶点寻找顶点v GraphGetVertex(G，v)；/返回顶点返回顶点v的值的值 GraphPutVertex(&G，v, value)；/为顶点为顶点v赋值赋值 GraphFirstAdjVex(G，v)；/返回返回v的第一个邻接顶点的第一个邻接顶点 GraphNextAdjVex(G，v，w)；/返回返回v的下一个邻接顶点的下一个邻接顶点 GraphInsertVertex(G，v)；/在图中添加新顶点在图中添加新顶

14、点v GraphDeleteVertex(G，v)；/删除顶点删除顶点v及相关的弧及相关的弧 GraphInsertArc(G，v，w)；/在图中增加弧在图中增加弧 GraphDeleteArc(G，v，w)；/删除图中删除图中v和和w之间的弧之间的弧 DFSTtraverse(G，v，Visit()；/深度优先遍历深度优先遍历 BFSTtraverse(G，v，Visit()；/广度优先遍历广度优先遍历 ADT Graph 7.2 图的存储结构 由于图的顶点之间存在多对多的关系，因此，图由于图的顶点之间存在多对多的关系，因此，图的存储结构相应的比较复杂。的存储结构相应的比较复杂。本节我们介绍

15、两种最常用的存储结构，本节我们介绍两种最常用的存储结构，邻接矩阵邻接矩阵表示表示法法(数组表示法数组表示法)和和邻接表邻接表表示法。表示法。十字链表十字链表表示法表示法邻接多重表邻接多重表表示法表示法7.2.1邻接矩阵表示法（数组表示法）用一个一维数组存储顶点的信息。用一个一维数组存储顶点的信息。用一个二维数组存储数据元素之间关系用一个二维数组存储数据元素之间关系(边或弧边或弧)的信息，的信息，这种表示方法我们称之为这种表示方法我们称之为邻接矩阵法邻接矩阵法。7.2.1邻接矩阵表示法（数组表示法）一、举例说明邻接矩阵表示法一、举例说明邻接矩阵表示法1.有向图有向图v1v2v3v4图G1v1v2

16、v3v4边信息数组边信息数组arcsv1v2v3v4v1v2v3v4顶点信息数组顶点信息数组vexs7.2.1邻接矩阵表示法（数组表示法）之间无边相连、若之间有边相连、若vjvivjvi01vjviarcsv1v2v3v4图G1v1v2v3v4边信息数组arcsv1v2v3v4v10110v20000v30001v41000顶点信息数组vexs7.2.1邻接矩阵表示法（数组表示法）v1v2v3v4图G1v1v2v3v4边信息数组arcsv1v2v3v4v10110v20000v30001v41000思考思考：（1）如何从）如何从arcs寻找寻找v1的出度、入度，邻接点；的出度、入度，邻接点；（

17、2）是否能从）是否能从arcs判断该图是否有向图。判断该图是否有向图。顶点信息数组vexs7.2.1邻接矩阵表示法（数组表示法）边信息数组arcsv1v2v3v4v10110v20000v30001v41000解答：解答：（1）如何从）如何从arcs寻找寻找v1的出度、入度，邻接的出度、入度，邻接点；点；V1行所有行所有1的个数为的个数为v1的出度；的出度；V1列所有列所有1的个数为的个数为v1的入度；的入度；V1行所有行所有1对应的下标在对应的下标在vexs中对应的顶点。中对应的顶点。（2）能否从）能否从arcs判断该图的类型，（有向图判断该图的类型，（有向图还是无向图）。还是无向图）。当当

18、arcs数组关于主对角线不对称时，可以肯定数组关于主对角线不对称时，可以肯定其是有向图。否则不能判定。其是有向图。否则不能判定。7.2.1邻接矩阵表示法（数组表示法）2.无向图无向图v1v2v3v4v5边信息数组arcsv1v2v3v4v5v1v2v3v4v5顶点信息数组vexsv1v2v3v4v5图G27.2.1邻接矩阵表示法（数组表示法）之间无边相连、若之间有边相连、若vjvivjvi01vjviarcsv1v2v3v4v5边信息数组arcsv1v2v3v4v5v10 101 0v21 010 1v30 101 1v41 010 00 110 0v5顶点信息数组vexsv1v2v3v4v5

19、图G27.2.1邻接矩阵表示法（数组表示法）思考思考：（1）如何从）如何从arcs寻找寻找v1的度，邻接点；的度，邻接点；（2）是否能从）是否能从arcs判断该图是否有向图。判断该图是否有向图。v1v2v3v4v5边信息数组arcsv1v2v3v4v5v10 101 0v21 010 1v30 101 1v41 010 00 110 0v5顶点信息数组vexsv1v2v3v4v5图G27.2.1邻接矩阵表示法（数组表示法）解答：解答：（1）如何从）如何从arcs寻找寻找v1的度，邻接点；的度，邻接点；V1行所有行所有1的个数为的个数为v1的度；的度；V1行所有行所有1对应的下标在对应的下标在v

20、exs中对应的顶点。中对应的顶点。（2）能否从）能否从arcs判断该图的类型，（有向图判断该图的类型，（有向图还是无向图）。还是无向图）。当当arcs数组关于主对角线不对称时，可以肯定数组关于主对角线不对称时，可以肯定其是有向图。否则不能判定。其是有向图。否则不能判定。边信息数组arcsv1v2v3v4v5v10 101 0v21 010 1v30 101 1v41 010 00 110 0v57.2.1邻接矩阵表示法（数组表示法）3.网网v1v2v3v4v5v61555346798v1v2v3v4v5v6顶点信息数组vexs7.2.1邻接矩阵表示法（数组表示法）v1v2v3v4v5v6155

21、5346798边信息数组arcsv1v2v3v4v5v6v157v24v389v4565v5v631之间无边相连、若之间有边相连、若vjvivjviwijvjviarcs二、用c语言描述图的存储结构及其操作1.存储结构存储结构 为了简单起见，我们假设顶点所代表数据的数据类型是字符为了简单起见，我们假设顶点所代表数据的数据类型是字符串，如串，如“v1”、“v2”等；考虑到顶点之间的边上可能带有权值，等；考虑到顶点之间的边上可能带有权值，则邻接矩阵的类型设为则邻接矩阵的类型设为double。当然大家可以根据应用问题的不。当然大家可以根据应用问题的不同，适当调整同，适当调整数据类型数据类型。stru

22、ct MGraphchar *vexs100;/存储顶点信息存储顶点信息double arcs100100;/存储边的信息存储边的信息 int vexnum,arcnum;/顶点数目和边的数目顶点数目和边的数目;二、用二、用c语言描述图的存储结构及其操作语言描述图的存储结构及其操作2.基本操作基本操作 图的基本操作包括图的初始化、查找顶点是否存在、查找边是否存在、插入图的基本操作包括图的初始化、查找顶点是否存在、查找边是否存在、插入一个顶点，插入一条边，删除一个顶点，删除一条边，求顶点的邻接点等。一个顶点，插入一条边，删除一个顶点，删除一条边，求顶点的邻接点等。void InitGraph(M

23、Graph &mg)/图的初始化图的初始化mg.arcnum=mg.vexnum=0;/顶点和边的数目均为顶点和边的数目均为0for(int i=1;i100;i+)for(int j=1;j100;j+) mg.arcsij=0; /各个顶点之间初始情况下没有边相连各个顶点之间初始情况下没有边相连二、用二、用c语言描述图的存储结构及其操作语言描述图的存储结构及其操作2.基本操作基本操作int FindVex(MGraph mg,char *vex)/查找顶点查找顶点vex是否存在是否存在for(int i=1;i=mg.vexnum;i+) if(strcmp(mg.vexsi,ve

24、x)=0)return i;/顶点存在，返回顶点存在，返回ireturn 0;/顶点不存在，返回顶点不存在，返回0二、用二、用c语言描述图的存储结构及其操作语言描述图的存储结构及其操作2.基本操作基本操作int FindArc(MGraph mg,char *v1,char *v2)/查找边或弧查找边或弧是否存在是否存在int x,y;x=FindVex(mg,v1);y=FindVex(mg,v2);if(x=0 | y=0) return 0; /某个顶点不存在某个顶点不存在,边肯定不存在，返回边肯定不存在，返回0if(mg.arcsxy=1) return 1;/边存在，返回边存在，返回

25、1二、用二、用c语言描述图的存储结构及其操作语言描述图的存储结构及其操作2.基本操作基本操作void InsertVex(MGraph &mg,char *vex)/插入一个顶点插入一个顶点vexif(FindVex(mg,vex)=0) /顶点不存在顶点不存在mg.vexnum+;mg.vexsmg.vexnum=new charstrlen(vex);strcpy(mg.vexsmg.vexnum,vex);/新顶点加入新顶点加入二、用二、用c语言描述图的存储结构及其操作语言描述图的存储结构及其操作2.基本操作基本操作void InsertArc(MGraph &mg,ch

26、ar *v1,char *v2)/插入一条边或弧插入一条边或弧int x,y;x=FindVex(mg,v1);y=FindVex(mg,v2);if(x & y) mg.arcsxy=1;mg.arcnum+;二、用二、用c语言描述图的存储结构及其操作语言描述图的存储结构及其操作2.基本操作基本操作int FirstAdjVex(MGraph mg,int v) /在图在图mg中，求顶点中，求顶点v的第一个邻接点的第一个邻接点/使用顶点的下标代替字符串，使用顶点的下标代替字符串，/如顶点如顶点“v1“对应下标为对应下标为v, 则使用则使用v代表代表“v1“for(int i=1;i=

27、mg.vexnum;i+) if(mg.arcsvi!=0)return i;return 0; /不存在邻接点时，返回不存在邻接点时，返回0二、用二、用c语言描述图的存储结构及其操作语言描述图的存储结构及其操作2.基本操作基本操作int NextAdjVex(MGraph mg,int v,int w)/在图在图mg中，求顶点中，求顶点v的相对于顶点的相对于顶点w的下一个邻接点的下一个邻接点for(int i=w+1;i=mg.vexnum;i+)if(mg.arcsvi!=0)return i;return 0;二、用二、用c语言描述图的存储结构及其操作语言描述图的存储结构及其操作2.基本

28、操作基本操作对于左图，可以用右面代码来构造对于左图，可以用右面代码来构造v1v2v3v4图图G1int main(int argc, char* argv ) MGraph mg; InitGraph(mg);/图的初始化图的初始化InsertVex(mg,v1);/插入顶点插入顶点InsertVex(mg,v2);InsertVex(mg,v3);InsertVex(mg,v4);InsertArc(mg,v1,v2);/插入边插入边InsertArc(mg,v1,v3);InsertArc(mg,v3,v4);InsertArc(mg,v4,v1); return 0;7.2.2 邻接表表

29、示法一、举例说明邻接表表示法一、举例说明邻接表表示法1.有向图有向图v1v2v3v4图图G11 v12 v23 v34 v42341思考：根据右图思考：根据右图1.如何求如何求v1的出度、入度、以的出度、入度、以v1为弧尾的邻接点？为弧尾的邻接点？2.如何求图中共有几条边？如何求图中共有几条边？7.2.2 邻接表表示法一、举例说明邻接表表示法一、举例说明邻接表表示法1.有向图有向图1 v12 v23 v34 v42341思考：思考：1.如何求如何求v1的出度、入度、以的出度、入度、以v1为弧尾的邻接点？为弧尾的邻接点？解答：解答：v1的出度是的出度是v1后面链表的长后面链表的长度。度。 V1的

30、入度为所有链表中数据域为的入度为所有链表中数据域为1的结点的个数。的结点的个数。V1的邻接点就是的邻接点就是v1后链表上的所有后链表上的所有结点。结点。2.如何求图中共有几条边？如何求图中共有几条边？所有链表中所有结点的个数。所有链表中所有结点的个数。7.2.2 邻接表表示法一、举例说明邻接表表示法一、举例说明邻接表表示法2.无向图无向图1 v12 v23 v34 v45 v524 41v1v2v3v4v5图G2135 25 3 23 思考：根据右图思考：根据右图1.如何求如何求v1的度、的度、v1的邻接点？的邻接点？2.如何求图中共有几条边？如何求图中共有几条边？7.2.2 邻接表表示法一、

31、用c语言描述图的邻接表存储结构及其操作1.存储结构存储结构 从上面的例子可以从上面的例子可以看出，邻接表中存在两看出，邻接表中存在两种结点，一种是种结点，一种是链表的链表的头结点头结点，用来存储，用来存储顶点顶点信息；一种是信息；一种是表结点表结点，用来存放用来存放邻接点以及边邻接点以及边的信息。的信息。1 v12 v23 v34 v45 v524 41135 25 3 23 7.2.2 邻接表表示法一、用c语言描述图的邻接表存储结构及其操作1 v12 v23 v34 v45 v524 41135 25 3 23 datafirstarc表头结点：表头结点：顶点信息顶点信息指向第指向第1个邻接

32、个邻接点的指针点的指针表结点表结点adjvexinfonextarc邻接点邻接点边或弧的信息（如边或弧的信息（如权值）权值）指向下一条边或指向下一条边或弧的结点弧的结点7.2.2 邻接表表示法一、一、用用c语言描述图的邻接表存储结构及其操作语言描述图的邻接表存储结构及其操作/表结点表结点-结构体类型结构体类型struct ArcNodeint adjvex; /邻接点邻接点double weight; /边的信息边的信息(权权)ArcNode *nextarc; /指向下一条边的指针指向下一条边的指针;7.2.2 邻接表表示法一、一、用用c语言描述图的邻接表存储结构及其操作语言描述图的邻接表存

33、储结构及其操作/头结点头结点-结构体类型结构体类型typedef struct VexNodechar data5;/顶点信息（字符串）顶点信息（字符串）ArcNode *firstarc;/指向第一条边的指针指向第一条边的指针VexNode;/图图-结构体类型结构体类型typedef structVexNode vexs100;/顶点的集合顶点的集合int vexnum,arcnum;/顶点的数目，边的数目顶点的数目，边的数目ALGraph;7.2.2 邻接表表示法一、一、用用c语言描述图的邻接表存储结构及其操作语言描述图的邻接表存储结构及其操作 图的基本操作包括图的基本操作包括图的初始化、

34、查找顶点是否存在、查找边是否存在、图的初始化、查找顶点是否存在、查找边是否存在、插入一个顶点，插入一条边，删除一个顶点，删除一插入一个顶点，插入一条边，删除一个顶点，删除一条边，求顶点的邻接点等。条边，求顶点的邻接点等。 void InitGraph(ALGraph &mg)/图的初始化图的初始化mg.arcnum=mg.vexnum=0;for(int i=1;i100;i+)strcpy(mg.vexsi.data,);mg.vexsi.firstarc=0;int FindVex(ALGraph mg,char *vex)/查找顶点查找顶点vex是否存在是否存在for(int i

35、=1;i=mg.vexnum;i+)if(strcmp(mg.vexsi.data,vex)=0)return i;return 0; /不存在不存在int FindArc(ALGraph mg,char *v,char *w)/查找边或弧查找边或弧是否存在是否存在int v1=FindVex(mg,v);int w1=FindVex(mg,w);if(v1 *w1=0) return 0; /不存在不存在ArcNode *p=mg.vexsv1.firstarc; /表结点表结点pwhile(p)if(p-adjvex=w1) return 1;/找到了找到了p=p-nextarc; /指向

36、下一条边指向下一条边(下一个邻接点下一个邻接点)return 0;/不存在不存在void InsertVex(ALGraph &mg,char *vex)/插入一个顶点插入一个顶点vexint v=FindVex(mg,vex);if(v!=0) return; /该顶点已经存在该顶点已经存在mg.vexnum+;strcpy(mg.vexsmg.vexnum .data,vex); return;void InsertArc(ALGraph &mg,char *v1,char *v2)/插入一条边或弧插入一条边或弧if(FindArc(mg,v1,v2)=0) /边不存在边不存在/此时我们假定顶点已经存在此时我们假定顶点已经存在ArcNode *p=new ArcNode; /定义表结点定义表结点 /生成一个新的结点生成一个新的结点 p-adjvex=FindVex(mg,v2);p-nextarc=0;p-weight=0;int v=FindVex(mg,v1); /新结点作为链表第一个结点新结点作为链表第一个结点p-nextarc=mg.vexsv.firstarc;mg.vexsv.firstarc=p;i