Parte 2 Parte 3 Parte 4 Fui solicitado a escrever este artigo por causa de uma tarefa prejudicial da missão Java Multithreading, que, não sem algumas provocações dos desenvolvedores, foi chamada por eles de “tarefa StringBuilder”. A essência de sua condição era que um conjunto de palavras (na condição em que são dados os nomes das cidades, o que lembra um jogo de palavras infantil) deveria ser organizado de acordo com o princípio do dominó, a última letra da palavra n deveria ser igual à primeira letra da palavra (n+1) go, e sabia-se que todas as palavras dadas (individualmente) foram somadas em tal cadeia. Caso fosse possível compor várias opções para a cadeia de palavras desejada, qualquer uma era aceita como solução. Apesar da aparente simplicidade e clareza da condição, resolver o problema não foi nada fácil, e o uso magistral do StringBuilder não salvou a situação. Os desenvolvedores do problema acabaram sendo isomorfos encomendados do planeta Linear Chaos, que mais de uma vez aterrorizou os cadetes do JavaRush. Como era de se esperar, soluções superficiais não agradavam ao validador, pois sempre havia cadeias que obrigavam o algoritmo ingênuo a pular palavras. Foi necessário acumular “muletas” adicionais que, embora complicassem o problema, não aproximavam a solução no caso geral e reforçavam cada vez mais o sentimento de que uma condição simples deveria ter uma solução igualmente simples. Tive que mudar de tática e mergulhar um pouco em áreas mais fundamentais. Deixe-me fazer uma reserva desde já que em nenhum caso me considero um especialista em teoria dos grafos; os tópicos que irei abordar quase não vão além do âmbito da resolução do problema da palavra dominó, com exceção, talvez, de apenas algumas digressões de natureza teórica. Então, gráficos. O que é um gráfico: é uma coleção (conjunto, conjunto, lista - tanto faz) de vértices conectados entre si . As conexões são geralmente chamadas de arestas , os vértices também são chamados de nós ou nós. Este é um gráfico: Isto também é um gráfico: Se pudermos dizer sobre uma aresta que ela tem uma direção, então o gráfico é chamado de orientado : Os gráficos nas duas primeiras imagens não são direcionados. Podemos dizer sobre eles que a aresta (u, v) é idêntica à aresta (v, u), ou seja, por exemplo, as arestas (0, 4) e (4, 0) são a mesma aresta. As setas nas arestas de um gráfico direcionado significam que a aresta (u, v) é um caminho do vértice u ao vértice v e a aresta (v, u) não existe. Na terceira foto há uma aresta (E, A). Não há aresta (A, E). Vamos dar uma olhada no último desenho. Você pode notar que o vértice F não possui arestas, isso é bem possível. Observamos também que uma aresta apareceu perto do vértice A - um loop, e entre os vértices B e D existem duas arestas direcionadas de forma diferente. Gráficos direcionados permitem tais artefatos. Digamos que o gráfico descreve um grupo de conhecidos que trocam presentes. Vemos que o ganancioso F não deu nada a ninguém, B e D trocaram presentes (exceto pelo fato de cada um ter dado um presente a outra pessoa) e A deu um presente a si mesmo, provavelmente por ocasião da solução bem-sucedida de um problema. problema do planeta Linear Chaos. A propósito, observe que os vértices do gráfico não precisam ser números ou conter números; eles são antes contêineres, ou seja, eles podem armazenar qualquer objeto. Um gráfico é uma descrição de conexões. Um termo importante que nos será útil mais tarde - o número de arestas anexadas a um vértice (ou, como também dizem, incidentes a ele) é chamado de grau de um determinado vértice. Por exemplo, na primeira imagem, o vértice 0 tem grau 2, 1 tem grau 4, 3 tem grau 3, o vértice 0 da segunda figura tem grau 1. Neste artigo não nos aprofundaremos na variedade de diferentes tipos de gráficos, mencionaremos apenas que também existem gráficos ponderados, Essa. aqueles em que um determinado número é anexado a cada aresta, o que indica o “preço” de sua passagem. Os gráficos conectados possuem vários subtipos, diferenciados por suas propriedades. Por exemplo, gráficos cujas arestas não formam um ciclo em nenhum lugar são chamados de árvores (eles têm famílias interessantes com nomes impressionantes como “árvores rubro-negras”, por exemplo) e são amplamente utilizados em uma variedade de algoritmos e estruturas de dados importantes. Usando um gráfico para resolver um problema Tudo isso é muito interessante, você diz, mas o que tudo isso tem a ver com a construção de uma cadeia de palavras? Acontece que o mais direto é. Vejamos nosso exemplo de teste da condição: { Amsterdam Melbourne New York Kyiv Vienna }. Vamos anotar em qualquer ordem as letras "nodais" às quais as palavras se apegam: {A, M, N, K, B} e conectá-las com palavras. Como podemos ver, temos um gráfico direcionado em que os nós são letras e as arestas são palavras, conectando-as. Se encontrarmos uma maneira de percorrer todas as arestas de vértice a vértice de modo que visitemos cada aresta apenas uma vez, nosso problema será resolvido. Vamos tentar distribuir os nós no diagrama de maneira um pouco diferente: Agora podemos ver melhor que nosso gráfico é um circuito fechado. Podemos iniciar a sequência com qualquer palavra e será a decisão certa. Contudo, a condição do problema diz-nos que qualquer solução será suficiente. Vamos substituir Vena por Vladimir: Vemos duas consequências: primeiro, tivemos que adicionar um novo vértice, a letra P, e segundo, vemos que não é mais possível fazer um loop em nosso gráfico. Vamos resumir tudo o que foi dito acima e introduzir dois novos termos: 1. Um grafo conectado cujas arestas podem ser percorridas visitando cada uma delas apenas uma vez é chamado de grafo contendo um “caminho euleriano ” . Uma característica de tal gráfico (exceto pela ausência de vértices sem arestas) é o grau par de todos os vértices, exceto dois (e apenas dois). 2. Se for possível retornar ao nó original, dizemos que existe um “ciclo euleriano” no grafo . Uma característica de tal gráfico (exceto pela ausência de vértices sem arestas) é o grau par de todos os vértices. Vamos imaginar nossa lista de cidades como esta: {Moscou Anapa Adler Rostov-on-Don Wuhan}. Vamos construir um gráfico: No diagrama você pode ver que este gráfico possui um caminho euleriano. Existem apenas dois vértices com grau ímpar - estes são M e L, os demais são pares: A tem grau 4, porque o loop é contado duas vezes e P e Y têm grau 2. Se chegarmos a um algoritmo que possa construir uma rota euleriana baseada neste esquema, digamos, na forma de uma lista {M, A, A, P, Y , L}, então resolveremos o problema, porque produzir palavras em uma determinada ordem será apenas uma questão de técnica. Assim, a solução para o nosso problema de dominó se resume à implementação de um algoritmo para encontrar um caminho euleriano (o ciclo é “livre”) em um grafo direcionado. Próximo ->
Isto também é um gráfico: 
Se pudermos dizer sobre uma aresta que ela tem uma direção, então o gráfico é chamado de orientado : 
Os gráficos nas duas primeiras imagens não são direcionados. Podemos dizer sobre eles que a aresta (u, v) é idêntica à aresta (v, u), ou seja, por exemplo, as arestas (0, 4) e (4, 0) são a mesma aresta. As setas nas arestas de um gráfico direcionado significam que a aresta (u, v) é um caminho do vértice u ao vértice v e a aresta (v, u) não existe. Na terceira foto há uma aresta (E, A). Não há aresta (A, E). Vamos dar uma olhada no último desenho. Você pode notar que o vértice F não possui arestas, isso é bem possível. Observamos também que uma aresta apareceu perto do vértice A - um loop, e entre os vértices B e D existem duas arestas direcionadas de forma diferente. Gráficos direcionados permitem tais artefatos. Digamos que o gráfico descreve um grupo de conhecidos que trocam presentes. Vemos que o ganancioso F não deu nada a ninguém, B e D trocaram presentes (exceto pelo fato de cada um ter dado um presente a outra pessoa) e A deu um presente a si mesmo, provavelmente por ocasião da solução bem-sucedida de um problema. problema do planeta Linear Chaos. A propósito, observe que os vértices do gráfico não precisam ser números ou conter números; eles são antes contêineres, ou seja, eles podem armazenar qualquer objeto. Um gráfico é uma descrição de conexões. Um termo importante que nos será útil mais tarde - o número de arestas anexadas a um vértice (ou, como também dizem, incidentes a ele) é chamado de grau de um determinado vértice. Por exemplo, na primeira imagem, o vértice 0 tem grau 2, 1 tem grau 4, 3 tem grau 3, o vértice 0 da segunda figura tem grau 1. Neste artigo não nos aprofundaremos na variedade de diferentes tipos de gráficos, mencionaremos apenas que também existem gráficos ponderados, Essa. aqueles em que um determinado número é anexado a cada aresta, o que indica o “preço” de sua passagem. Os gráficos conectados possuem vários subtipos, diferenciados por suas propriedades. Por exemplo, gráficos cujas arestas não formam um ciclo em nenhum lugar são chamados de árvores (eles têm famílias interessantes com nomes impressionantes como “árvores rubro-negras”, por exemplo) e são amplamente utilizados em uma variedade de algoritmos e estruturas de dados importantes. Usando um gráfico para resolver um problema Tudo isso é muito interessante, você diz, mas o que tudo isso tem a ver com a construção de uma cadeia de palavras? Acontece que o mais direto é. Vejamos nosso exemplo de teste da condição: { Amsterdam Melbourne New York Kyiv Vienna }. Vamos anotar em qualquer ordem as letras "nodais" às quais as palavras se apegam: {A, M, N, K, B} 
e conectá-las com palavras. 
Como podemos ver, temos um gráfico direcionado em que os nós são letras e as arestas são palavras, conectando-as. Se encontrarmos uma maneira de percorrer todas as arestas de vértice a vértice de modo que visitemos cada aresta apenas uma vez, nosso problema será resolvido. Vamos tentar distribuir os nós no diagrama de maneira um pouco diferente: 
Agora podemos ver melhor que nosso gráfico é um circuito fechado. Podemos iniciar a sequência com qualquer palavra e será a decisão certa. Contudo, a condição do problema diz-nos que qualquer solução será suficiente. Vamos substituir Vena por Vladimir: 
Vemos duas consequências: primeiro, tivemos que adicionar um novo vértice, a letra P, e segundo, vemos que não é mais possível fazer um loop em nosso gráfico. Vamos resumir tudo o que foi dito acima e introduzir dois novos termos: 1. Um grafo conectado cujas arestas podem ser percorridas visitando cada uma delas apenas uma vez é chamado de grafo contendo um “caminho euleriano ” . Uma característica de tal gráfico (exceto pela ausência de vértices sem arestas) é o grau par de todos os vértices, exceto dois (e apenas dois). 2. Se for possível retornar ao nó original, dizemos que existe um “ciclo euleriano” no grafo . Uma característica de tal gráfico (exceto pela ausência de vértices sem arestas) é o grau par de todos os vértices. Vamos imaginar nossa lista de cidades como esta: {Moscou Anapa Adler Rostov-on-Don Wuhan}. Vamos construir um gráfico: 
No diagrama você pode ver que este gráfico possui um caminho euleriano. Existem apenas dois vértices com grau ímpar - estes são M e L, os demais são pares: A tem grau 4, porque o loop é contado duas vezes e P e Y têm grau 2. Se chegarmos a um algoritmo que possa construir uma rota euleriana baseada neste esquema, digamos, na forma de uma lista {M, A, A, P, Y , L}, então resolveremos o problema, porque produzir palavras em uma determinada ordem será apenas uma questão de técnica. Assim, a solução para o nosso problema de dominó se resume à implementação de um algoritmo para encontrar um caminho euleriano (o ciclo é “livre”) em um grafo direcionado. Próximo ->
GO TO FULL VERSION