例 路径:1,2,3,5,6,3 路径长度:5 /单路径:1,2,3,5 回路:1,2,3,5,6,3,1 简单回路:3,5,6,3 例 路径:1,2,5,7,6,5,2,3 路径长度:7 简单路径:1,2,5,7,6 回路:1,2,5,7,6,5,2,1 简单回路:1,2,3,1
16
例 ②④⑤ 连通图 6 例⑤ 强连通图 ③ 例 非连通图 连通分量 6
17
基操 结神的建和锦 对顶点的访问绿你 人或顶点 点的操作 遍历 CreatGraph(8GR:l按定义NMwR构造图 Destroy Graph(8G:∥销毁图 Locate vex(Gl若G中存在顶u则返回该顶点在图中位置;否则返回其它信息。 GetVex(G,v}J返回v的值。 Putvex(&G,wva|ue;对倔值vaue FirstAdjVex (G,V回的第一个邻接点。若该顶点在G中没有邻接点则返回空”。 NextAdjVex(G,ww;回v的相对于训的下一个邻接点。若是最后一个则返回“空。 InsertVex(&Gv;∥在图G中增添新顶点v Deletevex(&G删除G中顶点及其相关的弧。 InsertArc(&Gw;在G中增添弧<W,若G是无向的则还增添对称弧Wv。 DeleteArci&G,w;在G中删除弧w,著G是无向的则还删除对称弧≮w,。 DFSTraverse(G,s0);以从顶点v深度优先遍历图G并对每个顶点调用s一次。 BFSTraverse(G,vsO);从顶点v广度忧先遍历图G并对每个顶点调用Ⅵ一次
18
7國的能结 图的特点:非线性结构(m:n) 顺序存储结构:无!(多个顶点,无序可言) 但可用数组描述元素间关系。 链式存储结构:可用多重链表 设计为邻接矩 邻接表 邻接多重表 十字链表 重点介绍:邻接矩阵(数组)表示法 邻接表(键式)表示法
19 7.2 图的存储结构
、Q激组)爱录 建立一个顶点表(记录各个顶点信息)和一个邻接矩阵(表示 各个顶点之间关系) 设图A=(V,E)有m个顶点,则图的邻接矩阵是一个二维数组 A Edgelnlln,定义为: ∫1,如果<ij>∈E或者()∈E A.Edge[iIj=10,否则 例 ABo101,0)J 顶点表:(v1v23V4V 邻接矩阵:「01010y 01011 10101 01110Jv 分析1:无向图的邻接矩阵是对称的; 分析2:顶点的度=第i行(列)中1的个数; 特别:完全图的邻接矩阵中,对角元素为0,其余全1
20