Pro.ID10164 TitleEulerian Tour Title链接http://10.20.2.8/oj/exercise/problem?problem_id=10164 AC0 Submit1 Ratio0.00% 时间&空间限制描述Sample Problem: Riding The FencesFarmer John owns a large number of fences, which he must periodically check for integrity. Farmer John keeps track of his fences by maintaining a list of their intersection points, along with the fences which end at each point. Each fence has two end points, each at an intersection point, although the intersection point may be the end point of only a single fence. Of course, more than two fences might share an endpoint. Given the fence layout, calculate if there is a way for Farmer John to ride his horse to all of his fences without riding along a fence more than once. Farmer John can start and end anywhere, but cannot cut across his fields (the only way he can travel between intersection points is along a fence). If there is a way, find one way. The AbstractionGiven: An undirected graph Find a path which uses every edge exactly once. This is called an Eulerian tour. If the path begins and ends at the same vertex, it is called a Eulerian circuit. The AlgorithmDetecting whether a graph has an Eulerian tour or circuit is actually easy; two different rules apply.
The basic idea of the algorithm is to start at some node the graph and determine a circuit back to that same node. Now, as the circuit is added (in reverse order, as it turns out), the algorithm ensures that all the edges of all the nodes along that path have been used. If there is some node along that path which has an edge that has not been used, then the algorithm finds a circuit starting at that node which uses that edge and splices this new circuit into the current one. This continues until all the edges of every node in the original circuit have been used, which, since the graph is connected, implies that all the edges have been used, so the resulting circuit is Eulerian. More formally, to determine a Eulerian circuit of a graph which has one, pick a starting node and recurse on it. At each recursive step:
# circuit is a global array
find_euler_circuit
circuitpos = 0
find_circuit(node 1)
# nextnode and visited is a local array
# the path will be found in reverse order
find_circuit(node i)
if node i has no neighbors then
circuit(circuitpos) = node i
circuitpos = circuitpos + 1
else
while (node i has neighbors)
pick a random neighbor node j of node i
delete_edges (node j, node i)
find_circuit (node j)
circuit(circuitpos) = node i
circuitpos = circuitpos + 1 To find an Eulerian tour, simply find one of the nodes which has odd degree and call find_circuit with it. Both of these algorithms run in O(m + n) time, where m is the number of edges and n is the number of nodes, if you store the graph in adjacency list form. With larger graphs, there's a danger of overflowing the run-time stack, so you might have to use your own stack. Execution ExampleConsider the following graph: Assume that selecting a random neighbor yields the lowest numbered neighbor, the execution goes as follows:
ExtensionsMultiple edges between nodes can be handled by the exact same algorithm. Self-loops can be handled by the exact same algorithm as well, if self-loops are considered to add 2 (one in and one out) to the degree of a node. A directed graph has a Eulerian circuit if it is strongly connected (except for nodes with both in-degree and out-degree of 0) and the indegree of each node equals its outdegree. The algorithm is exactly the same, except that because of the way this code finds the cycle, you must traverse arcs in reverse order. Finding a Eulerian path in a directed graph is harder. Consult Sedgewick if you are interested. Example problemsAirplane HoppingGiven a collection of cities, along with the flights between those cities, determine if there is a sequence of flights such that you take every flight exactly once, and end up at the place you started. Analysis: This is equivalent to finding a Eulerian circuit in a directed graph. Cows on ParadeFarmer John has two types of cows: black Angus and white Jerseys. While marching 19 of their cows to market the other day, John's wife Farmeress Joanne, noticed that all 16 possibilities of four successive black and white cows (e.g., bbbb, bbbw, bbwb, bbww, ..., wwww) were present. Of course, some of the combinations overlapped others. Given N (2 <= N <= 15), find the minimum length sequence of cows such that every combination of N successive black and white cows occurs in that sequence. Analysis: The vertices of the graph are the possibilities of N-1 cows. Being at a node corresponds to the last N-1 cows matching the node in color. That is, for N = 4, if the last 3 cows were wbw, then you are at the wbw node. Each node has out-degree of 2, corresponding to adding a black or white cow to the end of the sequence. In addition, each node has in-degree of 2, corresponding to whether the cow just before the last N-1 cows is black or white. The graph is strongly connected, and the in-degree of each node equals its out-degree, so the graph has a Eulerian circuit. The sequence corresponding to the Eulerian circuit is the sequence of N-1 cows of the first node in the circuit, followed by cows corresponding to the color of the edge.
输入This is NOT a problem , but a course. Read it , but not Submit 输出Description Sample Problem: Riding The FencesFarmer John owns a large number of fences, which he must periodically check for integrity. Farmer John keeps track of his fences by maintaining a list of their intersection points, along with the fences which end at each point. Each fence has two end points, each at an intersection point, although the intersection point may be the end point of only a single fence. Of course, more than two fences might share an endpoint. Given the fence layout, calculate if there is a way for Farmer John to ride his horse to all of his fences without riding along a fence more than once. Farmer John can start and end anywhere, but cannot cut across his fields (the only way he can travel between intersection points is along a fence). If there is a way, find one way. The AbstractionGiven: An undirected graph Find a path which uses every edge exactly once. This is called an Eulerian tour. If the path begins and ends at the same vertex, it is called a Eulerian circuit. The AlgorithmDetecting whether a graph has an Eulerian tour or circuit is actually easy; two different rules apply.
The basic idea of the algorithm is to start at some node the graph and determine a circuit back to that same node. Now, as the circuit is added (in reverse order, as it turns out), the algorithm ensures that all the edges of all the nodes along that path have been used. If there is some node along that path which has an edge that has not been used, then the algorithm finds a circuit starting at that node which uses that edge and splices this new circuit into the current one. This continues until all the edges of every node in the original circuit have been used, which, since the graph is connected, implies that all the edges have been used, so the resulting circuit is Eulerian. More formally, to determine a Eulerian circuit of a graph which has one, pick a starting node and recurse on it. At each recursive step:
# circuit is a global array
find_euler_circuit
circuitpos = 0
find_circuit(node 1)
# nextnode and visited is a local array
# the path will be found in reverse order
find_circuit(node i)
if node i has no neighbors then
circuit(circuitpos) = node i
circuitpos = circuitpos + 1
else
while (node i has neighbors)
pick a random neighbor node j of node i
delete_edges (node j, node i)
find_circuit (node j)
circuit(circuitpos) = node i
circuitpos = circuitpos + 1 To find an Eulerian tour, simply find one of the nodes which has odd degree and call find_circuit with it. Both of these algorithms run in O(m + n) time, where m is the number of edges and n is the number of nodes, if you store the graph in adjacency list form. With larger graphs, there's a danger of overflowing the run-time stack, so you might have to use your own stack. Execution ExampleConsider the following graph: Assume that selecting a random neighbor yields the lowest numbered neighbor, the execution goes as follows:
ExtensionsMultiple edges between nodes can be handled by the exact same algorithm. Self-loops can be handled by the exact same algorithm as well, if self-loops are considered to add 2 (one in and one out) to the degree of a node. A directed graph has a Eulerian circuit if it is strongly connected (except for nodes with both in-degree and out-degree of 0) and the indegree of each node equals its outdegree. The algorithm is exactly the same, except that because of the way this code finds the cycle, you must traverse arcs in reverse order. Finding a Eulerian path in a directed graph is harder. Consult Sedgewick if you are interested. Example problemsAirplane HoppingGiven a collection of cities, along with the flights between those cities, determine if there is a sequence of flights such that you take every flight exactly once, and end up at the place you started. Analysis: This is equivalent to finding a Eulerian circuit in a directed graph. Cows on ParadeFarmer John has two types of cows: black Angus and white Jerseys. While marching 19 of their cows to market the other day, John's wife Farmeress Joanne, noticed that all 16 possibilities of four successive black and white cows (e.g., bbbb, bbbw, bbwb, bbww, ..., wwww) were present. Of course, some of the combinations overlapped others. Given N (2 <= N <= 15), find the minimum length sequence of cows such that every combination of N successive black and white cows occurs in that sequence. Analysis: The vertices of the graph are the possibilities of N-1 cows. Being at a node corresponds to the last N-1 cows matching the node in color. That is, for N = 4, if the last 3 cows were wbw, then you are at the wbw node. Each node has out-degree of 2, corresponding to adding a black or white cow to the end of the sequence. In addition, each node has in-degree of 2, corresponding to whether the cow just before the last N-1 cows is black or white. The graph is strongly connected, and the in-degree of each node equals its out-degree, so the graph has a Eulerian circuit. The sequence corresponding to the Eulerian circuit is the sequence of N-1 cows of the first node in the circuit, followed by cows corresponding to the color of the edge.
Input This is NOT a problem , but a course. Read it , but not Submit Output This is NOT a problem , but a course. Read it , but not Submit Sample Input This is NOT a problem , but a course. Read it , but not Submit Sample Output This is NOT a problem , but a course. Read it , but not Submit Source 样例输入This is NOT a problem , but a course. Read it , but not Submit 样例输出This is NOT a problem , but a course. Read it , but not Submit 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2024-9-20 06:12 , Processed in 0.037666 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
