网页设计与网站开发第三版课后答案,怎么做网站的二维码,应用商店最新版本,江门建站公司数据结构 图 3月11日 – 天气#xff1a;晴 晚上无线网络突然不能用了#xff0c;花费好久弄这个#xff0c;耽误了一些时间 1. 图的定义 这里需要注意完全图的定义#xff0c;以及完全图的边数 这里需要注意连通图和连通分量的概念。 2. 图的存储结构
图有两种存储结构晴 晚上无线网络突然不能用了花费好久弄这个耽误了一些时间 1. 图的定义 这里需要注意完全图的定义以及完全图的边数 这里需要注意连通图和连通分量的概念。 2. 图的存储结构
图有两种存储结构分别是邻接矩阵和邻接表。 对于有向图来说邻接矩阵中每一行1的个数代表了该节点的出度。每一列中1的个数代表了该节点的入度。 对于无向图来说每一行或每一列1的个数代表了节点的度。 从图中可以看出来邻接矩阵的存储方式只和节点的个数有关 邻接表的存储方式的特点是链表中的每一个节点代表图中的一条边。链表中节点的个数等于边的个数。 对于无向图来说链表中的节点必然是偶数个。 3. 图的遍历方式 这里需要重点记住遍历不同存储方式的图的时间复杂度 4. 图的最小生成树 计算最小生成树的两种算法 Prim算法每次选择一条权值最小的边并选择出顶点然后从已经生成的部分中选择一条最小的边与已经生成的部分连接直到所有的顶点都相连。时间负责度为n^2 它只和顶点的个数有关因此适用于稠密图顶点多边少 Kruskal算法每一次都选择图中最小的一条边直到所有的顶点都被连接。 它只和边的个数有关因此适用于稀疏图。 5. 拓扑排序 每次选择入度为0的节点删除节点和与之相连边直到不存在入度为0的顶点 注意拓扑排序的顺序不一定唯一 6. 关键路径 关键路径可能不唯一 关于最早最晚开始时间以及松弛时间的计算问题 https://blog.csdn.net/zhangt2333/article/details/107029298 7. 最短路径 无需掌握这两种算法具体怎么计算的考试的时候直接看图就可以找到两个顶点之间的最短路径
