CODEWITHSUNDEEP
c#breadth-first-searchadjacency-matrix
beginner
beginner

Reputation: 2032

BFS in Adjacency Matrix

Using the following code, when I call the bfs method, I get a result of 123465247. How should I declare and use a visited variable so that the output will become 1234657? 

class Graph
{
    public int[] graph1VertexList = new int[] {1,2,3,4,5,6,7};
    public int[,] graph1=new int[7,7];

    public Graph()
    {
        //for the graph1
        graph1[0, 1] = 1;
        graph1[0, 2] = 1;
        graph1[1, 3] = 1;
        graph1[2, 5] = 1;
        graph1[3, 4] = 1;
        graph1[4, 1] = 1;
        graph1[5, 3] = 1;
        graph1[5, 6] = 1;
    }


    public void bfs()
    {
        Console.Write(graph1VertexList[0]);//print the first value
        for(int i = 0; i < graph1VertexList.Length; i++)
        {
            for(int z = 0; z < graph1VertexList.Length; z++)
            {
                if (graph1[i, z] == 1)
                {
                    Console.Write(graph1VertexList[z]);
                }
            }
        }
    }

}

Upvotes: 1

Views: 791

Answers (1)

Codor
Codor

Reputation: 17605

You should introduce a boolean array to indicate whether a certain vertex has already been visited. Furthermore, the array should be checked if an edge is followed and updated after doing so. This can be done as follows.

public int[] graph1VertexList = new int[] { 1, 2, 3, 4, 5, 6, 7 };
public int[,] graph1 = new int[7, 7];

public bool[] visited = new bool[7]; // new array, initialized to false

public void bfs()
{
    Console.Write(graph1VertexList[0]);//print the first value
    for (int i = 0; i < graph1VertexList.Length; i++)
    {
        for (int z = 0; z < graph1VertexList.Length; z++)
        {
            if (graph1[i, z] == 1 && !visited[z])   // check for visit
            {
                visited[z] = true;                  // mark as visited
                Console.Write(graph1VertexList[z]);
            }
        }
    }
}

Upvotes: 1

Related Questions