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

Question

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

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

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

我再次想到一旦我遍历该路径就从邻接列表中删除节点(为了维护 euler 的属性(路径应该遍历一次))，但我正在使用 vector 来存储邻接列表但我没有知道如何从向量中删除特定元素。我在谷歌上搜索了一下，发现 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(循环那个))。

/**
 * @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();
}