给定一个单词列表，确定单词是否可以链接成一个圆圈

Question

给定一个单词列表，确定单词是否可以链接成一个圆圈。一个字X 如果 X 的最后一个字符与 Y的第一个字符。 例如['chair'、'height'、'racket'、touch'、'tunic']等词可以组成如下圆圈： 椅子 --> 球拍 --> 触摸 --> 高度 --> 外衣 --> 椅子 输出它必须是一个 txt 文件，每行一个单词，例如： 椅子 球拍 触碰 高度 束腰外衣

我搜索了解决方案，但我只设法得到了部分解决方案，它回答了它是否可以是一个圆。

# Python program to check if a given directed graph is Eulerian or not
CHARS = 26

# A class that represents an undirected graph
class Graph(object):
    def __init__(self, V):
        self.V = V   # No. of vertices
        self.adj = [[] for x in range(V)] # a dynamic array
        self.inp = [0] * V

    # function to add an edge to graph
    def addEdge(self, v, w):
        self.adj[v].append(w)
        self.inp[w]+=1

    # Method to check if this graph is Eulerian or not
    def isSC(self):
        # Mark all the vertices as not visited (For first DFS)
        visited = [False] * self.V

        # Find the first vertex with non-zero degree
        n = 0
        for n in range(self.V):
            if len(self.adj[n]) > 0:
                break

        # Do DFS traversal starting from first non zero degree vertex.
        self.DFSUtil(n, visited)

        # If DFS traversal doesn't visit all vertices, then return false.
        for i in range(self.V):
            if len(self.adj[i]) > 0 and visited[i] == False:
                return False

        # Create a reversed graph
        gr = self.getTranspose()

        # Mark all the vertices as not visited (For second DFS)
        for i in range(self.V):
            visited[i] = False

        # Do DFS for reversed graph starting from first vertex.
        # Starting Vertex must be same starting point of first DFS
        gr.DFSUtil(n, visited)

        # If all vertices are not visited in second DFS, then
        # return false
        for i in range(self.V):
            if len(self.adj[i]) > 0 and visited[i] == False:
                return False

        return True

    # This function returns true if the directed graph has an eulerian
    # cycle, otherwise returns false
    def isEulerianCycle(self):

        # Check if all non-zero degree vertices are connected
        if self.isSC() == False:
            return False

        # Check if in degree and out degree of every vertex is same
        for i in range(self.V):
            if len(self.adj[i]) != self.inp[i]:
                return False

        return True

    # A recursive function to do DFS starting from v
    def DFSUtil(self, v, visited):

        # Mark the current node as visited and print it
        visited[v] = True

        # Recur for all the vertices adjacent to this vertex
        for i in range(len(self.adj[v])):
            if not visited[self.adj[v][i]]:
                self.DFSUtil(self.adj[v][i], visited)

    # Function that returns reverse (or transpose) of this graph
    # This function is needed in isSC()
    def getTranspose(self):
        g = Graph(self.V)
        for v in range(self.V):
            # Recur for all the vertices adjacent to this vertex
            for i in range(len(self.adj[v])):
                g.adj[self.adj[v][i]].append(v)
                g.inp[v]+=1
        return g

# This function takes an of strings and returns true
# if the given array of strings can be chained to
# form cycle
def canBeChained(arr, n):

    # Create a graph with 'alpha' edges
    g = Graph(CHARS)

    # Create an edge from first character to last character
    # of every string
    for i in range(n):
        s = arr[i]
        g.addEdge(ord(s[0])-ord('a'), ord(s[len(s)-1])-ord('a'))

    # The given array of strings can be chained if there
    # is an eulerian cycle in the created graph
    return g.isEulerianCycle()

# Driver program
arr1 = ["for", "geek", "rig", "kaf"]
n1 = len(arr1)
if canBeChained(arr1, n1):
    print ("Can be chained")
else:
    print ("Cant be chained")

arr2 = ["aab", "abb"]
n2 = len(arr2)
if canBeChained(arr2, n2):
    print ("Can be chained")
else:
    print ("Can't be chained")

来源：https://www.geeksforgeeks.org/given-array-strings-find-strings-can-chained-form-circle/

这个解决方案只有returns列表的布尔语句，意思是如果有圆就输出True。我的目标是尝试扩展此解决方案以将列表分开，我将举另一个例子：

Input:
{"for", "geek", "rig", "kaf"}

Output:
for
rig
geek
kaf
for

Answer 1

解决这个问题似乎费了很大功夫。考虑一个简单的解决方案，例如：

from collections import defaultdict

words = ['chair', 'height', 'racket', 'touch', 'tunic']

def findChains(words):
    dictionary = defaultdict(list)
    
    for word in words:
        dictionary[word[0]].append(word)

    chains = [[words[0]]]  # start with an arbitrary word

    while True:
        new_chains = []

        for chain in chains:
            for follower in dictionary[chain[-1][-1]]:
                if follower in chain:
                    continue

                new_chains.append([*chain, follower])

        if new_chains:
            chains = new_chains
        else:
            break

    return [chain for chain in chains if len(chain) == len(words) and chain[-1][-1] == chain[0][0]]
        
print(findChains(words))

输出

% python3 test.py
[['chair', 'racket', 'touch', 'height', 'tunic']]
% 

问题是随着单词列表变长，像上面这样的简单算法变得不可行了吗？您似乎还假设了一个解决方案，但是如果有足够的开始和结束字母冗余，则可能有多个解决方案。即使最后你只选择一个，你也需要编写多个代码。

Answer 2

您描述的问题是欧拉回路问题。

networkx 模块中实现了一个算法：

• networkx.algorithms.euler.eulerian_circuit

from networkx import DiGraph, eulerian_circuit

words = ['chair', 'height', 'racket', 'touch', 'tunic']
G = DiGraph()
G.add_weighted_edges_from(((w[0], w[-1], w) for w in words), weight='word')
result = [G[a][b]['word'] for a,b in eulerian_circuit(G)]

print(result)
# ['chair', 'racket', 'touch', 'height', 'tunic']