6. Write a source code to implement the BFS algorithm for the graph in the below figure. Also, show its output as the order of nodes visited, and draw your adjacency list.

#include #include #include #include using namespace std;

// add your head files here

class Graph { /* Requirements: 1. Initialize the adjacency list with the given array 2. Wrong answer or wrong BFS algorithm will get 0 point 3. Please do not change the file name 4. Your code will be tested in this way: Graph g = new Graph() ## Check the order of nodes visited int[] res1 = g.bfsNodesArr() check1(res1) ## Check the adjacency list int[][] res2 = g.adjacencyList() check2(res2) */ public: vector> adjacency_list; vector nodes_list;

public Graph() { vector> edges {{0, 1}, {0, 2}, {0, 3}, {1, 4}, {1, 5}, {1, 6}, {4, 9}, {3, 7}, {3, 8}}; // initialize your adjacency list with the given array

}

vector BFSNodesList() { /* Requirements: 1. Get nodes in BFS order, which starts at "0" node. :rtype: vector (containing the order of nodes visited) */ // Insert your codes here

// Assign your result to nodes_list, which contains the values of nodes in list // Example: nodes_list = [6, 5, 4, 3, 2, 1] nodes_list = NULL; // please modify this line return nodes_list; }

vector> draw_adjacency_list() { /* Requirements: 1. Get adjacency list in 2D vector, while the i-th vector represent the neighbors of the i-th node :rtype: 2D vector

Here is the function to draw your adjacency list Example of result: self.adjacency_list = [[],[2,3],[1,3],[1,2],[]] 0 1->2->3 2->1->3 3->1->2 4

The following result will also be correct: (The order of adjacency nodes in i-th list doesn't matter) self.adjacency_list = [[],[2,3],[3,1],[1,2],[]] 0 1->2->3 2->3->1 3->1->2 4 */

// Insert your codes here

// Assign your result to adjacency_list, which contains the values of nodes in 2D-list // Example: nodes_list = [[],[2,3],[3,1],[1,2],[]] adjacency_list = NULL; // please modify this line return adjacency_list; } };