Étant donné le graphique, comment pourrais-je le représenter en utilisant adj matrix ?. J'ai lu beaucoup de tutoriels, post, diapositives, etc, mais je ne peux pas obtenir ma tête autour de lui, j'ai juste besoin de cette petite poussée.Représentation graphique
alt text http://i39.tinypic.com/10xu4hv.png
Chaque combinaison de lettres numéro est un noeud dans votre graphique, à savoir, à partir A0, A1, A2, ... à F5, F6, F7. Votre graphe comporte 48 nœuds (8 colonnes multipliées par 6 dans votre labyrinthe), vous aurez donc besoin d'une matrice 48x48. Si vous le traitez comme un booléen, vous définissez tous les champs sur false sauf ceux où il existe une connexion entre deux nœuds, par ex. A0 à A1 signifierait que la ligne A0 a une valeur vraie dans la colonne A1, et vice versa (parce que votre graphique n'est pas dirigé).
Voilà ma tentative pour la première ligne horizontale du labyrinthe:
A0 A1 A2 A3 A4 A5 A6 A7
A0 0 1 0 0 0 0 0 0
A1 1 0 0 0 0 0 0 0
A2 0 0 0 1 0 0 0 0
A3 0 0 1 0 0 0 0 0
A4 0 0 0 0 0 1 0 0
A5 0 0 0 0 1 0 0 0
A6 0 0 0 0 0 0 0 0
A7 0 0 0 0 0 0 0 0
vous pouvez donc voir de ce que vous allez finir par une matrice symétrique en raison de la nature non orienté de vos bords et que son va être peu peuplé.
EDIT: Matrice vs listes
L'entrée wikipedia pour adjacency list a quelques bons points sur les avantages algorithmiques de chacun.
EDIT:
merci pour votre effort mon pote. J'étais confus parce que la façon dont je le faisais n'était pas symétrique, j'étais donc sûr que c'était faux. Mais quand j'ai pensé à l'idée A1 .... F7 je ne pouvais tout simplement pas le croire. Comme je l'ai demandé à Robert; que pensez-vous sera mieux dans cette matrice de cas ou de la liste d'adjacence? – Carlos
En raison de la nature de votre graphique, faible degré et non orienté, j'aurais pensé qu'une liste de bord serait un bon pari. Les algorithmes que vous voulez appliquer à la structure de données devraient également influencer votre décision. –
hey mon pote désolé par erreur j'ai voté vers le bas il ne me laisse pas annuler le vote pour une raison quelconque parce que édité, pouvez-vous éditer quelque chose dans votre poste de cette façon je peux vous rendre le rep/vote. Merci et désolé. – Carlos
Une autre façon serait d'avoir 2 boolean matrices nommées Hor et Ver pour suivre la possibilité de déplacement horizontal et vertical, respectivement.
Hor Matrix: Dimension: 6x9
[X,YZ] représente la possibilité d'un mouvement horizontal [X,Y]-[X,Z] sur la carte réelle.
-1 représente la limite
exemple: [A,01] est true et est donc [F,-10]. Mais [B,23] est false.
-10 01 12 23 34 45 56 67 7-1
A
B
C
D
E
F
De même
Ver Matrix: Dimension: 7x8
[XY,Z] représente la possibilité d'un mouvement vertical de [X,Z] à [Y,Z] sur le bord réel.
Capital o dans la ligne représentent la limite.
exemple: [DE,0] est true et [BC,7]. Mais [CD,0] est false.
0 1 2 3 4 5 6 7
OA
AB
BC
CD
DE
EF
FO
Ok, merci beaucoup. Pensez-vous qu'il vaudra mieux utiliser la liste d'adjacence dans ce cas. Cuz 48x48 semble un peu redondant (image miroir) et inefficace. – Carlos
Et cette matrice, par sa nature, est symétrique, de sorte que toute manipulation (et stockage, bien sûr) peut être effectuée sur l'une des moitiés seulement. – ysap
Le degré de chaque sommet est d'au plus 4, donc la liste d'adjacence serait beaucoup plus efficace. – polygenelubricants