抽象数据类型图的定义.ppt

第七章图7.1抽象数据类型图的定义图是由一个顶点集V和一个弧集R构成的数据结构。
Graph=(V,VR)
其中，VR＝{<v,w>|v,w∈V且P(v,w)}
<v,w>表示从v到w的一条弧，并称v为弧头，w为弧尾。
谓词P(v,w)定义了弧<v,w>的意义或信息。由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。若<v,w>VR必有<w,v>VR,
则称(v,w)为顶点v和顶点w之间存在一条边。名词和术语A假设图中有n个顶点，e条边，则假若顶点v和顶点w之间存在一条边，
则称顶点v和w互为邻接点，顶点的出度:以顶点v为弧尾的弧的数目;设图G=(V,{VR})中的一个顶点序列
{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)VR1≤j≤m,
则称从顶点u到顶点w之间存在一条路径。
路径上边的数目称作路径长度。若图G中任意两个顶点之间都有路径相通，则称此图为连通图;若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。结构的建立和销毁CreatGraph(&G,V,VR):
//按定义(V,VR)构造图对顶点的访问操作对邻接点的操作插入或删除顶点插入和删除弧遍历7.2图的存储表示Aij={有向图的邻接矩阵为非对称矩阵typedefstructArcCell{//弧的定义
VRTypeadj;//VRType是顶点关系类型。
//对无权图，用1或0表示相邻否；
//对带权图，则为权值类型。
InfoType*info;//该弧相关信息的指针
}ArcCell,
AdjMatrix[MAX_VERTEX_NUM]
[MAX_VERTEX_NUM];typedefstruct{//图的定义
VertexType//顶点信息
vexs[MAX_VERTEX_NUM];
AdjMatrixarcs;//弧的信息
intvexnum,arcnum;//顶点数，弧数
GraphKindkind;//图的种类标志
}MGraph;D有向图的邻接表AtypedefstructArcNode{
intadjvex;//该弧所指向的顶点的位置
structArcNode*nextarc;
//指向下一条弧的指针
InfoType*info;//该弧相关信息的指针
}ArcNode;typedefstructVNode{
VertexTypedata;//顶点信息
ArcNode*firstarc;
//指向第一条依附该顶点的弧
}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{
AdjListvertices;
intvexnum,arcnum;
intkind;//图的种类标志
}ALGraph;三、有向图的十字链表存储表示弧的结点结构顶点的结点结构typedefstruct{
VexNodexlist[MAX_VERTEX_NUM];
//顶点结点(表头向量)
intvexnum,arcnum;
//有向图的当前顶点数和弧数
}OLGraph;四、无向图的邻接多重表存储表示typedefstruct{//邻接多重表
VexBoxadjmulist[MAX_VERTEX_NUM];
intvexnum,edgenum;
}AMLGraph;7.3图的遍历从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。SG1从上页的图解可见:voidDFS(GraphG,intv){
//从顶点v出发，深度优先搜索遍历连通图G
visited[v]=TRUE;VisitFunc(v);
for(w=FirstAdjVex(G,v);
w!=0;w=NextAdjVex(G,v,w))
if(!visited[w])DFS(G,w);
//对v的尚未访问的邻接顶点w
//递归调用DFS
}//DFS首先将图中每个顶点的访问标志设为FALSE,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。voidDFSTraverse(GraphG,
Status(*Visit)(intv)){
//对图G作深度优先遍历。
VisitFunc=Visit;
for(v=0;v<G.vexnum;++v)
visited[v]=FALSE;//访问标志数组初始化
for(v=0;v<G.vexnum;++v)
if(!visited[v])DFS(G,v);
//对尚未访问的顶点调用DFS
}a二、广度优先搜索遍历图从图中的某个顶点V0出