数据结构II5--第7章图1.ppt

该【数据结构II5--第7章图1 】是由【小落意】上传分享，文档一共【66】页，该文档可以免费在线阅读，需要了解更多关于【数据结构II5--第7章图1 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构II5--第7章图1
图的抽象数据类型定义:
ADTGraph{
数据对象V:V是具有相同特性的数据元素的集合,称为顶
点集。
数据关系R:
R={VR}
VR={<v,w>|v,w∈V且P(v,w),<v,w>表示从v到w的弧,
谓词P(v,w)定义了弧<v,w>的意义或信息}
基本操作P:
GreateGraph(&G,V,VR);
DestroyGraph(&G);
LocateVex(G,u);
GetVex(G,v);
PutVex(&G,v,Value);
FirstAdjVex(G,v);
NextAdjVex(G,v,w);
InsertVex(&G,v);
DeleteVex(&G,v);
InsertArc(&G,v,w);
DeleteArc(&G,v,w);
DFSTraverse(G,v,Visit());
BFSTraverse(G,v,Visit());
}ADTGraph
v2
v1
v3
v4
v5
v2
v1
v4
v3
例如:G1=(v1,{A1})
其中:
v1={v1,v2,v3,v4,}
A1={<v1,v2>,<v1,v3>,
<v3,v4>,<v4,v1>}
例如:G2=(v2,{E2})
其中:
v2={v1,v2,v3,v4,v5}
E2={(v1,v2),(v1,v4),(v2,v3)
(v2,v5),(v3,v4),(v3,v5)}
设图中顶点数为n,边或弧数为e,则:
对于无向图,e的取值范围为0~~n(n-1)/2
具有n(n-1)/2条边的无向图称为完全图
对于有向图,e的取值范围为0~~n(n-1)
具有n(n-1)条边的有向图称为有向完全图
和图中边相关的数叫作权(weigth)
带权的图称为网
顶点的度是和该顶点相关联的边的数目。记作TD(v)
以顶点v为头的弧的数目称为v的入度。记作ID(v)
以顶点v为尾的弧的数目称为v的出度。记作OD(v)
顶点v的度TD(v)=ID(v)+OD(v)
邻接点:对于无向图G=(V,{E}),如果边(v,v’)∈E,则称顶
点v和v’互为邻接点
路径:路径是顶点的序列V={Vi0,Vi1,……Vin},
满足(Vij-1,Vij)E或<Vij-1,Vij>E,(1<jn)
路径长度:沿路径边的数目或沿路径各边权值之和
回路:第一个顶点和最后一个顶点相同的路径
简单路径:序列中顶点不重复出现的路径
简单回路:除了第一个顶点和最后一个顶点外,其余顶点不
重复出现的回路
连通:从顶点V到顶点W有一条路径,则说V和W是连通的
连通图:无向图中任意两个顶点都是连通的
连通分量:无向图中的极大连通子图
强连通图:有向图中,如果对每一对Vi,VjV,ViVj,从Vi到
Vj和从Vj到Vi都存在路径,则称G是强连通图
强连通分量:有向图中的极大强连通子图
有向完全图:具有n(n-1)条边的有向图
无向完备图:具有n(n-1)/2条边的无向图
权:与图的边或弧相关的数
网:带权的图

多重链表
例
G1
2
4
1
3
V1
V2^^
V4^
V3^
例
1
5
3
2
4
G2
^V1
V2
V4^
V5^
V3
实际中不适用
数组表示法(邻接矩阵)
设G=(V,E)是有n1个顶点的图,G的邻接矩阵A是具有以下性质的n阶方阵
A[i][j]=
1,若(Vi,Vj)E或<Vi,Vj>E
0,其它
例
G1
v2
v4
v1
v3
例
v1
v5
v3
v2
v4
G2








v1
v3
v2
v4










v1
v3
v2
v4
v5
图的数组(邻接矩阵)存储表示
#defineINFINITYINT_MAX
#defineMAX_VERTEX_NUM20
typedefenum{DG,DN,UDG,UDN}GraphKind;
typedefstructArcCell{
VRTypeadj;
InfoType*info;
}ArcCell,djMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct{
VertexTypevexs[MAX_VERTEX_NUM];
AdjMatrixarcs;
intvexnum,arcnum;
GraphKindkind;
}MGraph;
图的邻接表存储表示
#defineMAX_VERTEX_NUM20
typedefstructArcNode{
int adjvex;
structArcNode*nextarc;
InfoType *info;
}ArcNode;
typedefstructVnode{
VertexTypedata;
ArcNode*firstarc;
}Vnode,AdjList[MAX_VERTEX_NUM];
typedefstruct{
AdjListVertices;
int vexnum,arcnum;
int kind;
}ALGraph;
adjvex
nextarc
info
表结点
data
firstarc
头结点