1、7.1图的结构定义和术语7.2图的存储结构7.2.1 数组表示法7.2.2 邻接表7.3图的遍历7.3.1 深度优先搜索7.3.2 广度优先搜索第七章 图1图 是由一个 顶点集 V 和一个 弧集（边集） E构成的数据结构。G = (V, E )其中， V(G)是 顶点的集合；E(G)是边的集合 1、 图的结构定义 :无向边（ vi,vj ）有向边 2由于 “ 弧 ” 是有方向的，因此称由顶点集和弧集构成的图为 有向图 。12 53 4例如 : G1 = (V1, E1)其中V1 (G1) =1, 2, 3, 4, 5E1 (G1) =, , , , 32 31 46 5由顶点集和边集构成的图称
2、作 无向图。例如 : G2=(V2,E2)V2 (G2) =1, 2, 3, 4, 5, 6E2 (G2) =(1,2), (1,5),(2,5), (2,6), (3,4),(3,6), (4,6) 42、名词和术语有向完全图 、 无向完全图邻接点、度、入度、出度路径、回路 、 简单路径连通图、连通分量、强连通图、强连通分量5假设图中有 n 个顶点， e 条边，则有向图： 0e n(n-1) 若 e=n(n-1) 称作 有向完全图 ;无向图： 0e n(n-1)/2 若 e=n(n-1)/2 称作 无向完全图 ;6若存在 ， 则称 vi邻接于 vj或 vj邻接到 vi ;1346 5例如 :
3、ID(2) = 3ID(1) = 2和顶点 v 相关的 边的数目 定义为 v的 度 。2若存在 (vi,vj )， 则称 vi,vj互为 邻接点。7顶点的 出度 : 以顶点v为弧尾的弧的数目 ;12 43 5对有向图来说 ，顶点的 入度 : 以顶点 v为弧头的弧的数目 。顶点的 度 (TD)=出度 (OD)+入度 (ID)例如 :ID(2) = 2OD(2) = 1TD(2) = 38设图 G中从 u 到 w的一个顶点序列则称从顶点 u 到顶点 w 之间的一条 路径 。起始与终止点相同，称为 回路 。如 :从 1到 6的一条路径为 1,5,2,6简单路径 :指序列中顶点不重复出现的路径，或只有起点和终点相同的路径。1346 52如： 1,2,5是 简单路径1,2,5,1是 回路 ，而且是 简单路径91 23例如 :1,2,3是 简单路径， 不是 回路。1,2,3,2,1是 回路 ，但不是 简单路径10
