Function to perform breadth-first search (BFS) on a graph represented by an adjacency list
| 24 | // Function to perform breadth-first search (BFS) on a graph represented by an |
| 25 | // adjacency list |
| 26 | int BFS(const std::vector<std::vector<int>>& graph, |
| 27 | int root, |
| 28 | std::vector<int>& parents, |
| 29 | std::vector<std::pair<int, int>> banned_edges) { |
| 30 | int num_vertices = graph.size(); |
| 31 | |
| 32 | // Create a vector to store the visited status of each vertex |
| 33 | std::vector<bool> visited(num_vertices, false); |
| 34 | |
| 35 | // Create a vector to store the parent vertex for each vertex |
| 36 | parents.clear(); |
| 37 | parents.resize(num_vertices, -1); |
| 38 | parents[root] = root; |
| 39 | |
| 40 | // Create a queue for BFS traversal |
| 41 | std::queue<int> q; |
| 42 | |
| 43 | // Mark the start vertex as visited and enqueue it |
| 44 | visited[root] = true; |
| 45 | q.push(root); |
| 46 | |
| 47 | int counter = 0; |
| 48 | while (!q.empty()) { |
| 49 | int current_vertex = q.front(); |
| 50 | q.pop(); |
| 51 | |
| 52 | // Process the current vertex |
| 53 | // Traverse the adjacent vertices |
| 54 | for (int neighbor : graph[current_vertex]) { |
| 55 | if (std::find(banned_edges.begin(), |
| 56 | banned_edges.end(), |
| 57 | std::make_pair(current_vertex, neighbor)) != |
| 58 | banned_edges.end()) |
| 59 | continue; |
| 60 | if (std::find(banned_edges.begin(), |
| 61 | banned_edges.end(), |
| 62 | std::make_pair(neighbor, current_vertex)) != |
| 63 | banned_edges.end()) |
| 64 | continue; |
| 65 | |
| 66 | if (!visited[neighbor]) { |
| 67 | visited[neighbor] = true; |
| 68 | parents[neighbor] = current_vertex; |
| 69 | q.push(neighbor); |
| 70 | counter++; |
| 71 | } |
| 72 | } |
| 73 | } |
| 74 | |
| 75 | return counter; |
| 76 | } |
| 77 | |
| 78 | image_t MaximumSpanningTree(const ViewGraph& view_graph, |
| 79 | const std::unordered_map<image_t, Image>& images, |
no outgoing calls
no test coverage detected