Question

请问一下这道数据结构无向图的题目





Answer 1

1. 邻接矩阵的表示方法，如果图中两个顶点间有直接路径则矩阵相应位置为1或者路径权值，否则为0.可以用公式描述：

   

   所以其邻接矩阵为：

2. 

   深度优先搜索是指按照深度方向搜索 ，它类似于树的先根遍历。

   深度优先算法的基本思想是：

   若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述深度优先搜索过程，直至图中所有顶点均被访问过为止。 
   

   （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
   

3. 克鲁斯卡尔（Kruskal）算法基本思想:

   假设N=(V,E)是一个具有n个顶点的连通网，

   （1）将n个顶点看成n个集合；

   （2）按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并；

   （3）重复（2），直到所有的顶点都在同一个顶点集合内。  

   所以该题可以表示为：