密云城市建设官方网站,网上政务服务平台入口,网站数据分析案例,wordpress 影楼主题文章目录1.图的分类1.1.强连通图1.2.完全图2.存储结构2.1.邻接矩阵表示法#xff1a;2.2.邻接链表表示法#xff1a;3.图的遍历3.1.深度优先遍历3.2.广度优先遍历4.最小生成树4.1.普里姆算法#xff1a;4.2.克鲁斯卡尔算法#xff1a;5.AVO网络、AOE网络1.图的分类
1.1.强…
文章目录1.图的分类1.1.强连通图1.2.完全图2.存储结构2.1.邻接矩阵表示法2.2.邻接链表表示法3.图的遍历3.1.深度优先遍历3.2.广度优先遍历4.最小生成树4.1.普里姆算法4.2.克鲁斯卡尔算法5.AVO网络、AOE网络1.图的分类
1.1.强连通图
任意两顶点间都是联通的存在路径
1.2.完全图
任意两个顶点都有边
2.存储结构
对于图G有m个边n个节点
2.1.邻接矩阵表示法
对于图G二维数组A[i][j],如果边vivj存在路径则A[i][j] 1否则A[i][j] 0 深度优先遍历时需要遍历邻接矩阵的n×n个点所以时间复杂度为(O(n2))
2.2.邻接链表表示法
为图的每个顶点建立一个单链表第i个节点表示依附于顶点Vi的边弧 深度优先遍历时依次访问每一个节点然后依次访问当前节点的每条边把这些边的终点节点的入度1,所以每个节点每条边都需要访问一边所以时间复杂度为(O(mn))
3.图的遍历
3.1.深度优先遍历
首先访问顶点然后访问当前节点邻接且未被访问过的节点 无符合的则回溯到一个尚有邻接节点且未被访问的节点重复第一步
3.2.广度优先遍历
首先访问顶点v然后依次访问当前v的各个未被访问的邻接点然后分别冲这些邻接点访问他们的邻接点
4.最小生成树
图的生成树 图的最小生成树各边的权值总和最小的生成树
4.1.普里姆算法
On2,与边数无关适合边密集的图 选一条最小权值的边不断选择与已选择边邻接且权值最小的边加入集合直至集合包含所有的顶点贪心法
4.2.克鲁斯卡尔算法
Onlogn与顶点无关适合边稀疏的图 在不形成回路的前提下不断寻找权值最小的边尝试构成最小生成树回溯法
5.AVO网络、AOE网络
AVO网络一个项目的的实施过程有很多活动这些活动的进行有先后顺序那么这些挥动的先后关系可以用一个有向图表示顶点代表活动、有向边表示活动间的先后关系 拓扑排序AOV网络的拓扑排序可能有多个只要满足对于AVO网络中的每条弧ij拓扑排序中i都在j的前面 AOE网络带权值的AVO网络边代表活动、边上的权值代表活动需要的时间、顶点代表活动结束的事件 AOE网络的关键路径完成项目需要的最少时间也就是AOE网络中从开始顶点到结束顶点的最长带权路径的权值和 求图的 拓扑排序 及关键路径长度
