数图的基本操作 LOC-VERTEX(G,v):顶点定位函数 构 GET-VERTEX(G,I):取顶点函数; FIRST-ADJ (G, v) 求第一个邻接点函数 之 NEXT-ADJ(G,v,w):求下一个接点函数; INS-VERTEX(G,u):插入顶点操作; 图INS-ARC(G,v,w):插入弧操作; DEL-VERTEX(G,v):删除顶点操作; DEL-ARC(G,v,w):删除弧的操作 72图的存储结构 数>邻接矩阵:用一个二维数组来表示图中的相邻关系。 设图G(V,NR)有n1个顶点,则G的邻接矩阵是 构按如下定义的n阶方阵: 1,若(i,V)或<i,Vj>∈VR 0,反之 无向图G2的邻接矩阵 0110 A1=0000 10101 12 0001 A2=01011 1000 10100 有向图G1的邻接矩阵 01100
6 数 据 结 构 之 图 11 图的基本操作 LOC-VERTEX（G，v）： 顶点定位函数； GET-VERTEX（G，I）： 取顶点函数； FIRST-ADJ（G，v）： 求第一个邻接点函数； NEXT-ADJ（G，v，w）： 求下一个接点函数； INS-VERTEX（G，u）： 插入顶点操作； INS-ARC（G，v，w）： 插入弧操作； DEL-VERTEX（G，v）： 删除顶点操作； DEL-ARC（G，v，w）： 删除弧的操作。 数 据 结 构 之 图 12 7.2 图的存储结构 ¾ 邻接矩阵：用一个二维数组来表示图中的相邻关系。 设图G=（V，VR）有n≥1个顶点，则G的邻接矩阵是 按如下定义的n阶方阵： 1，若（Vi , Vj )或<Vi , Vj>∈ VR A[i，j]= 0，反之 无向图G2的邻接矩阵 0 1 1 0 0 1 0 1 0 A1= 0 0 0 0 1 0 1 0 1 0 0 0 1 A2= 0 1 0 1 1 1 0 0 0 1 0 1 0 0 有向图G1的邻接矩阵 0 1 1 0 0
/例:分别写出下面图的邻接矩阵 0100 0100 1011 0010 0001 0110 0100 邻接矩阵存储的特点 数据结构 无向图的邻接矩阵是对称的,对有n个顶 点的无向图只需存入下三角矩阵,即需要 n(n+1)/2个存储单元; 而有向图的邻接矩阵不一定对称,对有n 个顶点的有向图需要n*n个单元来存储邻 接矩阵; 另外用向量来存储顶点的有关信息;
7 数 据 结 构 之 图 13 例：分别写出下面图的邻接矩阵。 1 2 3 4 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 2 3 4 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 数 据 结 构 之 图 14 ¾ 邻接矩阵存储的特点 ¾无向图的邻接矩阵是对称的，对有n个顶 点的无向图只需存入下三角矩阵，即需要 n(n+1)/2 个存储单元； ¾而有向图的邻接矩阵不一定对称，对有n 个顶点的有向图需要n*n个单元来存储邻 接矩阵； ¾另外用向量来存储顶点的有关信息；
求顶点的度 据结构 对无向图,vi的度数=邻接矩阵第i行元 素之和 TDi=∑AG,j=∑A[,i 对有向图,vi的出度=第i行元素之和 vi的入度=第i列元素之和 TD(Vi=OD(VITID(Vi) ∑A[i,+∑A[j,i >网的邻接矩阵 w,若(Vi,V)或<vi,vj>∈ⅤR 据A[i,jl=10,(i=j) 构 反之 05 04 0 0∞506 50 3∞∞∞10
8 数 据 结 构 之 图 15 ¾求顶点的度 ¾对无向图，Vi的度数=邻接矩阵第 i 行元 素之和 ¾对有向图，Vi的出度=第 i 行元素之和 Vi的入度=第 i 列元素之和 n n TD(Vi)=∑A[i,j]=∑A[j,i] j=1 j=1 TD(Vi)=OD(Vi)+ID(Vi) n n = ∑A[i,j]+∑A[j,i] j=1 j=1 数 据 结 构 之 图 16 ¾ 网的邻接矩阵 wi , j，若（Vi , Vj )或<Vi , Vj>∈ VR A[i，j]= 0 , ( i = j ) ∞，反之 0 5 ∞ 7 ∞ ∞ ∞ 0 4 ∞∞ ∞ 8 ∞ 0 ∞ ∞ 9 ∞ ∞ 5 0 ∞ 6 ∞∞∞ 5 0 ∞ 3 ∞ ∞∞ 1 0 V1 V2 V3 V4 V6 V5 1 5 3 5 4 8 7 9 6 5
>图的数组(邻接矩阵)存储表示邻接矩阵 #define max Data 35000 提# define VerNum20 结/有向图,有向网,无向图,无向网 M typedef enum(DG, DN, UDG, UDN GraphKind typedef char VertexType typedef int VRType;/顶点关系0/或“权值 typedef struct( VRType adj; Info Type *information; ArcType; typedef structi VertexType vex verNum; ArcType arcs VerNum VerNum; int vernum arenum. Graph Kind kind; MGraph; 采用邻接矩阵表示法,构造图 s Status Create Graph(MGraph &G)( 构 scanf(&G kind) switch(G kind)t case DG: return CreateDG(G) case DN: return CreateDN(G); case UDG: return CreateUDG(G); case UDN: return CreateUDN(G) default: return ERROR;
9 数 据 结 构 之 图 17 ¾ 图的数组（邻接矩阵）存储表示邻接矩阵 #define MaxData 35000 #define VerNum 20 /* 有向图，有向网，无向图，无向网 */ typedef enum{DG, DN, UDG, UDN}GraphKind; typedef char VertexType; typedef int VRType; /*顶点关系 0/1 或 “权值” typedef struct{ VRType adj; InfoType *information; }ArcType; typedef struct{ VertexType vexs[VerNum]; ArcType arcs[VerNum][VerNum]; int vernum, arcnum; GraphKind kind; } MGraph; 数 据 结 构 之 图 18 采用邻接矩阵表示法，构造图 Status CreateGraph(MGraph &G){ scanf(&G.kind); switch(G.kind){ case DG: return CreateDG(G); case DN: return CreateDN(G); case UDG: return CreateUDG(G); case UDN: return CreateUDN(G); default: return ERROR; } }
采用邻接矩阵表示法,构造无向网 Status CreateUDN(MGraph &G) scanf(&G. vexnum, &G arcum, &Infoflag); I* for(i-0;i<G. vexnum; i++)scanf(&G. vexs[il 构fori=0;i<G. vexnum;i+)/*邻接矩阵初始化* forG=0;j<G. vexnum: j++) if (i!=j) Garcs=Max Data, NULL G arcs[l=(0, NULL; for(k=0; k<G arcum; k++) scanf(&vl, &v2, &w); i=Locate Vex(G, vI); j=Locate vex(G, v2); G arcs[jl. adj=w;/弧<v1,v2>的权值* if(infoflag) input( G arcs[jj. information) 19 G.ares[jlliI=G arcs[illil; 3 return OK: 邻接链表 数 据 图的邻接链表存储结构是一种顺序分配和链 式分配相结合的存储结构:一部分是链表; 构 另一部分是向量 链表部分:每个顶点对应一个链表,共有n 个链表; 向量部分:用于存储n个链表的表头结点。 4 20 4 4vs-2一
10 数 据 结 构 之 图 19 采用邻接矩阵表示法，构造无向网 Status CreateUDN(MGraph &G){ scanf(&G.vexnum,&G.arcnum,&Infoflag); for(i=0;i<G.vexnum;i++) scanf(&G.vexs[i]); for(i=0;i<G.vexnum;i++) / *邻接矩阵初始化 */ for(j=0;j<G.vexnum;j++) if (i != j) G.arcs[i][j]={MaxData, NULL}; else G.arcs[i][j]={0, NULL}; for(k=0;k<G.arcnum;k++){ scanf(&v1,&v2,&w); i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs[i][j].adj=w; /*弧<v1,v2>的权值 */ if(infoflag) input(*G.arcs[i][j].information); G.arcs[j][i]=G.arcs[i][j]; } return OK; } 数 据 结 构 之 图 20 ¾ 邻接链表 ¾ 图的邻接链表存储结构是一种顺序分配和链 式分配相结合的存储结构：一部分是链表； 另一部分是向量。 ¾ 链表部分：每个顶点对应一个链表，共有n 个链表； ¾ 向量部分：用于存储n个链表的表头结点。 V1 V2 V4 V5 V3 0 v1 1 v2 2 v3 3 v4 4 v5 3 1 ^ 2 0 ^ 2 1 ^ 4 3 4 2 0 ^ 1 ^