Рубрики

Алгоритм Флери для печати Eulerian Path или Circuit

Путь Эйлера — это путь в графе, который посещает каждый край ровно один раз. Эйлерова цепь — это эйлерова тропа, которая начинается и заканчивается в одной и той же вершине.

Мы настоятельно рекомендуем сначала прочитать следующий пост на Euler Path and Circuit.
http://espressocode.top/eulerian-path-and-circuit/

В вышеупомянутом посте мы обсуждали проблему выяснения, является ли данный граф эйлеровым или нет. В этом посте обсуждается алгоритм печати эйлеровых следов или схем.

Ниже приведен алгоритм Флери для печати эйлеров след или цикл (Источник REF1 ).

1. Убедитесь, что в графе 0 или 2 нечетных вершины.

2. Если есть 0 нечетных вершин, начните с любого места. Если есть 2 нечетных вершины, начните с одной из них.

3. Следуйте по краям по одному. Если у вас есть выбор между мостом и без моста, всегда выбирайте без моста .

4. Остановитесь, когда у вас кончатся края.

Идея состоит в том, чтобы «не сжигать мосты », чтобы мы могли вернуться к вершине и пересечь оставшиеся ребра. Например, давайте рассмотрим следующий график.

Есть две вершины с нечетной степенью, «2» и «3», мы можем начать путь с любой из них. Давайте начнем тур с вершины '2'.

Из вершины '2' выходят три ребра, какой из них выбрать? Мы не выбираем границу «2-3», потому что это мост (мы не сможем вернуться к «3»). Мы можем выбрать любой из оставшихся двух ребер. Допустим, мы выбрали «2-0». Мы удалим это ребро и переместимся в вершину '0'.

В вершине '0' есть только одно ребро, поэтому мы выбираем его, удаляем и переходим к вершине '1'. Эйлер тур становится «2-0 0-1».

В вершине '1' есть только одно ребро, поэтому мы выбираем его, удаляем и переходим к вершине '2'. Эйлер тур становится '2-0 0-1 1-2'

Опять же, есть только одно ребро из вершины 2, поэтому мы выбираем его, удаляем и переходим в вершину 3. Тур Эйлера становится «2-0 0-1 1-2 2-3»

Больше нет краев, поэтому мы остановимся здесь. Финальный тур 2-0 0-1 1-2 2-3.

Смотрите это для и это передних больше примеров.

Следующее — реализация C ++ вышеупомянутого алгоритма. В следующем коде предполагается, что данный граф имеет эйлерово след или схему. Основное внимание уделяется печати эйлеровых следов или схем. Мы можем использовать isEulerian (), чтобы сначала проверить, есть ли Eulerian Trail или Circuit в данном графе.

Сначала мы находим начальную точку, которая должна быть нечетной вершиной (если есть нечетные вершины), и сохраняем ее в переменной 'u'. Если есть нечетные нечетные вершины, мы начинаем с вершины '0'. Мы вызываем printEulerUtil () для печати тура Эйлера, начинающегося с u. Мы пересекаем все смежные вершины и, если есть только одна смежная вершина, мы сразу ее рассмотрим. Если имеется более одной смежной вершины, мы рассматриваем смежную v, только если ребро uv не является мостом. Как узнать, является ли данное ребро мостом? Посчитаем количество вершин, достижимых от вас. Мы удаляем ребро uv и снова подсчитываем число достижимых вершин из u. Если число достижимых вершин уменьшено, то ребро uv является мостом. Чтобы подсчитать достижимые вершины, мы можем использовать BFS или DFS, мы использовали DFS в приведенном выше коде. Функция DFSCount (u) возвращает количество вершин, достижимых из u.
Как только ребро обработано (включено в тур Эйлера), мы удаляем его из графика. Чтобы удалить ребро, мы заменяем запись вершины на -1 в списке смежности. Обратите внимание, что простое удаление узла может не сработать, поскольку код является рекурсивным, а родительский вызов может быть в середине списка смежности.

C / C ++

// Программа на C ++, печатающая Эйлерову тропу в заданном эйлеровом или полуэйлеровом графе
#include <iostream>
#include <string.h>
#include <algorithm>
#include <list>

using namespace std;

  
// Класс, представляющий неориентированный граф

class Graph

{

  int V;    // Количество вершин

  list<int> *adj;    // Динамический массив списков смежности

public:

    // Конструктор и деструктор

  Graph(int V)  { this->V = V;  adj = new list<int>[V];  }

  ~Graph()      { delete [] adj;  }

  

  // функции для добавления и удаления ребра

  void addEdge(int u, int v) {  adj[u].push_back(v); adj[v].push_back(u); }

  void rmvEdge(int u, int v);

  

  // Способы печати эйлерова тура

  void printEulerTour();

  void printEulerUtil(int s);

  

  // Эта функция возвращает количество вершин, достижимых из v. Это делает DFS

  int DFSCount(int v, bool visited[]);

  

  // Утилита для проверки правильности следующего ребра в

  // Эйлерова тропа или схема

  bool isValidNextEdge(int u, int v);

};

  
/ * Основная функция печати Eulerian Trail. Сначала находит странный

   вершина степени (если есть) и затем вызывает printEulerUtil ()

   напечатать путь * /

void Graph::printEulerTour()

{

  // Найти вершину с нечетной степенью

  int u = 0;

  for (int i = 0; i < V; i++)

      if (adj[i].size() & 1)

        {   u = i; break;  }

  

  // Печать тура, начиная с oddv

  printEulerUtil(u);

  cout << endl;

}

  
// Печатать тур Эйлера, начиная с вершины u

void Graph::printEulerUtil(int u)

{

  // Повторение для всех вершин, смежных с этой вершиной

  list<int>::iterator i;

  for (i = adj[u].begin(); i != adj[u].end(); ++i)

  {

      int v = *i;

  

      // Если ребро uv не удалено и это допустимое следующее ребро

      if (v != -1 && isValidNextEdge(u, v))

      {

          cout << u << "-" << v << "  ";

          rmvEdge(u, v);

          printEulerUtil(v);

      }

  }

}

  
// Функция, которая проверяет, можно ли рассматривать край ультрафиолета как следующий край в
// Эйлер Тоут

bool Graph::isValidNextEdge(int u, int v)

{

  // Край uv действителен в одном из следующих двух случаев:

  

  // 1) Если v единственная смежная вершина из u

  int count = 0;  // Хранить количество смежных вершин

  list<int>::iterator i;

  for (i = adj[u].begin(); i != adj[u].end(); ++i)

     if (*i != -1)

        count++;

  if (count == 1)

    return true;

  

  

  // 2) Если есть несколько смежных, то уф не является мостом

  // Выполните следующие шаги, чтобы проверить, является ли uv мостом

  

  // 2.a) количество вершин, достижимых от вас

  bool visited[V];

  memset(visited, false, V);

  int count1 = DFSCount(u, visited);

  

  // 2.b) Удалить ребро (u, v) и после удаления ребра посчитать

  // вершины достижимы из вас

  rmvEdge(u, v);

  memset(visited, false, V);

  int count2 = DFSCount(u, visited);

  

  // 2.c) Добавить ребро обратно на график

  addEdge(u, v);

  

  // 2.d) Если count1 больше, то edge (u, v) является мостом

  return (count1 > count2)? false: true;

}

  
// Эта функция удаляет края уф из графа. Это удаляет край
// замена значения примыкающей вершины на -1.

void Graph::rmvEdge(int u, int v)

{

  // Найти v в списке смежности u и заменить его на -1

  list<int>::iterator iv = find(adj[u].begin(), adj[u].end(), v);

  *iv = -1;

  

  // Найти вас в списке смежности v и заменить его на -1

  list<int>::iterator iu = find(adj[v].begin(), adj[v].end(), u);

  *iu = -1;

}

  
// Функция на основе DFS для подсчета достижимых вершин из v

int Graph::DFSCount(int v, bool visited[])

{

  // Пометить текущий узел как посещенный

  visited[v] = true;

  int count = 1;

  

  // Повторение для всех вершин, смежных с этой вершиной

  list<int>::iterator i;

  for (i = adj[v].begin(); i != adj[v].end(); ++i)

      if (*i != -1 && !visited[*i])

          count += DFSCount(*i, visited);

  

  return count;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

  // Давайте сначала создадим и протестируем графики, показанные на рисунке выше

  Graph g1(4);

  g1.addEdge(0, 1);

  g1.addEdge(0, 2);

  g1.addEdge(1, 2);

  g1.addEdge(2, 3);

  g1.printEulerTour();

  

  Graph g2(3);

  g2.addEdge(0, 1);

  g2.addEdge(1, 2);

  g2.addEdge(2, 0);

  g2.printEulerTour();

  

  Graph g3(5);

  g3.addEdge(1, 0);

  g3.addEdge(0, 2);

  g3.addEdge(2, 1);

  g3.addEdge(0, 3);

  g3.addEdge(3, 4);

  g3.addEdge(3, 2);

  g3.addEdge(3, 1);

  g3.addEdge(2, 4);

  g3.printEulerTour();

  

  return 0;

}

Джава

// Java-программа печати Eulerian Trail
// в данном эйлеровом или полуэйлеровом графе

import java.util.ArrayList;

  
// Неориентированный граф, использующий
// представление списка смежности

public class Graph {

  

    private int vertices; // Количество вершин

    private ArrayList<Integer>[] adj; // список смежности

  

    // Конструктор

    Graph(int numOfVertices)

    {

        // инициализировать количество вершин

        this.vertices = numOfVertices;

  

        // инициализировать список смежности

        initGraph();

    }

  

    // служебный метод для инициализации списка смежности

    @SuppressWarnings("unchecked")

    private void initGraph()

    {

        adj = new ArrayList[vertices];

        for (int i = 0; i < vertices; i++) 

        {

            adj[i] = new ArrayList<>();

        }

    }

  

    // добавить край уф

    private void addEdge(Integer u, Integer v)

    {

        adj[u].add(v);

        adj[v].add(u);

    }

  

    // Эта функция удаляет края уф из графа.

    private void removeEdge(Integer u, Integer v)

    {

        adj[u].remove(v);

        adj[v].remove(u);

    }

  

    / * Основная функция печати Eulerian Trail.

       Сначала он находит вершину нечетной степени (если есть

       любой), а затем вызывает printEulerUtil () для

       распечатать путь * /

    private void printEulerTour()

    {

        // Найти вершину с нечетной степенью

        Integer u = 0;

        for (int i = 0; i < vertices; i++)

        {

            if (adj[i].size() % 2 == 1)

            {

                u = i;

                break;

            }

        }

          

        // Печать тура, начиная с oddv

        printEulerUtil(u);

        System.out.println();

    }

  

    // Печатать тур Эйлера, начиная с вершины u

    private void printEulerUtil(Integer u)

    {

        // Повторение для всех вершин, смежных с этой вершиной

        for (int i = 0; i < adj[u].size(); i++)

        {

            Integer v = adj[u].get(i);

            // Если edge uv является допустимым следующим ребром

            if (isValidNextEdge(u, v)) 

            {

                System.out.print(u + "-" + v + " ");

                  

                // Этот край используется, поэтому удалите его сейчас

                removeEdge(u, v); 

                printEulerUtil(v);

            }

        }

    }

  

    // Функция, чтобы проверить, может ли край уф быть

    // рассматривается как следующее преимущество Euler Tout

    private boolean isValidNextEdge(Integer u, Integer v)

    {

        // Край уф действителен в одном из

        // следующие два случая:

  

        // 1) Если v единственная смежная вершина из u

        // т.е. размер списка смежных вершин равен 1

        if (adj[u].size() == 1) {

            return true;

        }

  

        // 2) Если есть несколько смежных, то

        // Уф не является мостом Выполните следующие шаги

        // проверить, является ли уф мостом

        // 2.a) количество вершин, достижимых от вас

        boolean[] isVisited = new boolean[this.vertices];

        int count1 = dfsCount(u, isVisited);

  

        // 2.b) Удалить ребро (u, v) и после удаления

        // ребро, количество вершин, достижимых от вас

        removeEdge(u, v);

        isVisited = new boolean[this.vertices];

        int count2 = dfsCount(u, isVisited);

  

        // 2.c) Добавить ребро обратно на график

        addEdge(u, v);

        return (count1 > count2) ? false : true;

    }

  

    // Функция на основе DFS для подсчета достижимости

    // вершины из v

    private int dfsCount(Integer v, boolean[] isVisited)

    {

        // Пометить текущий узел как посещенный

        isVisited[v] = true;

        int count = 1;

        // Повторение для всех вершин, смежных с этой вершиной

        for (int adj : adj[v])

        {

            if (!isVisited[adj])

            {

                count = count + dfsCount(adj, isVisited);

            }

        }

        return count;

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String a[])

    {

        // Давайте сначала создадим и протестируем

        // графики, показанные на рисунке выше

        Graph g1 = new Graph(4);

        g1.addEdge(0, 1);

        g1.addEdge(0, 2);

        g1.addEdge(1, 2);

        g1.addEdge(2, 3);

        g1.printEulerTour();

  

        Graph g2 = new Graph(3);

        g2.addEdge(0, 1);

        g2.addEdge(1, 2);

        g2.addEdge(2, 0);

        g2.printEulerTour();

  

        Graph g3 = new Graph(5);

        g3.addEdge(1, 0);

        g3.addEdge(0, 2);

        g3.addEdge(2, 1);

        g3.addEdge(0, 3);

        g3.addEdge(3, 4);

        g3.addEdge(3, 2);

        g3.addEdge(3, 1);

        g3.addEdge(2, 4);

        g3.printEulerTour();

    }

}

  
// Этот код предоставлен Химаншу Шехар

питон

# Программа Python для печати Эйлерова тропы в заданном эйлеровом или полуэйлеровом графе

   

from collections import defaultdict

   
# Этот класс представляет неориентированный граф, используя представление списка смежности

class Graph:

   

    def __init__(self,vertices):

        self.V= vertices #No. вершин

        self.graph = defaultdict(list) # словарь по умолчанию для хранения графика

        self.Time = 0

   

    # функция для добавления ребра на график

    def addEdge(self,u,v):

        self.graph[u].append(v)

        self.graph[v].append(u)

  

    # Эта функция удаляет края уф из графика

    def rmvEdge(self, u, v):

        for index, key in enumerate(self.graph[u]):

            if key == v:

                self.graph[u].pop(index)

        for index, key in enumerate(self.graph[v]):

            if key == u:

                self.graph[v].pop(index)

  

    # Функция на основе DFS для подсчета достижимых вершин из v

    def DFSCount(self, v, visited):

        count = 1

        visited[v] = True

        for i in self.graph[v]:

            if visited[i] == False:

                count = count + self.DFSCount(i, visited)         

        return count

  

    # Функция, чтобы проверить, может ли край уф считаться следующим ребром в

    # Эйлер Тур

    def isValidNextEdge(self, u, v):

        # Граница uv действительна в одном из следующих двух случаев:

   

          # 1) Если v единственная смежная вершина из u

        if len(self.graph[u]) == 1:

            return True

        else:

            «»»

             2) Если есть несколько смежных, то уф не является мостом

                 Выполните следующие шаги, чтобы проверить, является ли уф мост

   

            2.a) количество вершин, доступных из u '' '    

            visited =[False]*(self.V)

            count1 = self.DFSCount(u, visited)

  

            '' '2.b) Удалите край (u, v) и после удаления края посчитайте

                вершины, достижимые из u '' '

            self.rmvEdge(u, v)

            visited =[False]*(self.V)

            count2 = self.DFSCount(u, visited)

  

            # 2.c) Добавьте ребро обратно на график

            self.addEdge(u,v)

  

            # 2.d) Если count1 больше, то ребро (u, v) является мостом

            return False if count1 > count2 else True

  

  

    # Печать тура Эйлера, начиная с вершины и

    def printEulerUtil(self, u):

        # Повторить для всех вершин, смежных с этой вершиной

        for v in self.graph[u]:

            # Если край ультрафиолетовый не удаляется, и это действительный следующий край

            if self.isValidNextEdge(u, v):

                print("%d-%d " %(u,v)),

                self.rmvEdge(u, v)

                self.printEulerUtil(v)

  

  

      

    '' 'Основная функция, которая печатает Eulerian Trail. Сначала находит странный

   вершина степени (если есть) и затем вызывает printEulerUtil ()

   напечатать путь '' '

    def printEulerTour(self):

        # Найти вершину с нечетной степенью

        u = 0

        for i in range(self.V):

            if len(self.graph[i]) %2 != 0 :

                u = i

                break

        # Печать тура, начиная с нечетной вершины

        print ("\n")

        self.printEulerUtil(u)

  
# Создайте график, приведенный на диаграмме выше

  

g1 = Graph(4)

g1.addEdge(0, 1)

g1.addEdge(0, 2)

g1.addEdge(1, 2)

g1.addEdge(2, 3)

g1.printEulerTour()

  

  

g2 = Graph(3)

g2.addEdge(0, 1)

g2.addEdge(1, 2)

g2.addEdge(2, 0)

g2.printEulerTour()

  

g3 = Graph (5)

g3.addEdge(1, 0)

g3.addEdge(0, 2)

g3.addEdge(2, 1)

g3.addEdge(0, 3)

g3.addEdge(3, 4)

g3.addEdge(3, 2)

g3.addEdge(3, 1)

g3.addEdge(2, 4)

g3.printEulerTour()

  

  
# Этот код предоставлен Ниламом Ядавом

C #

// AC # программа print Eulerian Trail
// в данном эйлеровом или полуэйлеровом графе

using System;

using System.Collections.Generic;

  
// Неориентированный граф, использующий
// представление списка смежности

class Graph

{

    private int vertices; // Количество вершин

    private List<int>[] adj; // список смежности

  

    // Конструктор

    Graph(int numOfVertices)

    {

        // инициализировать количество вершин

        this.vertices = numOfVertices;

  

        // инициализировать список смежности

        initGraph();

    }

  

    // служебный метод для инициализации списка смежности

    private void initGraph()

    {

        adj = new List<int>[vertices];

        for (int i = 0; i < vertices; i++) 

        {

            adj[i] = new List<int>();

        }

    }

  

    // добавить край уф

    private void addEdge(int u, int v)

    {

        adj[u].Add(v);

        adj[v].Add(u);

    }

  

    // Эта функция удаляет края уф из графа.

    private void removeEdge(int u, int v)

    {

        adj[u].Remove(v);

        adj[v].Remove(u);

    }

  

    / * Основная функция печати Eulerian Trail.

    Сначала он находит вершину нечетной степени (если есть

    любой), а затем вызывает printEulerUtil () для

    распечатать путь * /

    private void printEulerTour()

    {

        // Найти вершину с нечетной степенью

        int u = 0;

        for (int i = 0; i < vertices; i++)

        {

            if (adj[i].Count % 2 == 1)

            {

                u = i;

                break;

            }

        }

          

        // Печать тура, начиная с oddv

        printEulerUtil(u);

        Console.WriteLine();

    }

  

    // Печатать тур Эйлера, начиная с вершины u

    private void printEulerUtil(int u)

    {

        // повторить для всех вершин

        // рядом с этой вершиной

        for (int i = 0; i < adj[u].Count; i++)

        {

            int v = adj[u][i];

              

            // Если edge uv является допустимым следующим ребром

            if (isValidNextEdge(u, v)) 

            {

                Console.Write(u + "-" + v + " ");

                  

                // Этот край используется, поэтому удалите его сейчас

                removeEdge(u, v); 

                printEulerUtil(v);

            }

        }

    }

  

    // Функция, чтобы проверить, может ли край уф быть

    // рассматривается как следующее преимущество Euler Tout

    private bool isValidNextEdge(int u, int v)

    {

        // Край уф действителен в одном из

        // следующие два случая:

  

        // 1) Если v единственная смежная вершина из u

        // т.е. размер списка смежных вершин равен 1

        if (adj[u].Count == 1) 

        {

            return true;

        }

  

        // 2) Если есть несколько смежных, то

        // Уф не является мостом Выполните следующие шаги

        // проверить, является ли уф мостом

        // 2.a) количество вершин, достижимых от вас

        bool[] isVisited = new bool[this.vertices];

        int count1 = dfsCount(u, isVisited);

  

        // 2.b) Удалить ребро (u, v) и после удаления

        // ребро, количество вершин, достижимых от вас

        removeEdge(u, v);

        isVisited = new bool[this.vertices];

        int count2 = dfsCount(u, isVisited);

  

        // 2.c) Добавить ребро обратно на график

        addEdge(u, v);

        return (count1 > count2) ? false : true;

    }

  

    // Функция на основе DFS для подсчета достижимости

    // вершины из v

    private int dfsCount(int v, bool[] isVisited)

    {

        // Пометить текущий узел как посещенный

        isVisited[v] = true;

        int count = 1;

          

        // Повтор для всех смежных вершин

        // к этой вершине

        foreach(int i in adj[v])

        {

            if (!isVisited[i])

            {

                count = count + dfsCount(i, isVisited);

            }

        }

        return count;

    }

  

    // Код драйвера

    public static void Main(String []a)

    {

        // Давайте сначала создадим и протестируем

        // графики, показанные на рисунке выше

        Graph g1 = new Graph(4);

        g1.addEdge(0, 1);

        g1.addEdge(0, 2);

        g1.addEdge(1, 2);

        g1.addEdge(2, 3);

        g1.printEulerTour();

  

        Graph g2 = new Graph(3);

        g2.addEdge(0, 1);

        g2.addEdge(1, 2);

        g2.addEdge(2, 0);

        g2.printEulerTour();

  

        Graph g3 = new Graph(5);

        g3.addEdge(1, 0);

        g3.addEdge(0, 2);

        g3.addEdge(2, 1);

        g3.addEdge(0, 3);

        g3.addEdge(3, 4);

        g3.addEdge(3, 2);

        g3.addEdge(3, 1);

        g3.addEdge(2, 4);

        g3.printEulerTour();

    }

}

  
// Этот код предоставлен PrinciRaj1992


Выход:

2-0  0-1  1-2  2-3
0-1  1-2  2-0
0-1  1-2  2-0  0-3  3-4  4-2  2-3  3-1

Обратите внимание, что приведенный выше код модифицирует данный граф, мы можем создать копию графа, если мы не хотим, чтобы данный граф был изменен.

Сложность времени: временная сложность вышеописанной реализации составляет O ((V + E) 2 ). Функция printEulerUtil () похожа на DFS и вызывает isValidNextEdge (), которая также выполняет DFS два раза. Временная сложность DFS для представления списка смежности составляет O (V + E). Следовательно, общая сложность времени составляет O ((V + E) * (V + E)), которая может быть записана как O (E 2 ) для связного графа.

Алгоритм Гирхольцера находит в O (V + E) время лучших алгоритмов для печати тура Эйлера.

Ссылки:
http://www.math.ku.edu/~jmartin/courses/math105-F11/Lectures/chapter5-part2.pdf
http://en.wikipedia.org/wiki/Eulerian_path#Fleury.27s_algorithm

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Алгоритм Флери для печати Eulerian Path или Circuit

0.00 (0%) 0 votes