例:有向图的邻接矩阵 2 顶点表:(1vv3v4) A 邻接矩阵:「0110y1 AEdge=0000v2 3 v4) 00013 1000 注:在有向图的邻接矩阵中, 第i行含义:以结点v为尾的弧(即出度边) 第列含义:以结点v为头的弧(即入度边) 分析1:有向图的邻接矩阵可能是不对称的。 分析2:顶点的出度=第i行元素之和,OD(V= CAEdgel 顶点的入度=第列元素之和。ID(V= 2A. Edge! 顶点的度=第行元素之和+第列元素之和 即:TD=0D()+ID)
21
特别讨论:网(即有权图)的邻接矩阵 定义为: aEdgel i l[ j=a无边(Z)vy)evR V<v;v;>或(v 以有向网为例: 5 顶点表:(V1V2v4wv) ②,邻接矩阵:(5 7 o OC 8 N 3 NEdge 0040O 9 8 00050006 O00500 5 邻接矩阵法优点:容易实现图的操作,如:求某顶点的度、判断 顶点之间是否有边(弧)、找顶点的邻接点等等。 邻接矩阵法缺点:n个顶点需要物个单元存储边(弧);空间效率 为0(n2)。对稀疏图而言尤其浪费空间
22
的降储豪录 注:用两个数组分别存储顶点表和邻接矩阵 #define infinity int max //最大值∞ define maX verteX num20//假设的最大顶点数 Typedef enum{DG,DN,AG,AN} Graph Kind;/有向/无向图,有向/无向网 Typedef struct ArcCel!//弧(边)结点的定义 Ⅴ RType adi;/顶点间关系,无权图取1或0;有权图取权值类型 InfoType *info;//该弧相关信息的指针 3 ArcCell, AdjMatrix I MAX_ VERTEX_ NUM[ MAX VERTEX NUM Typedef struct //图的定义 VertexType veXs MAX VERTEX NUM;//顶点表,用一维向量即可 AdjMatrix arcs; //邻接矩阵 int vernum, arcum;//顶点总数,弧(边)总数 Graph Kind kind;//图的种类标志 3 Mgraph: 对于n个顶点的图或网,空间效率=0(n2)
23
例:用邻接矩阵生成无向网的算法 Status CreateUDN(Mgraph&G){/无向网的构造,用邻接矩阵表示 scanfe(& G. vexnum,& G arcum,& IncInfo);//输入总顶点数,总弧数和信息 for(i=0;i< G. vexnum,;++i) scant(& G vex[);//输入顶点值,存入一维向量中 for(i=0;i< G. vexnum;++i)//对邻接矩阵n*n个单元初始化,adj=∞,info=NULL for(j=0;j<G. vexnum; ++D Garcs[l=(INFINITY, NULLi; for(k=0:k< Garenum;++k){//给邻接矩阵有关单元赋初值(循环次数=弧数 scanf(&v1,&v2,&w);//输入弧的两顶点以及对应权值 i= Locate yex(G,v1);j= Locate vex(G,2);//找到两顶点在矩阵中的位置(m次? G.rcs]j]adj=w;/输入对应权值 if( IncInfo) Inpute(G.arcs[ il. info);//如果弧有信息则填入 Grcj]= G.ares jl[i;//无向网是对称矩阵 return oK: 3 //CreateUDN 对于n个顶点e条弧的网, 建网时间效率=0(n2+n+e*n
24
、漫示 对每个顶点v建立一个单链表,把与v;有关联的边的信息(即 度或出度边)链接起来,表中每个结点都设为3个域; 头结点 表结点 data firstar adjvex nextare info 数据域,存目链域,指向邻接点域,表链域,指向数据域,与 储顶点v信单链表的第示v一个邻接v下一个边边有关信息 息 一个结点 点的位置 或弧的结点(如权值 每个单链表还应当附设一个头结点(设为2个域),存v信息; 每个单链表的头结点另外用顺序存储结构存储
25