第14章 图
(度为偶数的画环,度为奇数的画环之后,剩下的两两配对连线)
点连通度小于等于边连通度小于等于最小度
其实很简单,沿着边轮流标号1,2,1,2,1,2…,最后每条边两个端点序号不一样的就是二部图。
第15章 欧拉图与哈密顿图
就一个思想,能不走桥就不走桥
讲人话就是,每走一步都是找到最短的路径,并且每走一步都实时更新所有距离,保证每次都选择最短路径。
(dijkstra的算法思想
是从以上最短距离数组中每次选择一个最近的点,将其作为下一个点,然后重新计算从起始点经过该点到其他所有点的距离,更新最短距离数据。已经选取过的点就是确定了最短路径的点,不再参与下一次计算。)
第16章 树
(注意,生成树要包含原图中的所有顶点)
上面第二个图中4应该是实线