J'ai un graphique de cette structure:
def add_disconnected_nodes(Graph, begin):
if begin not in Graph:
return False
beg = {}
bbg = []
for vet in Graph.keys():
bbg.append(vet)
bba = []
while len(bbg) != 0:
for ls in bbg:
if ls != begin and ls not in Graph[begin]:
bba.append(ls)
bbg.remove(ls)
if len(bbg) == 0:
break
beg[begin] = Graph[begin] + bba
Graph.update(beg)
return Graph
3 Réponses :
Le moyen le plus simple de créer un graphique simple connecté est de connecter un nœud à tous les autres nœuds du graphique: ici, nous n'avons pas utilisé Dfs ou bfs. Le code est si simple mais le nombre de bords ajoutés n'est pas minimum.
Ce code ne peut être utilisé que dans des graphiques simples (car la définition de la connectivité est différente pour les graphiques dirigés). La complexité temporelle de cet algorithme est O (| V | + | e |) ou O (n + m).
Si vous utilisez dfs ou bfs, la complexité temporelle serait la même.
Vous avez dit qu'il comporte 6378 nœuds et 39932 bords. Traitement de tous les nœuds et bords une fois, ne prendra pas beaucoup de temps.
Voulez-vous dire ne prendrez-vous pas beaucoup de temps, ou cela prendra beaucoup de temps?
Je voulais dire que cet algorithme est assez rapide.
J'ai pu éventuellement le casser. Cela fonctionne pour des graphiques simples et des structures de graphique plus grandes. J'apprécie ceux qui ont contribué à cette question et surtout à @julien qui m'a fait croire! Voici mon code ci-dessous:
from collections import defaultdict as dd
def add_disconnected_nodes(Graph, begin):
if begin not in Graph:
return False
temp_dict = dd()
init_node_list = []
temp_node_list = []
for vertices in Graph.keys():
init_node_list.append(vertices)
if init_node_list:
for node_items in init_node_list:
if node_items != begin and not node_items in Graph[begin]:
temp_node_list.append(node_items)
temp_dict[begin] = Graph[begin] + temp_node_list
init_node_list.remove(node_items)
Graph.update(temp_dict)
return Graph
Si vous voulez le faire sous forme optimisée, utilisez des composants fortement connectés ( algorithème de Kosaraju a>) et découvrez les composants les plus connectés et ajoutez vos nœuds faiblement connectés pour créer un graphique entièrement connecté. échantillon de code pour démontrer: p> Disons J'ai au total 18 nœuds et certaines connexions initiales: p> mon entrée initiale ont des connexions comme: p> après avoir exécuté L'algorithme ci-dessus Le composant fortement connecté que j'ai obtenu est le suivant: p> par hasard si je ajoute des connexions ci-dessous. mon graphique devient complètement connecté: p> exécutant à nouveau sur les composants ci-dessus fortement connectés Algo La sortie finale est la suivante: P> Following are strongly connected components in given graph
0
12
4
14
11
5
9
7
8
6
13
10
3
2
16
17
1
15
*****
Trouvez les composants déconnectés et connectez-les?
Quelque part dans la façon dont poser les questions, la documentation dit que vous devez réellement montrer votre code, l'approche que vous prenez déjà pour le problème, sinon, cela peut sembler que vous demandez à quelqu'un de faire vos devoirs. C'est probablement pourquoi vous voyez des commentaires négatifs dans votre question. Veuillez le mettre à jour avec votre solution actuelle
@Banishedbot C'est un graphique dirigé
@Julien il y a mon mal de tête en fait. Je n'ai pas ajouté que je suis un peu nouveau aux graphiques; Donc, je trouve qu'il est difficile de travailler sur certains de ces concepts
La seule façon de ne plus être nouvelle à un sujet est de lire des tutoriels, des choses à Google et d'essayer vous-même. Trouver des composants connectés est un problème de théorie de base graphique qui a déjà été couvert de milliers de fois. Faites votre peu de recherche et de travail alors, si vous avez toujours des problèmes, montrez le code que vous avez essayé.
@vic Le problème est ambigu, vous pouvez connecter le graphique en connectant chaque paire de sommets dans O (N ^ 2). Si vous ne le souhaitez pas, vous devez spécifier ce que vous considérez comme un graphique dirigé, c'est-à-dire faiblement ou fortement connecté.
@Julien je pourrais facilement utiliser NetworkX.Connected_components (g) pour générer les composants connectés. Bien que je puisse voir les composants déconnectés, je joinçais ces quelques composants déconnectés à la majeure partie des composants connectés à peupler le temps trop complexe est en réalité le défi
@Banishedbot par dirigé, je veux dire que l'on pourrait trouver un chemin de nœud 1 au noeud 100, par exemple, mais il n'y a pas de chemin du nœud 100 au nœud 1. La majeure partie des nœuds est bien connectée, avec quelques composants (avec peut-être 2 ou 3 nœuds) séparés à part. L'objectif est en fait de connecter ces petits composants disjoints avec la majeure partie des nœuds fortement connectés. J'espère que mon explication est assez claire s'il vous plaît? Si je savais comment télécharger la photo du graphique résultant, j'aurais pu faire ça
@Julien Pouvez-vous faire des suggestions?