数据结构（陈仲民）CH7.PPTVIP

第七章 图 7.1 图的定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对 有向图——有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为v,w，v,w是顶点，v为弧尾，w为弧头 无向图——无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v) 有向完备图——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是~ 7.2 图的存储结构 多重链表 邻接矩阵——表示顶点间相联关系的矩阵 定义：设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列元素之和 网络的邻接矩阵可定义为： 特点 关联矩阵每列只有两个非零元素，是稀疏矩阵；n越大，零元素比率越大 无向图中顶点Vi的度TD(Vi)是关联矩阵A中第i行元素之和 有向图中， 顶点Vi的出度是A中第i行中“1”的个数 顶点Vi的入度是A中第i行中“-1”的个数 邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧） 特点 无向图中顶点Vi的度为第i个单链表中的结点数 有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表 有向图的十字链表表示法 7.3 图的遍历 深度优先遍历(DFS) 方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止 算法7.2 Void DFS(int i) { visit(i); visited[i]=1; P=adjlist[i]; 链表头指针 While (p!=NULL) { j=p-vertex; 初始状态是第一个边或第一条弧 if (visited[j]==0) DFS(j); p=p-next; } } 算法7.4 Void BFS(int i) { front=0, rear=0; visit(i); visited[i]=1; Enqueue(q,i); /*顶点i 入队*/ do { v=Dequeue(q); /*从队列中取出一个顶点*/ p=adjlist[v]; while(p!=NULL) /*访问的所有顶点*/ { if (visited[p-vertex]==0) { j=p-vertex; visited[j]=1; visit(j);