第七章图
图的概念
图G是由顶点集V和边集E组成顶点集是有穷非空集边集是有穷集;
G中每条边都有方向称有向图;有向边称弧;边的始点称弧尾;边的终点称弧头;G中每条边都没有方向的称无向图
顶点n与边数e的关系无向图的边数e介于~n(n)/之间有n(n)/条边的称无向完全图;
有向图的边数e介于~n(n)之间有n(n)条边的称有向完全图;
无向图中顶点的度是关联与顶点的边数;有向图中顶点的度是入度与出度的和
所有图均满足所有顶点的度数和的一半为边数
图G(VE)如V是V的子集E是E的子集且E中关联的顶点均在V中则G(VE)是G的子图
在有向图中从顶点出发都有路径到达其它顶点的图称有根图;
在无向图中任意两个顶点都有路径连通称连通图;极大连通子图称连通分量;
在有向图中任意顺序两个顶点都有路径连通称强连通图;极大连通子图称强连通分量;
将图中每条边赋上权则称带权图为网络
图的存储结构
邻接矩阵表示法
邻接矩阵是表示顶点间相邻关系的矩阵n个顶点就是n阶方阵
无向图是对称矩阵;有向图行是出度列是入度
邻接表表示法
对图中所有顶点把与该顶点相邻接的顶点组成一个单链表称为邻接表adjvex|next如要保存顶点信息加入data;
对所有顶点设立头结点vertex|firstedge并顺序存储在一个向量中;vertex保存顶点信息firstedge保存邻接表头指针
邻接矩阵表示法与邻接表表示法的比较
) 邻接矩阵是唯一的邻接表不唯一;
) 存储稀疏图用邻接表存储稠密图用邻接矩阵;
) 求无向图顶点的度都容易求有向图顶点的度邻接矩阵较方便;
) 判断是否是图中的边邻接矩阵容易邻接表最坏时间为O(n);
) 求边数e邻接矩阵耗时为O(n^)与e无关邻接表的耗时为O(e+n);
图的遍历
图的深度优先遍历
图的深度优先遍历类似与树的前序遍历按访问顶点次序得到的序列称DFS序列
对邻接表表示的图深度遍历称DFS时间复杂度为O(n+e); 对邻接矩阵表示的图深度遍历称DFSM时间复杂度为O(n^);
图的广度优先遍历
图的广度优先遍历类似与树的层次遍历按访问顶点次序得到的序列称BFS序列
对邻接表表示的图广度遍历称BFS时间复杂度为O(n+e); 对邻接矩阵表示的图广度遍历称BFSM时间复杂度为O(n^);
生成树和最小生成树
将没有回路的连通图定义为树称自由树
生成树
连通图G的一个子图若是一棵包含G中所有顶点的树该子图称生成树
有DFS生成树和BFS生成树BFS生成树的高度最小
非连通图生成的是森林
最小生成树
将权最小的生成树称最小生成树(是无向图的算法)
普里姆算法
) 确定顶点S初始化候选边集T[~n];formvex|tovex|lenght
) 选权值最小的T[i]与第条记录交换;
) 从T[]中将tovex取出替换以下记录的fromvex计算权;若权小则替换否则不变;
) 选权值最小的T[i]与第条记录交换;
) 从T[]中将tovex取出替换以下记录的fromvex计算权;若权小则替换否则不变;
) 重复n次
初始化时间是O(n)选轻边的循环执行nk次调整轻边的循环执行nk;算法的时间复杂度为O(n^)适合于稠密图
克鲁斯卡尔算法
) 初始化确定顶点集和空边集;对原边集按权值递增顺序排序;
) 取第条边判断边的个顶点是不同的树加入空边集否则删除;
) 重复e次
对边的排序时间是O(eloge);初始化时间为O(n);执行时间是O(loge);算法的时间复杂度为O(eloge)适合于稀疏图
最短路径
路径的开始顶点称源点路径的最后一个顶点称终点;
单源最短路径问题已知有向带权图求从某个源点出发到其余各个顶点的最短路径;
单目标最短路径问题将图中每条边反向转换为单源最短路径问题;
单顶点对间最短路径问题以分别对不同顶点转换为单源最短路径问题;
所有顶点对间最短路径问题分别对图中不同顶点对转换为单源最短路径问题;
迪杰斯特拉算法
) 初始化顶点集S[i]路径权集D[i]前趋集P[i];
) 设置S[s]为真D[s]为;
) 选取D[i]最小的顶点加入顶点集;
) 计算非顶点集中顶点的路径权集;
) 重复)n次
算法的时间复杂度为O(n^)
拓扑排序
对一个有向无环图进行拓扑排序是将图中所有顶点排成一个线性序列满足弧尾在弧头之前这样的线性序列称拓扑序列
无前趋的顶点优先
总是选择入度为的结点输出并删除该顶点的所有边设置各个顶点入度时间是O(n+e)设置栈或队列的时间是O(n)算法时间复杂度为O(n+e)
无后继的顶点优先
总是选择出度为的结点输出并删除该顶点的所有边设置各个顶点出度时间是O(n+e)设置栈或队列的时间是O(n)算法时间复杂度为O(n+e)求得的是逆拓扑序列
附二:
第七章图
*************************************************************************************
图的逻辑结构特征就是其结点(顶点)的前趋和后继的个数都是没有限制的即任意两个结点之间之间都可能相关
图GraphG=(VE)V是顶点的有穷非空集合E是顶点偶对的有穷集
有向图Digraph每条边有方向;无向图Undigraph每条边没有方向
有向完全图具有n*(n)条边的有向图;无向完全图具有n*(n)/条边的无向图;
有根图有一个顶点有路径到达其它顶点的有向图;简单路径是经过顶点不同的路径;简单回路是开始和终端重合的简单路径;
网络是带权的图
*************************************************************************************
图的存储结构·邻接矩阵表示法用一个n阶方阵来表示图的结构是唯一的适合稠密图 ·无向图邻接矩阵是对称的
·有向图行是出度列是入度
建立邻接矩阵算法的时间是O(n+n^+e)其时间复杂度为O(n^)
·邻接表表示法用顶点表和邻接表构成不是唯一的适合稀疏图·顶点表结构 vertex | firstedge指针域存放邻接表头指针
·邻接表用头指针确定 ·无向图称边表;
·有向图又分出边表和逆邻接表;
·邻接表结点结构为 adjvex | next
时间复杂度为O(n+e)空间复杂度为O(n+e)
图的遍历 ·深度优先遍历借助于邻接矩阵的列使用栈保存已访问结点
·广度优先遍历借助于邻接矩阵的行使用队列保存已访问结点
*************************************************************************************
生成树的定义若从图的某个顶点出发可以系统地访问到图中所有顶点则遍历时经过的边和图的所有顶点所构成的子图称作该图的生成树
最小生成树图的生成树不唯一从不同的顶点出发可得到不同的生成树把权值最小的生成树称为最小生成树(MST)
构造最小生成树的算法 ·Prim算法的时间复杂度为O(n^)与边数无关适于稠密图
·Kruskal算法的时间复杂度为O(lge)主要取决于边数较适合于稀疏图
*************************************************************************************
最短路径的算法·Dijkstra算法时间复杂度为O(n^)·类似于prim算法
*************************************************************************************
拓扑排序是将有向无环图G中所有顶点排成一个线性序列若∈E(G)则在线性序列u在v之前这种线性序列称为拓扑序列
拓扑排序也有两种方法·无前趋的顶点优先每次输出一个无前趋的结点并删去此结点及其出边最后得到的序列即拓扑序列
·无后继的结点优先每次输出一个无后继的结点并删去此结点及其入边最后得到的序列是逆拓扑序列
