数据结构－图.pptVIP

第七章　 图 7.1 图的定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集(没有空图) E(G)是边的有限集合，边是顶点的无序对或有序对 p156 ADT 有向完全图——n个顶点的有向图最大边数是n(n-1) 无向完全图——n个顶点的无向图最大边数是n(n-1)/2 权——与图的边或弧相关的数叫~ 网——带权的图叫~ 子图——如果图G(V,E)和图G‘(V’,E‘),满足： V’?V E’?E 则称G‘为G的子图 顶点的度 无向图中，顶点的度为与每个顶点相连的边数 有向图中，顶点的度分成入度与出度 入度：以该顶点为头的弧的数目 出度：以该顶点为尾的弧的数目 路径——路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)?E 或 Vij-1,Vij?E,(1j?n) 路径长度——沿路径边的数目或沿路径各边权值之和 回路——第一个顶点和最后一个顶点相同的路径叫~ 简单路径——序列中顶点不重复出现的路径叫~ 简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫~ 连通——从顶点V到顶点W有一条路径，则说V和W是连通的 连通图——图中任意两个顶点都是连通的叫~ 连通分量——非连通图的每一个连通部分叫~ 强连通图——有向图中，如果对每一对Vi,Vj?V, Vi?Vj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是~ 有很少条边或弧（如 en log n）的图称为稀疏图(Sparse graph) 反之称为稠密图(Dense graph) 一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的 n-1 条边。 　　　注：一棵有n个顶点的生成树有且仅有n-1 条边。如果一个图有 n 个顶点和小于n-1 条边，则是非连通图。如果它多于n-1 条边，则一定有环。但是有n-1条边的图不一定是生成树。 如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。 邻接矩阵——表示顶点间相联关系的矩阵 定义：设G=(V,E)是有n?1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵 特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n2 无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和 有向图中， 顶点Vi的出度是A中第i行元素之和 顶点Vi的入度是A中第i列元素之和 网络的邻接矩阵可定义为： # define INFINITY INT_MAX // 最大值 # define MAX_VERTEX_NUM 20 // 最大顶点个数 typedef enum {DG, DN, UDG, UDN} GraphKind; typedef struct ArcCell { VRType adj; //对无权图,用0或1表示相邻否;对带权图,则为权值类型 InfoType *info; // 该弧相关信息的指针 } ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum, arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 } MGraph; 构造无向网G的算法： Status CreateUDN( MGraph G){ // 采用数组（邻接矩阵）表示法，构造无向网G。 scanf( G.vexnum, G.arcnum, IncInfo); for(i = 0;iG.vexnum; ++i) scanf(G.vexs[i]); //构造顶点向量 for(i = 0;iG.vexnum; ++i) //初始化邻接矩阵 for(j=0; jG.vexnum; ++j) G.arcs[i][j]={INFINITY, NULL}; for(k=0; kG.arcn