Part 2 Part 3 Part 4 I was prompted to write this article by a harmful task from the Java Multithreading quest, which, not without some teasing from the developers, was called by them a “StringBuilder task.” The essence of her condition was that a set of words (in the condition the names of cities are given, which is reminiscent of a children's word game) had to be arranged according to the domino principle, the last letter of the n' word should be equal to the first letter of the word (n+1) go, and it was known that all the given (individually) words were added up in such a chain. If it was possible to compose several options for the desired chain of words, any one was accepted as a solution. Despite the apparent simplicity and clarity of the condition, solving the problem was far from easy, and masterful use of StringBuilder did not save the situation. The developers of the problem turned out to be ordered isomorphs from the planet Linear Chaos, who more than once terrified JavaRush cadets. As expected, superficial solutions did not suit the validator, since there were always chains that forced the naive algorithm to skip words. It was necessary to pile up additional “crutches”, which, while complicating the problem, did not bring the solution closer in the general case and increasingly strengthened the feeling that a simple condition should have an equally simple solution. I had to change tactics and dive a little into more fundamental areas. Let me make a reservation right away that in no case do I consider myself an expert in graph theory; the topics that I will touch upon almost do not go beyond the scope of solving the domino word problem, with the exception, perhaps, of only a couple of digressions of a theoretical nature. So, graphs. What is a graph: it is a collection (set, set, list - whatever) of vertices connected to each other . Connections are usually called edges , vertices are also called nodes or nodes. This is a graph: This is also a graph: If we can say about an edge that it has a direction, then the graph is called oriented : The graphs in the first two pictures are undirected. We can say about them that the edge (u, v) is identical to the edge (v, u), that is, for example, the edges (0, 4) and (4, 0) are the same edge. Arrows on the edges of a directed graph mean that edge (u, v) is a path from vertex u to vertex v and edge (v, u) does not exist. In the third picture there is an edge (E, A). There is no edge (A, E). Let's take a closer look at the last drawing. You can notice that vertex F has no edges at all, this is quite possible. We also note that an edge has appeared near vertex A - a loop, and between vertices B and D there are two differently directed edges. Directed graphs allow such artifacts. Let's say that the graph describes a group of acquaintances who give each other gifts. We see that greedy F did not give anything to anyone, B and D exchanged gifts (except for the fact that each of them gave a gift to someone else), and A gave a gift to himself, probably on the occasion of successfully solving a problem from the planet Linear Chaos. By the way, note that the vertices of the graph do not have to be numbers or contain numbers; they are rather containers, i.e. they can store any object. A graph is a description of connections. An important term that will be useful to us later - the number of edges attached to a vertex (or, as they also say, incident to it) is called the degree of a given vertex. For example, in the first picture, vertex 0 has degree 2, 1 has degree 4, 3 has degree 3, vertex 0 of the second figure has degree 1. In this article we will not delve into the variety of different types of graphs, we will only mention that there are also weighted graphs, those. those in which a certain number is attached to each edge, which indicates the “price” of its passage. Connected graphs have a number of subtypes, distinguished by their properties. For example, graphs whose edges do not form a cycle anywhere are called trees (they have interesting families with awesome names like “red-black trees,” for example) and are widely used in a variety of important algorithms and data structures. Using a graph to solve a problem All this is very interesting, you say, but what does all this have to do with constructing a chain of words? It turns out that the most direct thing is. Let's look at our test example from the condition: { Amsterdam Melbourne New York Kyiv Vienna }. Let's write down in any order the "nodal" letters that the words cling to: {A, M, N, K, B} and connect them with words. As we can see, we have a directed graph in which the nodes are letters and the edges are words , connecting them. If we find a way to traverse all edges from vertex to vertex so that we visit each edge only once, our problem will be solved. Let's try to distribute the nodes in the diagram a little differently: Now we can better see that our graph is a closed loop. We can start the sequence with any word, and it will be the right decision. However, the condition of the problem tells us that any one solution will be sufficient. Let's replace Vena with Vladimir: We see two consequences: firstly, we had to add a new vertex, the letter P, and secondly, we see that it is no longer possible to loop our graph. Let's summarize all of the above and introduce two new terms: 1. A connected graph whose edges can be traversed by visiting each one only once is called a graph containing an “Eulerian path” . A feature of such a graph (except for the absence of vertices without edges) is the even degree of all vertices except two (and only two). 2. If it turns out to be possible to return to the original node, we say that there is an “Eulerian cycle” in the graph . A feature of such a graph (except for the absence of vertices without edges) is the even degree of all vertices. Let's imagine our list of cities like this: {Moscow Anapa Adler Rostov-on-Don Wuhan}. Let's build a graph: In the diagram you can see that this graph has an Eulerian path. There are only two vertices with an odd degree - these are M and L, the rest are even: A has degree 4, because the loop is counted twice, and P and Y have degree 2. If we come up with an algorithm that can build an Eulerian route based on this scheme, say, in the form of a list {M, A, A, P, Y, L}, then we will solve the problem , because outputting words in a given order will only be a matter of technique. Thus, the solution to our domino word problem comes down to implementing an algorithm for finding an Eulerian path (the cycle is “free”) in a directed graph. Next ->
This is also a graph: 
If we can say about an edge that it has a direction, then the graph is called oriented : 
The graphs in the first two pictures are undirected. We can say about them that the edge (u, v) is identical to the edge (v, u), that is, for example, the edges (0, 4) and (4, 0) are the same edge. Arrows on the edges of a directed graph mean that edge (u, v) is a path from vertex u to vertex v and edge (v, u) does not exist. In the third picture there is an edge (E, A). There is no edge (A, E). Let's take a closer look at the last drawing. You can notice that vertex F has no edges at all, this is quite possible. We also note that an edge has appeared near vertex A - a loop, and between vertices B and D there are two differently directed edges. Directed graphs allow such artifacts. Let's say that the graph describes a group of acquaintances who give each other gifts. We see that greedy F did not give anything to anyone, B and D exchanged gifts (except for the fact that each of them gave a gift to someone else), and A gave a gift to himself, probably on the occasion of successfully solving a problem from the planet Linear Chaos. By the way, note that the vertices of the graph do not have to be numbers or contain numbers; they are rather containers, i.e. they can store any object. A graph is a description of connections. An important term that will be useful to us later - the number of edges attached to a vertex (or, as they also say, incident to it) is called the degree of a given vertex. For example, in the first picture, vertex 0 has degree 2, 1 has degree 4, 3 has degree 3, vertex 0 of the second figure has degree 1. In this article we will not delve into the variety of different types of graphs, we will only mention that there are also weighted graphs, those. those in which a certain number is attached to each edge, which indicates the “price” of its passage. Connected graphs have a number of subtypes, distinguished by their properties. For example, graphs whose edges do not form a cycle anywhere are called trees (they have interesting families with awesome names like “red-black trees,” for example) and are widely used in a variety of important algorithms and data structures. Using a graph to solve a problem All this is very interesting, you say, but what does all this have to do with constructing a chain of words? It turns out that the most direct thing is. Let's look at our test example from the condition: { Amsterdam Melbourne New York Kyiv Vienna }. Let's write down in any order the "nodal" letters that the words cling to: {A, M, N, K, B} 
and connect them with words. 
As we can see, we have a directed graph in which the nodes are letters and the edges are words , connecting them. If we find a way to traverse all edges from vertex to vertex so that we visit each edge only once, our problem will be solved. Let's try to distribute the nodes in the diagram a little differently: 
Now we can better see that our graph is a closed loop. We can start the sequence with any word, and it will be the right decision. However, the condition of the problem tells us that any one solution will be sufficient. Let's replace Vena with Vladimir: 
We see two consequences: firstly, we had to add a new vertex, the letter P, and secondly, we see that it is no longer possible to loop our graph. Let's summarize all of the above and introduce two new terms: 1. A connected graph whose edges can be traversed by visiting each one only once is called a graph containing an “Eulerian path” . A feature of such a graph (except for the absence of vertices without edges) is the even degree of all vertices except two (and only two). 2. If it turns out to be possible to return to the original node, we say that there is an “Eulerian cycle” in the graph . A feature of such a graph (except for the absence of vertices without edges) is the even degree of all vertices. Let's imagine our list of cities like this: {Moscow Anapa Adler Rostov-on-Don Wuhan}. Let's build a graph: 
In the diagram you can see that this graph has an Eulerian path. There are only two vertices with an odd degree - these are M and L, the rest are even: A has degree 4, because the loop is counted twice, and P and Y have degree 2. If we come up with an algorithm that can build an Eulerian route based on this scheme, say, in the form of a list {M, A, A, P, Y, L}, then we will solve the problem , because outputting words in a given order will only be a matter of technique. Thus, the solution to our domino word problem comes down to implementing an algorithm for finding an Eulerian path (the cycle is “free”) in a directed graph. Next ->
GO TO FULL VERSION