CODEWITHSUNDEEP
c#graph
Francesco Bonizzi
Francesco Bonizzi

Reputation: 5302

BFS on a non weighted directed graph. How to return a list of the path between A and B

I have a grid represented by a graph. Each "node" is called Cell.

What I want in output is a path from A to B. I wrote on the console the output and I see that it is wrong. In particular it seems that it produces a path that "jumps" a lot, in the meaning that from one node to the next one there isn't a direct link.

If working, I would just need a path from A to B, not the path to reach every node.

What's wrong with my code?

Cell is an object that contains a List<Cell> NearCells with the reference of all adiacent cells.

    private List<Cell> FindPath(Cell A, Cell B)
    {
        List<Cell> path = new List<Cell>();
        List<Cell> visited = new List<Cell>();

        path.Add(A);

        while (path.Count != 0)
        {
            Cell c = path[0];
            path.RemoveAt(0);

            visited.Add(c);

            if (c == B)
                return path;

            foreach (Cell near in c.NearCells)
            {
                    if (!visited.Contains(near))
                    {
                        visited.Add(near);
                        path.Add(near);
                    }
            }

        }

        return path;
    }

Upvotes: 1

Views: 341

Answers (1)

Rodrigo L&#243;pez
Rodrigo L&#243;pez

Reputation: 4259

The path variable in your code, will only return the nodes that you queued but not checked yet, that by any means does NOT represents the path between A and B. To achieve that you should create a map that stores the parent of each node, and when you find the match you run throughout this map until you reach the start node, building a list while you do that. This list however will be reversed, you will need to fix that.

Having these points in mind, you should do something like this:

private List<Cell> FindPath(Cell A, Cell B)
{
    var parent = new Dictionary<Cell, Cell>();

    List<Cell> queue = new List<Cell>();
    List<Cell> visited = new List<Cell>();

    queue.Add(A);
    parent.Add(A, null);

    while (queue.Count != 0)
    {
        Cell c = queue[0];
        queue.RemoveAt(0);

        visited.Add(c);

        if (c == B)
            break;

        foreach (Cell near in c.NearCells)
        {                    
            if (!visited.Contains(near))
            {
                parent.Add(near, c);
                visited.Add(near);
                queue.Add(near);
            }
        }
    }

    List<Cell> path = new List<Cell>();

    if(parent.ContainsKey(B))
    {
        Cell backTrack = B;
        do
        {
            path.Add(backTrack);
            backTrack = parent[backTrack];
        }
        while (backTrack != null);
        path.Reverse();
    }
    return path;
}

Upvotes: 3

Related Questions