algorithm - 遍历欧拉电路中的所有边并打印节点

Question

我正在尝试解决这个问题。我可以通过查看给定结构可以形成欧拉电路的程度来找到，但是对于给定的测试用例，我无法弄清楚如何找到跟踪所有路径

5

2 1

2 2

3 4

3 1

2 4

在节点 2 的电路中有一个循环，我不知道如何跟踪，如果我使用邻接表表示，那么我将得到以下列表

1：2,3

2：1,2,2,4

3：1,4

4：2,3

所以如何遍历每一条边，我知道这是欧拉电路问题，但是自循环的事情让我很难编写代码，而且我没有任何教程或博客可以从中理解这件事。

我再次考虑在遍历该路径后从邻接列表中删除节点（为了维护欧拉的属性（路径应该遍历一次）），但是我使用向量来存储邻接列表并且我不知道如何从向量中删除特定元素。我用谷歌搜索它并找到remove从向量中删除的命令，但从向量中remove删除所有匹配元素。

我现在尝试如下解决问题，但是得到了 WA :(

#include<iostream>
#include<cstdio>
#include<cstring>

int G[52][52];
int visited[52],n;

void printadj() {
  int i,j;
  for(i=0;i<51;i++) {
    for(j=0;j<51;j++)
      printf("%d  ",G[i][j]);
    printf("\n");
  }     
 }

 void dfs(int u){
  int v;
  for(v=0;v<51;v++){
    if(G[u][v]){
        G[u][v]--;
        G[v][u]--;
        printf("%d %d\n",u,v);       
        dfs(v);
     }                  
  }
}

bool is_euler(){
   int i,j,colsum=0,count=0;
   for(i=0;i<51;i++) {
    colsum=0;
    for(j=0;j<51;j++) {
       if(G[i][j] > 0) {
           colsum+=G[i][j];
       }
    }
     if(colsum%2!=0) count++; 
  }     
//  printf("\ncount=%d\n",count);
  if(count >0 ) return false;
  else return true;
}
void reset(){
    int i,j;
    for(i=0;i<51;i++)
      for(j=0;j<51;j++)                 
        G[i][j]=0;
}
int main(){
    int  u,v,i,t,k;
    scanf("%d",&t);
    for(k=0;k<t;k++) {
      scanf("%d",&n);
      reset();
      for(i=0;i<n;i++){
        scanf("%d%d",&u,&v);
        G[u][v]++;
        G[v][u]++;     
       }
//    printadj();
       printf("Case #%d\n",k+1);
      if(is_euler()) {
         dfs(u);
      }
      else printf("some beads may be lost\n");
      printf("\n");
  }
  return 0;
}

不知道为什么要得到 WA :(

新代码：-

#include<iostream>
#include<cstdio>
#include<cstring>

#define max 51

int G[max][max],print_u[max],print_v[max],nodes_traversed[max],nodes_found[max];
int n,m;

void printadj() {
  int i,j;
  for(i=0;i<max;i++) {
    for(j=0;j<max;j++)
      printf("%d  ",G[i][j]);
    printf("\n");
  }
 }

void dfs(int u){
  int v;
  for(v=0;v<50;v++){
    if(G[u][v]){
        G[u][v]--;
        G[v][u]--;
        print_u[m]=u;
        print_v[m]=v;
        m++;
        dfs(v);
     }
  }
  nodes_traversed[u]=1;
}

bool is_evendeg(){
   int i,j,colsum=0,count=0;
   for(i=0;i<50;i++) {
    colsum=0;
    for(j=0;j<50;j++) {
       if(G[i][j] > 0) {
           colsum+=G[i][j];
       }
    }
     if(colsum&1) return false;
  }
  return true;
}

int count_vertices(int nodes[]){
 int i,count=0;
 for(i=0;i<51;i++) if(nodes[i]==1) count++;
 return count;
}
void reset(){
    int i,j;
    m=0;
    for(i=0;i<max;i++)
      for(j=0;j<max;j++)
        G[i][j]=0;
    memset(print_u,0,sizeof(print_u));
    memset(print_v,0,sizeof(print_v));
    memset(nodes_traversed,0,sizeof(nodes_traversed));
    memset(nodes_found,0,sizeof(nodes_found));
}

bool is_connected(int tot_nodes,int trav_nodes) {
 if(tot_nodes == trav_nodes) return true;
 else return false;
}

int main(){
    int  u,v,i,t,k,tot_nodes,trav_nodes;
    scanf("%d",&t);
    for(k=0;k<t;k++) {
      scanf("%d",&n);
      reset();
      for(i=0;i<n;i++){
        scanf("%d%d",&u,&v);
        G[u][v]++;
        G[v][u]++;
        nodes_found[u]=nodes_found[v]=1;
       }
//    printadj();
      printf("Case #%d\n",k+1);
      tot_nodes=count_vertices(nodes_found);
      if(is_evendeg()) {
        dfs(u);
        trav_nodes=count_vertices(nodes_traversed);
        if(is_connected(tot_nodes,trav_nodes)) {
          for(i=0;i<m;i++)
            printf("%d  %d\n",print_u[i],print_v[i]);
        }
        else printf("some beads may be lost\n");
      }
      else printf("some beads may be lost\n");
      printf("\n");
  }
  return 0;
}

这段代码在那里给了我运行时错误，请查看代码。

Answer 1

您需要做的是形成任意循环，然后将所有循环连接在一起。您似乎只进行了一次深度优先遍历，这可能会给您一个欧拉回路，但它也可能给您一个欧拉回路的“捷径”。这是因为在欧拉回路通过不止一次的每个顶点（即，它与自身相交的地方），当深度优先遍历第一次到达那里时，它可能会选择直接返回深度起点的边第一次遍历。

因此，您的算法应该由两部分组成：

1. 查找所有循环
2. 将循环连接在一起

如果操作正确，您甚至不必检查所有顶点的度数是否相等，相反，您可以依靠这样一个事实，即如果步骤 1 或 2 不能再继续，则不存在欧拉循环。

参考实现 (Java)

由于您的问题中没有语言标签，因此我假设您可以为您提供 Java 参考实现。此外，我将使用术语“节点”而不是“顶点”，但这只是个人喜好（它提供更短的代码；））。

我将在这个算法中使用一个常量，我将从其他类中引用它：

public static final int NUMBER_OF_NODES = 50;

然后，我们需要一个 Edge 类来轻松构建我们的循环，它们基本上是边的链表：

public class Edge
{
    int u, v;
    Edge prev, next;

    public Edge(int u, int v)
    {
        this.u = u;
        this.v = v;
    }

    /**
     * Attaches a new edge to this edge, leading to the given node
     * and returns the newly created Edge. The node where the
     * attached edge starts doesn't need to be given, as it will
     * always be the node where this edge ends.
     * 
     * @param node The node where the attached edge ends.
     */
    public Edge attach(int node)
    {
        next = new Edge(this.v, node);
        next.prev = this;
        return next;
    }
}

然后，我们需要一个可以轻松加入两个循环的 Cycle 类：

public class Cycle
{
    Edge start;
    boolean[] used = new boolean[NUMBER_OF_NODES+1];

    public Cycle(Edge start)
    {
        // Store the cycle itself
        this.start = start;
        // And memorize which nodes are being used in this cycle
        used[start.u] = true;
        for (Edge e = start.next; e != start; e = e.next)
            used[e.u] = true;
    }

    /**
     * Checks if this cycle can join with the given cycle. That is
     * the case if and only if both cycles use a common node.
     * 
     * @return {@code true} if this and that cycle can be joined,
     *         {@code false} otherwise.
     */
    public boolean canJoin(Cycle that)
    {
        // Find a commonly used node
        for (int node = 1; node <= NUMBER_OF_NODES; node++)
            if (this.used[node] && that.used[node])
                return true;
        return false;
    }

    /**
     * Joins the given cycle to this cycle. Both cycles will be broken
     * at a common node and the paths will then be connected to each
     * other. The given cycle should not be used after this call, as the
     * list of used nodes is most probably invalidated, only this cycle
     * will be updated and remains valid.
     * 
     * @param that The cycle to be joined to this cycle.
     */
    public void join(Cycle that)
    {
        // Find the node where we'll join the two cycles
        int junction = 1;
        while (!this.used[junction] || !that.used[junction])
            junction++;
        // Find the join place in this cycle
        Edge joinAfterEdge = this.start;
        while (joinAfterEdge.v != junction)
            joinAfterEdge = joinAfterEdge.next;
        // Find the join place in that cycle
        Edge joinBeforeEdge = that.start;
        while (joinBeforeEdge.u != junction)
            joinBeforeEdge = joinBeforeEdge.next;
        // Connect them together
        joinAfterEdge.next.prev = joinBeforeEdge.prev;
        joinBeforeEdge.prev.next = joinAfterEdge.next;
        joinAfterEdge.next = joinBeforeEdge;
        joinBeforeEdge.prev = joinAfterEdge;
        // Update the used nodes
        for (int node = 1; node <= NUMBER_OF_NODES; node++)
            this.used[node] |= that.used[node];
    }

    @Override
    public String toString()
    {
        StringBuilder s = new StringBuilder();
        s.append(start.u).append(" ").append(start.v);
        for (Edge curr = start.next; curr != start; curr = curr.next)
            s.append("\n").append(curr.u).append(" ").append(curr.v);
        return s.toString();
    }
}

现在我们的实用程序类已经到位，我们可以编写实际的算法（尽管从技术上讲，算法的一部分是扩展路径（Edge.attach(int node)）并加入两个循环（Cycle.join(Cycle that)）。

/**
 * @param edges A variant of an adjacency matrix: the number in edges[i][j]
 *        indicates how many links there are between node i and node j. Note
 *        that this means that every edge contributes two times in this
 *        matrix: one time from i to j and one time from j to i. This is
 *        also true in the case of a loop: the link still contributes in two
 *        ways, from i to j and from j to i, even though i == j.
 */
public static Cycle solve(int[][] edges)
{
    Deque<Cycle> cycles = new LinkedList<Cycle>();
    // First, find a place where we can start a new cycle
    for (int u = 1; u <= NUMBER_OF_NODES; u++)
        for (int v = 1; v <= NUMBER_OF_NODES; v++)
            if (edges[u][v] > 0)
            {
                // The new cycle starts at the edge from u to v
                Edge first, last = first = new Edge(u, v);
                edges[last.u][last.v]--;
                edges[last.v][last.u]--;
                int curr = last.v;
                // Extend the list of edges until we're back at the start
                search: while (curr != u)
                {
                    // Find any edge that extends the last edge
                    for (int next = 1; next <= NUMBER_OF_NODES; next++)
                        if (edges[curr][next] > 0)
                        {
                            // We found an edge, attach it to the last one
                            last = last.attach(next);
                            edges[last.u][last.v]--;
                            edges[last.v][last.u]--;
                            curr = next;
                            continue search;
                        }
                    // We can't form a cycle anymore, which
                    // means there is no Eulerian cycle.
                    return null;
                }
                // Connect the end to the start
                last.next = first;
                first.prev = last;
                // Save it
                cycles.add(new Cycle(last));
                // And don't forget about the possibility that there are
                // more edges running from u to v, so v should be
                // re-examined in the next iteration.
                v--;
            }
    // Now we have put all edges into cycles,
    // we join them all together (if possible)
    merge: while (cycles.size() > 1)
    {
        // Join the last cycle with any of the previous ones
        Cycle last = cycles.removeLast();
        for (Cycle curr : cycles)
            if (curr.canJoin(last))
            {
                // Found one! Just join it and continue the merge
                curr.join(last);
                continue merge;
            }
        // No compatible cycle found, meaning there is no Eulerian cycle
        return null;
    }
    return cycles.getFirst();
}