Полная проверка графа

Question

Как я могу эффективно проверить полный граф (т. Е. Каждый узел подключен друг к другу)? Данный граф неориентирован и не взвешен.

Я использовал BFS, чтобы проверить, но это не эффективный способ для проверки всех узлов,

1 <= number of nodes <= 10^4 

Есть ли другой подход, который поможет мне в решении этой задачи? полная (неориентированный) графа

Answer 1

для n числа узлов, Есть n*(n-1)/2 края. так что вы можете легко проверить для полного графа

Answer 2

А, как известно, имеют точно V(V-1)/2 края, где V является число вершин.

Итак, вы можете просто проверить, что у вас ровно V(V-1)/2 ребер.

count = 0 
for-each edge in E 
    count++ 
if (count == V(V-1)/2) 
    return true 
else 
    return false 

Почему это правильно?
Если каждая вершина соединена со всеми другими вершинами, то каждая вершина имеет ровно V-1 ребер. Это V(V-1). Так почему мы делим на 2? Это связано с тем, что в нашем подсчете каждое ребро связано с другой вершиной, поэтому мы дважды подсчитывали каждое ребро. Наконец, мы получаем V(V-1)/2 краев.

Answer 3

Чтобы быть полным графом:

1. Числом ребер в графе должно быть N(N-1)/2
2. Каждого Vertice должны быть подключены к точно N-1 другим вершинам.

Время Сложность проверить второе условие: O(N^2)

использовать этот подход для второй проверки состояния:

for i in 1 to N-1 
for j in i+1 to N 
    if i is not connected to j 
    return FALSE 
return TRUE 

Answer 4

для п

1<=n<=10^4 

количество узлов, Есть

= n*(n-1)/2 

края. так что вы можете легко проверить полный график