1、n 图图n 图的存储表示图的存储表示n 图的遍历图的遍历n 无向图的连通分量和生成树无向图的连通分量和生成树n 最短路径最短路径 n 拓扑排序拓扑排序一、图图 应用最广泛的数据结构。不同于树的另一种 非线性结构每个顶点可以与 多个 其他顶点相关联，各顶 点之间的关系是 任意 的。简单图 没有自身环，两点间至多一条边 v5v1 v1v3v2 v3v4 v4v2无向图 有向图图的基本概念G= V=v1,v2,vn 顶点 集E= (vi, vj) | vi,vj V, vivj 边 集 无向图E=|vi , vj V有向边 集 有向图有向边 ， vi起点 弧尾 ， vj终点 弧头 TD(vi): 一
2、个顶点的 度 ,以 vi为端点的边的数目。OD(vi): 出度 , 以 vi为起点的边的数目。ID(vi): 入度 ，以 vi为终点的边的数目。TD(vi)= OD(vi)+ ID(vi)OD=ID, TD=2|E|， |E| =1/2*TD TD OD ID 为整个图的总度 ,出度 ,入度数 。图的基本概念路径 vivj, 以 vi为起点 vj为终点的顶点序列。路径的长 路径上边的数目，简单路径 顶点都不重复的路径，回路 环 首尾相接的路径，简单回路 除第一个和最后一个顶点以外都不重复的路径，vivj连通 有路径 vivj，连通图 任意两点都连通，有向图 vivj强连通 vivj连通 vjv
3、i也连通，强连通图 任意两点都强连通。v5v1v3v2v4v5v1v3v2v4弱连通 强连通强连通分量：彼此强连通的顶点的子集ACBDIEGFHABCDEFGHI完全图 任意两点间都有边相关联的图。无向完全图 共有边 1/2(n*(n-1) 条 ,有向完全图 共有边 n(n-1) 条。稀疏图 |E|nlog n稠密图 |E|nlog n带权边 具有边长的边有权图 图的所有边都是带权边。网络 有权图子图G=(V, E), G=(V, E)如果 V V, E E ,就称 G是 G的子图。 连通分量 一个图的极大连通子图。强连通分量 一个图的极大强连通子图。连通图的 生成树 含有所有顶点的极小 连通图 n个顶点尽可能少边的连通图有 n-1条边。非连通图的 生成森林： 所有 k个连通分支的生成树组成生成森林，共有 n-k条边。有向树有向图连通图恰有一个顶点的入度为 0，其余顶点的入度都是 1。有向图的 生成森林：有向图的一个子图，含有所有顶点，构成若干互不相交的有向树，叫做生成森林。二、图的存储结构1.邻接矩阵用矩阵表示图的顶点之间的相邻关系。Ai,j=1 (vi,vj) E=0 o.w.v5v1v3v2v40 1 1 0 01 0 0 1 11 0 0 0 10 1 0 0 00 1 1 0 0
