[graphe]: construire un graphe de relation

Selon les livres que j'ai lus, ils construisent souvent un graphe en utilisant des sommets dont la valeur va de 1 à n, donc chaque sommet a un nom unique.[graphe]: construire un graphe de relation

si je dois construire un graphique en utilisant des sommets dont la valeur sont des chaînes, dites

V = {'Arm', 'Bob', 'Lin', 'Kok'} #vertices 
E = {('Arm', 'Lin'), (Bob, 'Lin'), ('Bob', 'Kok')} #edges

Suis-je censé carte ces sommets de chaîne en entiers avant de construire le graphe pour eux? Un exemple auquel je peux me référer?

Source

2011-09-12 Alcott

Je ne vois aucune raison de les mapper aux numéros. Je ne suis pas sûr du logiciel que vous utilisez, mais si vous dessinez avec pygraphviz vous pouvez utiliser des noms très bien. – Owen

@Owen, en fait j'essaie d'implémenter des algorithmes de graphes tels que DFS et BFS, la façon dont j'ai appris des livres est de marquer chaque sommet découvert gris ou noir, et chaque vertex est assigné un nombre de 1 à n, donc leur la couleur peut simplement être représentée par une couleur de tableau [i], mais si le sommet est une chaîne, comment puis-je faire le travail de coloration? j'ai donc pensé que je devrais mapper chaque sommet de corde en un nombre i compris entre 1 et n. Ai-je raison? – Alcott

Vous pourriez le faire. Vous pouvez également stocker les couleurs dans les nœuds eux-mêmes (en faire des objets), ou conserver les couleurs dans un dict et utiliser 'color [nom]' pour obtenir la couleur. – Owen

Je vais sortir sur un membre et suppose que vous dessinez avec pygraphviz

En utilisant des chaînes au lieu de chiffres, le simple.py exemple ressemblerait à ceci:

import pygraphviz as pgv 

A=pgv.AGraph() 

A.add_edge('foo', 'bar') 
A.add_edge('bar', 'baz') 
A.add_edge('baz', 'foo') 

A.write('simple.dot') 

B=pgv.AGraph('simple.dot') 
B.layout() 
B.draw('simple.png')

Ou, si vous ne pas dessiner, juste construire, le code que vous avez posté est un excellent moyen de représenter un graphique; pas besoin d'utiliser des chiffres lorsque les chaînes fonctionnent très bien.

Source

2011-09-12 00:46:53 Owen

[graphe]: construire un graphe de relation

Répondre

Questions connexes