locked
BFS on the Dictionary in C# RRS feed

  • Question

  • User-1592798427 posted

    Hi I am new to C# I need to implement a BFS search on the dictionary which generates key values pairs like

    81 - 70,72,68

    70 - 81,71

    71- 81,70

    68-81,70,71

    so its basically like 81 is the source room and 70,72,68 are the destination rooms

    I need a generate a list so that i need to cover all the rooms by passing only from source to destination

    Sample output path would be

    68->81->70->71

    please help me out. How to implement this

    Tuesday, August 23, 2016 12:48 AM

All replies

  • User-491950272 posted

    Greetings,

    Using Dictionary for this example might be very good. Use List<> or Queue instead as the dictionaries are KV pairs. So writing algorithms like these might be difficult. For Queue<> implementation of BFS, check out this post.

    Tuesday, August 23, 2016 6:45 AM
  • User-1592798427 posted
      var qrylist = new Dictionary<string, List<string>>();
                    qrylist = dic.GroupBy(c => c.Key).ToDictionary(group => group.Key, group => group.Select(c => c.Value).ToList());
    
    
                    List<List<string>> final = qrylist.Values.ToList();
    
                    data.Rules = qrylist;
                    ///
                    foreach (var p in qrylist.Keys)
                    {
                        Queue<string> traverseOrder = new Queue<string>();
                        Queue<string> Q = new Queue<string>();
                        HashSet<string> S = new HashSet<string>();
                        Q.Enqueue(p);
                        S.Add(p);
    
    
                        while (Q.Count != 0)
                        {
                            string v = Q.Dequeue();
                            traverseOrder.Enqueue(v);
                            foreach (var w in qrylist.Values.First())
                            {
                                if (!S.Contains(w))
                                {
                                    Q.Enqueue(w);
                                    S.Add(w);
                                }
                            }
                        }
                        while (traverseOrder.Count > 0)
                        {
                           string s = traverseOrder.Dequeue();
    
                            data.result = s.ToString();
                        }
                    }
             
    
    I have tried out using the queue for the traversal. But it does not return the path as I expected. 
    It is just returning only one room       

    Tuesday, August 23, 2016 2:18 PM
  • User303363814 posted

    Can you put some test data into dic and show us the code.  Run the code, show us the output.  Tell us what the output should be and why.

    Sunday, August 28, 2016 10:58 PM