CODEWITHSUNDEEP
c++matrixdepth-first-searchbreadth-first-searchadjacency-matrix
Lorraine
Lorraine

Reputation: 23

Apply breadth and depth first search on an adjacency matrix?

I'm given this adjacency matrix which I have to read from a text file, and supposed to return the result of reading it breadth-first and depth-first.

I know that breadth-first uses a FIFO queue and that depth-first uses a LIFO stack. I'm able to get these searches when I have the graph, and manually. I'm just not sure how to approach this on the computer, and using a matrix, on C++.

I would appreciate guidance on how to solve this problem. Some questions I have:

  1. Do I save the matrix from the text file into my program as a regular matrix?
  2. What to do once I have read the text file to display the result of the search?

Upvotes: 0

Views: 2140

Answers (2)

its4zahoor
its4zahoor

Reputation: 1821

ANS 1: Yes, it's better to read the input from the text file into a regular matrix. 

void MyGraph::csv_import()
    {
        int temp, i=0;
        string parsed;
        fstream file("input.csv");
        while (getline(file, parsed, ',')) {
            temp = stoi(parsed);
            arr[i/10][i%10] = temp; //10 x 10 Matrix
            i++;
        }
    }

ANS 2: Select a starting node, call the BFS to display results of search. for example(in my case)

void MyGraph::BFS(int v)
    {
        memset(visited, false, sizeof(visited);
        QQ.push(v);                         //push the starting vertex into queue
        visited[v] = true;                  //mark the starting vertex visited
        while (!QQ.empty())                 //until queue is not empty
        {
            v = QQ.front();                 //assign v the vertex on front of queue
            cout << v << "  ";              //print the vertex to be popped
            QQ.pop();                       //pop the vertex on front
            for (int c = 0; c< V; c++)      //V is the number of nodes
            {
                 //M[i][j] == 1, when i,j are connected
                if (M[v][c] == 1 && visited[c] == false) 
                {                           //if vertex has edge and is unvisited
                    QQ.push(c);             //push to the queue
                    visited[c] = true;      //mark it visited
                    Path[c] = p;            //assign the path length
                }
            }
        }
    }

Upvotes: 1

Yashwanth CB
Yashwanth CB

Reputation: 194

  1. Yes
  2. http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/

BFS: Note: for an undirected graph scanning upper or lower triangle of the matrix is enough. For a directed graph the whole matrix should be considered.

Step1: maintain an array of Boolean values for saving whether a node is visited or not.

Step2: implement a queue

Step3: start with any element and push it into the queue and Mark it as visited. Step4: In a loop Dequeue the top element in the queue..let it be x

For all unvisited neighbors of x..push them into the queue and Mark them as visited.

Do step4 until the queue is empty..

The graph traversal order is given at the time of pushing the elements into the queue.

I will explain dfs if I find time

Upvotes: 1

Related Questions