重庆建工集团建设网站,优秀wordpress个人博客,上海网站建设服务是什么,上海高新企业名单查询图#xff08;Graph#xff09;是由定点的又穷非空集合和顶点之间边的集合组成#xff0c;通常表示为#xff1a;G#xff08;V,E#xff09;#xff0c;其中#xff0c;G表示一个图#xff0c;V是图G中顶点的集合#xff0c;E是图G中边的集合。
一、各种图的定义
…图Graph是由定点的又穷非空集合和顶点之间边的集合组成通常表示为GV,E其中G表示一个图V是图G中顶点的集合E是图G中边的集合。
一、各种图的定义
图按是否有方向分可分为有向图和无向图。有向边用尖括号“”表示无向边用小括号“”表示。 简单图无环无重复边。我们以下讨论的都是简单图。 无向完全图任意两个顶点之间都存在边。 含有n个顶点的无向完全图有n*n-1/2条边。 有向完全图任意两个顶点之间都存在方向互为相反的两条弧。 含有n个顶点的有向完全图有n*n-1条边。 网带权的图。 回路或环第一个顶点到最后一个顶点相同的路径称为回路或环。 简单路径序列中顶点不重复出现的路径。 简单回路或简单环除了第一个顶点和最后一个顶点之外其余顶点不重复出现的回路。 连通图任意两个顶点之间互通。 连通分量无向图中极大连通子图。要是子图、子图要是连通的、连通子图含有极大顶点数、具有极大定点数的连通子图包含依附于这些顶点的所有边
二、图的存储方式
一邻接矩阵 邻接矩阵是顶点和边的二维数组若顶点间存在边则标作1否则标作0。 横着的和是该顶点的度。 二邻接表 数组与链表相结合的存储方法。 但在有向图中一般只关注到出度问题逆连接表关注到的是入度的问题。 三十字链表 把邻接表和逆邻接表结合。 四邻接多重表
三、图的遍历
图的遍历指的是从图中某一顶点出发访遍图中其余顶点且使每一个顶点仅被访问一次。 一深度优先遍历 深度优先遍历Depth_First_SearchDFS顾名思义就是从一个顶点出发往最深里找。 广度优先遍历Breath_First_SearchBFS也就是从一个顶点出发一层层找。 它们的时间复杂度是一样的只是结点访问的顺序不一样。
四、最小生成树
最小生成树构造连通网的最小代价生成树。 普里姆算法从一个点出发找连通的。 克鲁斯卡尔算法先找最短的边。
五、最短路径
迪杰斯特拉算法从一个顶点出发逐渐找权最小的。 弗洛伊德算法 如果要求所有点到其他点的最短路径选弗洛伊德算法。
六、关键路径
一个个去掉度为0的顶点。
