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

Question

给定单词列表，请确定是否可以链接单词以形成一个圆圈。一个单词x 如果x的最后一个字符与 Y的第一个角色。 例如，[“椅子”，“高度”，“球拍”，Touch'，'Tunic']单词可以形成以下圆： 主席 - ＆GT;球拍 - ＆gt;触摸 - ＆gt;身高 - ＆GT;中衣 - ＆GT;椅子 输出必须是一个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")

来源：

此解决方案仅返回列表的布尔语句，这意味着如果有一个圆圈，它将输出True。我的目标是尝试扩展该解决方案以使列表分开，我将举一个例子：

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

Output:
for
rig
geek
kaf
for

Answer 1

您要描述的问题是 Eulerian电路问题。

在模块网络中实现了一种算法：

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']

Answer 2

这似乎是为解决这个问题的努力。考虑一个简单的解决方案，例如：

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']]
% 

随着单词列表越来越长，像上面的简单算法变得不可行？您似乎还假设一个解决方案，但是有了足够的开始和结束字母冗余，可能会有多种解决方案。即使您只选择一个，您也需要为多个代码进行编码。