是否存在更有效的算法来查找具有最大度数的节点（在图中）？

Question

问题:

给定一个图，在列表中找到度数最大且 return it/them 的节点。

我的解决方案：

def max_degree(graph):
        """
        :param graph: non-null and non-oriented networkx type graph to analyze.
        :return: list of nodes of this graph with maximum degree; 0 if the graph has no nodes; -1 if the graph is disconnected;
        """
        if len(graph.nodes) == 0:
            return 0
        if not nx.is_connected(graph):
            return -1
        # node_grade_list -> [(<node>, <grade>), ...]
        node_grade_list = sorted(grafo.degree, key=lambda x: x[1], reverse=True)
        max_grade = node_grade_list[0][1]
        max_grade_nodes_list = []
        for node in node_grade_list:
            if node[1] == max_grade:
                max_grade_nodes_list.append(node[0])
        return max_grade_nodes_list

有没有办法让它更有效率？

Answer 1

假设 graph.degree 是一个元组列表

[(<node>, <grade>), ...]

将获取最大节点数替换为

max_grade = max(graph.degree, key=lambda x: x[1])[1]
max_grade_nodes_list = [node[0] for node in graph.degree if node[1] == max_grade]

这更快，因为这是 O(n)，而排序需要 O(n*log(n))

修改后的代码

def max_degree(graph):
    """
    :param graph: non-null and non-oriented networkx type graph to analyze.
    :return: list of nodes of this graph with maximum degree; 0 if the graph has no nodes; -1 if the graph is disconnected;
    """
    if len(graph.nodes) == 0:
        return 0
    if not nx.is_connected(graph):
        return -1
    # graph.degree -> [(<node>, <grade>), ...]
    max_grade = max(graph.degree, key=lambda x: x[1])[1]

    return [node[0] for node in graph.degree if node[1] == max_grade]

为什么 Max 更快的解释

Time complexity is a concept in computer science that deals with the quantification of the amount of time taken by a set of code or algorithm to process or run as a function of the amount of input.

max 和 sorted 都是内置函数，因此都是本机编码的。

函数 max 在时间 O(n) 上是线性的，因为我们只需要遍历列表一次就可以找到最大值。这意味着当我们将列表的大小 n 加倍时，找到最大列表所需的时间也会加倍。

Python排序使用TimSort，平均时间复杂度为O(n*log(n))，其中n是输入列表的长度。

O(n*log(n)) 平均复杂度是许多排序算法的典型值，例如快速排序、归并排序等

将 O(n*log(n)) 与 O(n) 进行比较，我们发现 Max 的速度优势为：

O(n*log(n))/log(n)  = O(log(n)).

意味着对于 1024 个元素的列表，n = 2^10 它将快 log(2^10) = 10 倍

对于较小的列表，例如 n = 10，使用哪种方法并不重要。

是否存在更有效的算法来查找具有最大度数的节点（在图中）？

Does exists a more efficient algortihm of finding the node(s) (in a graph) with the maximum degree?

algorithm

graph

time-complexity

networkx