请问一下这道数据结构无向图的题目
最新回答
锁骨草莓印
2021-01-30 00:18:04
邻接矩阵的表示方法，如果图中两个顶点间有直接路径则矩阵相应位置为1或者路径权值，否则为0.可以用公式描述：
所以其邻接矩阵为：
深度优先搜索是指按照深度方向搜索 ，它类似于树的先根遍历。
深度优先算法的基本思想是：
若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述深度优先搜索过程，直至图中所有顶点均被访问过为止。
（1）访问出发点v0。
（2）依次以v0的未被访问的邻接点为出发点，深度优先搜索图，直至图中所有与v0有路径相通的顶点都被访问。
所以深度优先搜索的序列是：D B A C F G E
广度优先搜索是指按照广度方向搜索，它类似于树的按层次遍历。
广度优先搜索的基本思想是：
（1）从图中某个顶点v0出发，首先访问v0。
（2）依次访问v0的各个未被访问的邻接点。
（3）分别从这些邻接点（端结点）出发，依次访问它们的各个未被访问的邻接点（新的端结点）。
所以广度优先搜索的序列是：D B C E A F G
克鲁斯卡尔（Kruskal）算法基本思想:
假设N=(V,E)是一个具有n个顶点的连通网，
（1）将n个顶点看成n个集合；
（2）按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并；
（3）重复（2），直到所有的顶点都在同一个顶点集合内。
所以该题可以表示为：
热门标签
