今天刚上完算法课，课上知识内容包括拓扑排序和图论一些基本知识，所以我就去leetcode上面找了一道有关图论的题目来巩固自己所学的知识。
题目简介： For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
提炼内容： 从一个无向图中寻找一个根节点，使得该根节点生成的树拥有最小的高度。 显然，如果对每个节点使用DFS或者BFS去搜索该节点的树高度将会得到 O(V(V+E))的时间，这是一个十分慢的搜索过程。 因此，我试着换个角度来思考这个问题。如果一条根到叶子的路径上包含a,b,c,d,e,f,g七个点，那么当我们选取中间点d作为根时，d到所有节点的路径是最短的（相比b到g或者a到f）。也就是说，我们可以从图中逐个删除度为1的节点，那么当图中最后只剩一条边或者无边的时候，即可获得中间节点，也就是生成树高度最小的根节点。 第一次尝试： 不使用邻接表保存边，不使用列表保存度为1的叶子节点后所产生的新节点。测试结果，只通过62个测例，当节点数达到2020时，算法超时。
#找度为1的点，根据其边来减小点的度数，然后删除该点 #重复该步骤直至无点度数大于1 while 1: hasDegreeMoreThan1 = False oneDegreeNodeList = [] for i in range(n): if degree[i][1] == False: if degree[i][0] == 1: oneDegreeNodeList.append(i) #只剩一个点的情况 elif degree[i][0] == 0: return [i] else: hasDegreeMoreThan1 = True if hasDegreeMoreThan1: #如果有度数大于1的点，则根据入度为1的点的边减少相应点的度数 for i in range(len(oneDegreeNodeList)): for j in range(len(edges)): #访问完毕便删除度数等于1的点的边 if edges[j][0] == oneDegreeNodeList[i]: degree[edges[j][1]][0] -= 1 del edges[j] break elif edges[j][1] == oneDegreeNodeList[i]: degree[edges[j][0]][0] -= 1 del edges[j] break #标记度数为1的点已被删除 degree[oneDegreeNodeList[i]][1] = True else: return oneDegreeNodeList第二次尝试： 使用列表保存新叶子，当测例节点数达到5000时超时。
#重复该步骤直至无点度数大于1 while size - usedEdgeCounts > 1: #用来保存新的度数为1的点 newOneDegList = [] #如果有度数大于1的点，则根据入度为1的点的边减少相应点的度数 for i in range(len(oneDegreeNodeList)): for j in range(len(edges)): #访问完毕便删除度数等于1的点的边 if edges[j][0] == oneDegreeNodeList[i]: degree[edges[j][1]] -= 1 if degree[edges[j][1]] == 1: newOneDegList.append(edges[j][1]) #若有度数为0的点即可直接返回 elif degree[edges[j][1]] == 0: return [edges[j][1]] del edges[j] usedEdgeCounts += 1 break elif edges[j][1] == oneDegreeNodeList[i]: degree[edges[j][0]] -= 1 if degree[edges[j][0]] == 1: newOneDegList.append(edges[j][0]) elif degree[edges[j][0]] == 0: return [edges[j][0]] del edges[j] usedEdgeCounts += 1 break oneDegreeNodeList = newOneDegList return oneDegreeNodeList第三次尝试： 参考了leetcode上其他用户所使用的数据结构，改用邻接表保存边（而不是每次都遍历edges）且使用列表保存新叶子。AC
#度为1的点必为叶子节点，若以度为1的点作为根，则生成树高度最高 #算法思想：从图中逐个删除入度为1的点，直至只剩下入度为1的点即为高度最小的根。 class Solution(object): def findMinHeightTrees(self, n, edges): #无顶点则直接返回空 if n == 0: return [] #无边则返回各个定点 if edges == []: return [x for x in range(n)] #统计边个数并用邻接表将边存储起来 size = len(edges) adjList = [set() for _ in range(n)] for i, j in edges: adjList[i].add(j) adjList[j].add(i) leaves = [] for i in range(len(adjList)): if len(adjList[i]) == 1: leaves.append(i) while size > 1: newLeaves = [] for leaf in leaves: node = adjList[leaf].pop() adjList[node].remove(leaf) if len(adjList[node]) == 1: newLeaves.append(node) elif len(adjList[node]) == 0: return [node] size -= len(leaves) leaves = newLeaves return leaves至此，该题代码编写完毕。累。。。
