Partie 2 Partie 3 Partie 4 J'ai été invité à écrire cet article par une tâche nuisible de la quête Java Multithreading, qui, non sans quelques taquineries de la part des développeurs, a été appelée par eux une « tâche StringBuilder ». L'essence de sa condition était qu'un ensemble de mots (dans la condition, les noms des villes sont donnés, ce qui rappelle un jeu de mots pour enfants) devait être disposé selon le principe des dominos, la dernière lettre du mot n' devait être égal à la première lettre du mot (n+1) go, et on savait que tous les mots donnés (individuellement) étaient additionnés dans une telle chaîne. S'il était possible de composer plusieurs options pour la chaîne de mots souhaitée, n'importe laquelle était acceptée comme solution. Malgré l'apparente simplicité et clarté de la condition, résoudre le problème était loin d'être facile, et l'utilisation magistrale de StringBuilder n'a pas sauvé la situation. Les développeurs du problème se sont avérés être des isomorphes ordonnés de la planète Linear Chaos, qui ont plus d'une fois terrifié les cadets de JavaRush. Comme prévu, les solutions superficielles ne convenaient pas au validateur, car il y avait toujours des chaînes qui obligeaient l'algorithme naïf à sauter des mots. Il a fallu empiler des « béquilles » supplémentaires qui, tout en compliquant le problème, ne rapprochaient pas la solution dans le cas général et renforçaient de plus en plus le sentiment qu'une condition simple devait avoir une solution tout aussi simple. J’ai dû changer de tactique et me plonger un peu dans des domaines plus fondamentaux. Permettez-moi tout de suite de faire une réserve : en aucun cas je ne me considère comme un expert en théorie des graphes ; les sujets que j'aborderai ne dépassent quasiment pas le cadre de la résolution du problème des mots dominos, à l'exception peut-être seulement de quelques digressions d'ordre théorique. Donc des graphiques. Qu'est-ce qu'un graphe : c'est une collection (ensemble, ensemble, liste - peu importe) de sommets connectés les uns aux autres . Les connexions sont généralement appelées arêtes , les sommets sont également appelés nœuds ou nœuds. Ceci est un graphe : Ceci est aussi un graphe : Si l'on peut dire d'une arête qu'elle a une direction, alors le graphe est dit orienté : Les graphes des deux premières images ne sont pas orientés. On peut dire d'eux que l'arête (u, v) est identique à l'arête (v, u), c'est-à-dire par exemple que les arêtes (0, 4) et (4, 0) sont la même arête. Les flèches sur les bords d'un graphe orienté signifient que le bord (u, v) est un chemin allant du sommet u au sommet v et que le bord (v, u) n'existe pas. Sur la troisième image, il y a un bord (E, A). Il n'y a pas de bord (A, E). Regardons de plus près le dernier dessin. Vous pouvez remarquer que le sommet F n’a aucune arête, c’est tout à fait possible. Nous notons également qu'une arête est apparue près du sommet A - une boucle, et entre les sommets B et D il y a deux arêtes dirigées différemment. Les graphes orientés autorisent de tels artefacts. Disons que le graphique décrit un groupe de connaissances qui s'offrent des cadeaux. On voit que le gourmand F n'a rien donné à personne, B et D ont échangé des cadeaux (sauf que chacun d'eux a fait un cadeau à quelqu'un d'autre), et A s'est fait un cadeau, probablement à l'occasion de la résolution réussie d'un problème. problème de la planète Linear Chaos. À propos, notez que les sommets du graphe ne doivent pas nécessairement être des nombres ou contenir des nombres ; ce sont plutôt des conteneurs, c'est-à-dire ils peuvent stocker n'importe quel objet. Un graphique est une description des connexions. Un terme important qui nous sera utile plus tard - le nombre d'arêtes attachées à un sommet (ou, comme on dit aussi, incidentes à celui-ci) est appelé le degré d'un sommet donné. Par exemple, dans la première image, le sommet 0 a le degré 2, 1 a le degré 4, 3 a le degré 3, le sommet 0 de la deuxième figure a le degré 1. Dans cet article, nous n'entrerons pas dans la variété des différents types de graphiques, on mentionnera seulement qu'il existe aussi des graphiques pondérés, ceux-là. ceux dans lesquels un certain numéro est attaché à chaque bord, qui indique le « prix » de son passage. Les graphes connectés ont un certain nombre de sous-types, qui se distinguent par leurs propriétés. Par exemple, les graphiques dont les bords ne forment aucun cycle nulle part sont appelés arbres (ils ont des familles intéressantes avec des noms impressionnants comme « arbres rouge-noir », par exemple) et sont largement utilisés dans une variété d’algorithmes et de structures de données importants. Utiliser un graphique pour résoudre un problème Tout cela est très intéressant, dites-vous, mais qu'est-ce que tout cela a à voir avec la construction d'une chaîne de mots ? Il s'avère que la chose la plus directe est. Regardons notre exemple de test à partir de la condition : { Amsterdam Melbourne New York Kiev Vienne }. Écrivons dans n'importe quel ordre les lettres "nodales" auxquelles s'accrochent les mots : {A, M, N, K, B} et connectons-les avec des mots. Comme nous pouvons le voir, nous avons un graphe orienté dans lequel les nœuds sont des lettres et les bords sont des mots qui les relient. Si nous trouvons un moyen de parcourir toutes les arêtes de sommet en sommet afin de visiter chaque arête une seule fois, notre problème sera résolu. Essayons de répartir les nœuds du diagramme un peu différemment : Nous pouvons maintenant mieux voir que notre graphique est une boucle fermée. Nous pouvons commencer la séquence avec n’importe quel mot, et ce sera la bonne décision. Cependant, l’état du problème nous indique qu’une seule solution suffira. Remplaçons Vena par Vladimir : Nous voyons deux conséquences : d'une part, nous avons dû ajouter un nouveau sommet, la lettre P, et d'autre part, nous voyons qu'il n'est plus possible de boucler notre graphe. Résumons tout ce qui précède et introduisons deux nouveaux termes : 1. Un graphe connexe dont les arêtes peuvent être parcourues en visitant chacune d'entre elles une seule fois est appelé un graphe contenant un « chemin eulérien » . Une caractéristique d'un tel graphe (à l'exception de l'absence de sommets sans arêtes) est le degré pair de tous les sommets sauf deux (et seulement deux). 2. S'il s'avère possible de revenir au nœud d'origine, on dit qu'il y a un « cycle eulérien » dans le graphe . Une caractéristique d'un tel graphe (à l'exception de l'absence de sommets sans arêtes) est le degré pair de tous les sommets. Imaginons notre liste de villes comme celle-ci : {Moscou Anapa Adler Rostov-on-Don Wuhan}. Construisons un graphique : Dans le diagramme, vous pouvez voir que ce graphique a un chemin eulérien. Il n'y a que deux sommets de degré impair - ce sont M et L, les autres sont pairs : A a le degré 4, car la boucle est comptée deux fois, et P et Y ont le degré 2. Si nous proposons un algorithme capable de construire une route eulérienne basée sur ce schéma, disons sous la forme d'une liste {M, A, A, P, Y , L}, alors nous résoudrons le problème , car sortir les mots dans un ordre donné ne sera qu’une question de technique. Ainsi, la solution à notre problème de mot domino revient à implémenter un algorithme pour trouver un chemin eulérien (le cycle est « libre ») dans un graphe orienté. Suivant ->
Ceci est aussi un graphe : 
Si l'on peut dire d'une arête qu'elle a une direction, alors le graphe est dit orienté : 
Les graphes des deux premières images ne sont pas orientés. On peut dire d'eux que l'arête (u, v) est identique à l'arête (v, u), c'est-à-dire par exemple que les arêtes (0, 4) et (4, 0) sont la même arête. Les flèches sur les bords d'un graphe orienté signifient que le bord (u, v) est un chemin allant du sommet u au sommet v et que le bord (v, u) n'existe pas. Sur la troisième image, il y a un bord (E, A). Il n'y a pas de bord (A, E). Regardons de plus près le dernier dessin. Vous pouvez remarquer que le sommet F n’a aucune arête, c’est tout à fait possible. Nous notons également qu'une arête est apparue près du sommet A - une boucle, et entre les sommets B et D il y a deux arêtes dirigées différemment. Les graphes orientés autorisent de tels artefacts. Disons que le graphique décrit un groupe de connaissances qui s'offrent des cadeaux. On voit que le gourmand F n'a rien donné à personne, B et D ont échangé des cadeaux (sauf que chacun d'eux a fait un cadeau à quelqu'un d'autre), et A s'est fait un cadeau, probablement à l'occasion de la résolution réussie d'un problème. problème de la planète Linear Chaos. À propos, notez que les sommets du graphe ne doivent pas nécessairement être des nombres ou contenir des nombres ; ce sont plutôt des conteneurs, c'est-à-dire ils peuvent stocker n'importe quel objet. Un graphique est une description des connexions. Un terme important qui nous sera utile plus tard - le nombre d'arêtes attachées à un sommet (ou, comme on dit aussi, incidentes à celui-ci) est appelé le degré d'un sommet donné. Par exemple, dans la première image, le sommet 0 a le degré 2, 1 a le degré 4, 3 a le degré 3, le sommet 0 de la deuxième figure a le degré 1. Dans cet article, nous n'entrerons pas dans la variété des différents types de graphiques, on mentionnera seulement qu'il existe aussi des graphiques pondérés, ceux-là. ceux dans lesquels un certain numéro est attaché à chaque bord, qui indique le « prix » de son passage. Les graphes connectés ont un certain nombre de sous-types, qui se distinguent par leurs propriétés. Par exemple, les graphiques dont les bords ne forment aucun cycle nulle part sont appelés arbres (ils ont des familles intéressantes avec des noms impressionnants comme « arbres rouge-noir », par exemple) et sont largement utilisés dans une variété d’algorithmes et de structures de données importants. Utiliser un graphique pour résoudre un problème Tout cela est très intéressant, dites-vous, mais qu'est-ce que tout cela a à voir avec la construction d'une chaîne de mots ? Il s'avère que la chose la plus directe est. Regardons notre exemple de test à partir de la condition : { Amsterdam Melbourne New York Kiev Vienne }. Écrivons dans n'importe quel ordre les lettres "nodales" auxquelles s'accrochent les mots : {A, M, N, K, B} 
et connectons-les avec des mots. 
Comme nous pouvons le voir, nous avons un graphe orienté dans lequel les nœuds sont des lettres et les bords sont des mots qui les relient. Si nous trouvons un moyen de parcourir toutes les arêtes de sommet en sommet afin de visiter chaque arête une seule fois, notre problème sera résolu. Essayons de répartir les nœuds du diagramme un peu différemment : 
Nous pouvons maintenant mieux voir que notre graphique est une boucle fermée. Nous pouvons commencer la séquence avec n’importe quel mot, et ce sera la bonne décision. Cependant, l’état du problème nous indique qu’une seule solution suffira. Remplaçons Vena par Vladimir : Nous 
voyons deux conséquences : d'une part, nous avons dû ajouter un nouveau sommet, la lettre P, et d'autre part, nous voyons qu'il n'est plus possible de boucler notre graphe. Résumons tout ce qui précède et introduisons deux nouveaux termes : 1. Un graphe connexe dont les arêtes peuvent être parcourues en visitant chacune d'entre elles une seule fois est appelé un graphe contenant un « chemin eulérien » . Une caractéristique d'un tel graphe (à l'exception de l'absence de sommets sans arêtes) est le degré pair de tous les sommets sauf deux (et seulement deux). 2. S'il s'avère possible de revenir au nœud d'origine, on dit qu'il y a un « cycle eulérien » dans le graphe . Une caractéristique d'un tel graphe (à l'exception de l'absence de sommets sans arêtes) est le degré pair de tous les sommets. Imaginons notre liste de villes comme celle-ci : {Moscou Anapa Adler Rostov-on-Don Wuhan}. Construisons un graphique : 
Dans le diagramme, vous pouvez voir que ce graphique a un chemin eulérien. Il n'y a que deux sommets de degré impair - ce sont M et L, les autres sont pairs : A a le degré 4, car la boucle est comptée deux fois, et P et Y ont le degré 2. Si nous proposons un algorithme capable de construire une route eulérienne basée sur ce schéma, disons sous la forme d'une liste {M, A, A, P, Y , L}, alors nous résoudrons le problème , car sortir les mots dans un ordre donné ne sera qu’une question de technique. Ainsi, la solution à notre problème de mot domino revient à implémenter un algorithme pour trouver un chemin eulérien (le cycle est « libre ») dans un graphe orienté. Suivant ->
GO TO FULL VERSION