Fleury's Algorithm Solution


  • 0

    This solution is long and not fast, But it is a simple implementation of Fleury's algorithm.
    https://en.wikipedia.org/wiki/Eulerian_path (Read about Fleury's algorithm here) it is very simple.

    I created a Vertex class to represent the graph.
    Then Created two graphs representing flights.
    First one is the directed graph of the itinerary.
    Second is an undirected version of the First graph to detect connectivity. (I added two edges in opposite directions for every edge in the first graph)
    In each iteration I remove an edge and check if graph is still connected and I continue to do this until all edges are removed.

            private class Vertex : IComparable<Vertex>, IComparable
            {
                public Vertex(string name)
                {
                    Name = name;
                    Neighbours = new List<Vertex>();
                }
                public string Name { private set; get; }
                public List<Vertex> Neighbours { private set; get; }
    
                public int CompareTo(object obj)
                {
                    return CompareTo((Vertex)obj);
                }
    
                public int CompareTo(Vertex other)
                {
                    return this.Name.CompareTo(other.Name);
                }
            }
    
            private bool IsGraphConnected(List<Vertex> vertexes, Vertex s)
            {
                HashSet<Vertex> visited = new HashSet<Vertex>();
                Queue<Vertex> visit = new Queue<Vertex>(vertexes.Count);
                visit.Enqueue(s);
    
                while (visit.Count > 0)
                {
                    Vertex v = visit.Dequeue();
                    if (!visited.Contains(v))
                    {
                        visited.Add(v);
                        foreach(Vertex u in v.Neighbours)
                        {
                            if (!visited.Contains(u)) visit.Enqueue(u);
                        }
                    }
                }
                return visited.Count == vertexes.Count;
            }
    
            public IList<string> FindItinerary(string[,] tickets)
            {
                List<string> path = new List<string>();
    
                int len = tickets.GetLength(0);
                Dictionary<string, Vertex> vertexes = new Dictionary<string, Vertex>();
                Dictionary<string, Vertex> vertexes2 = new Dictionary<string, Vertex>();
    
                for (int i=0; i<len; i++)
                {
                    Vertex s,s2;
                    if (vertexes.ContainsKey(tickets[i, 0]))
                    {
                        s = vertexes[tickets[i, 0]];
                        s2 = vertexes2[tickets[i, 0]];
                    }
                    else
                    {
                        s = new Vertex(tickets[i, 0]);
                        vertexes.Add(tickets[i, 0], s);
                        s2 = new Vertex(tickets[i, 0]);
                        vertexes2.Add(tickets[i, 0], s2);
                    }
    
                    Vertex e,e2;
                    if (vertexes.ContainsKey(tickets[i, 1]))
                    {
                        e = vertexes[tickets[i, 1]];
                        e2 = vertexes2[tickets[i, 1]];
                    }
                    else
                    {
                        e = new Vertex(tickets[i, 1]);
                        vertexes.Add(tickets[i, 1], e);
                        e2 = new Vertex(tickets[i, 1]);
                        vertexes2.Add(tickets[i, 1], e2);
                    }
                    s.Neighbours.Add(e);
    
                    s2.Neighbours.Add(e2);
                    e2.Neighbours.Add(s2);
                }
    
                foreach (KeyValuePair<string, Vertex> pair in vertexes) pair.Value.Neighbours.Sort();
    
                List<Vertex> vertexList2 = vertexes2.Values.ToList();
                Vertex w = vertexes["JFK"];
    
                while (w.Neighbours.Count > 0)
                {
                    for( int i=0; i<w.Neighbours.Count; i++)
                    {
                        Vertex u = w.Neighbours.ElementAt(i);
    
                        //remove from second graph
                        Vertex w2 = vertexes2[w.Name];
                        Vertex u2 = vertexes2[u.Name];
    
                        w2.Neighbours.Remove(u2);
                        u2.Neighbours.Remove(w2);
    
                        if (w2.Neighbours.Count == 0)
                        {
                            vertexList2.Remove(w2);
                        }
    
                        bool connected = IsGraphConnected(vertexList2, u2);
                        if (connected)
                        {
                            path.Add(w.Name);
                            w.Neighbours.Remove(u);
                            w = u;                        
                            break;
                        }
                        else
                        {
                            if (i == w.Neighbours.Count - 1) return null;
                            w2.Neighbours.Add(u2);
                            u2.Neighbours.Add(w2);
                        }
                    }
                }
                path.Add(w.Name);
                return path;
            }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.