C++ 8. Write a program to implement Fleury’s algorithm as described in this chap

Question

C++

8. Write a program to implement Fleury’s algorithm as described in this chapter

Page 721 http://btechcsrc.weebly.com/uploads/2/5/4/7/25473675/data_structures_using_c_dsmalik.pdf

Fleury’s Algorithm

Step 1. Choose a vertex v as the starting vertex for the circuit and choose an edge e with
v as one of the end vertices.

Step 2. If the other end vertex u of the edge e is also v, go to Step 3. Otherwise, choose
an edge e1 different from e with u as one of the end vertices. If the other vertex u1 of e1 is
v, go to Step 3; otherwise, choose an edge e2 different from e and e1 with u1 as one of the
end vertices and repeat Step 2.

Step 3. If the circuit T1 obtained in Step 2 contains all the edges, then stop. Otherwise,
choose an edge ej different from the edges of T1 such that one of the end vertices of ej
say, w is a member of the circuit T1.

FIGURE 12-25 Graph of the Ko¨ nigsberg bridge problem with two additional bridges
Euler Circuits | 721

Step 4. Construct a circuit T2 with starting vertex w, as in Steps 1 and 2, such that all the
edges of T2 are different from the edges in the circuit T1.

Step 5. Construct the circuit T3 by inserting the circuit T2 at w of the circuit T1. Now go
to Step 3 and repeat Step 3 with the circuit T3.
Next, we illustrate how Fleury’s algorithm works. Consider the graph of Figure 12-26.
Let us apply Fleury’s algorithm to find an Eulerian circuit.
First, select vertex 0 and form the circuit: T1: (0, e1, 1, e3, 2, e2, 0).
Next, select vertex 1 and edge e4. Construct the circuit: C1: (1, e4, 2, e6, 6, e7, 3, e5, 1).
Then form the circuit: T2: (0, e1, C1, e3, 2, e2, 0).
Circuit T2 does not contain all the edges of the given graph. Now choose vertex 6 and
edge e8 and form the circuit: C2: (6, e8, 6).
Now construct the circuit: T3: (0, e1, 1, e4, 2, e6, C2, e7, 3, e5, 1, e3, 2, e2, 0).
This circuit also does not contain all the edges. Select now vertex 3 and edge e11. Form
the circuit: C3: (3, e11, 4, e10, 5, e9, 3).
Next, construct the circuit: T4: (0, e1,1, e4, 2, e6, C2, e7, C3, e5, 1, e3, 2, e2, 0).
Circuit T4 contains all the vertices and all the edges of the given graph and, hence, it is an
Euler circuit.

Explanation / Answer

1. pick any vertex to start
2. from that vertex pick an edge to traverse (see below for important rule)
3. darken that edge, as a reminder that you can't traverse it again
4. travel that edge, coming to the next vertex
5. repeat 2-4 until all edges have been traversed, and you are back at the starting vertex

at each stage of the algorithm:

Notes:

#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);


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


bool isValidNextEdge(int u, int v);
};

void Graph::printEulerTour()
{

int u = 0;
for (int i = 0; i < V; i++)
      if (adj[i].size() & 1)
        {   u = i; break; }


printEulerUtil(u);
cout << endl;
}

void Graph::printEulerUtil(int u)
{
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{
      int v = *i;

    
      if (v != -1 && isValidNextEdge(u, v))
      {
          cout << u << "-" << v << " ";
          rmvEdge(u, v);
          printEulerUtil(v);
      }
}
}

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

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;



bool visited[V];
memset(visited, false, V);
int count1 = DFSCount(u, visited);


rmvEdge(u, v);
memset(visited, false, V);
int count2 = DFSCount(u, visited);


addEdge(u, v);

return (count1 > count2)? false: true;
}

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

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

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

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;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.