-
Reprenez les fichiers graph.h, graph.cc, ugraph.h et ugraph.cc
faits lors du TD 1.
Implémentez dans un fichier bfs.1.cc la fonction BFS() décrite dans le fichier bfs.1.h:
#include "ugraph.h"
// Runs a Breadth-First-Search on the graph, starting from node "src".
// See https://en.wikipedia.org/wiki/Breadth-first_search .
// Returns a vector of size N (N is the number of nodes of the
// graph) representing the "parent" tree: parent[i] is the parent of
// node #i in the BFS tree. The parent of "src" is itself, and the
// parent of a node that wasn't reached by the BFS exploration is -1.
vector<int> BFS(const UndirectedGraph& graph, int src);
La complexité devra être O(M + N), où M est le nombre d'arcs et N le nombre de noeuds.
Utilisez une file de priorité deque de la librairie standard (#include <deque>). Les méthodes dont vous avez besoin sont :
- file.empty(): tester si la file est vide
- file.front(): renvoyer la tête de file
- file.push_back(elt): ajouter un élément en fin de file
- file.pop_front(): retirer la tête de file
Test:
rm test.tar.gz; wget --no-cache http://fabien.viger.free.fr/oc/td2/test.tar.gz
tar xf test.tar.gz
make bfs.1
RENDU: bfs.1.cc
-
Implémentez la fonction GetBfsDistances() décrite dans le fichier bfs.2.h:
#include <vector>
using std::vector;
// Extracts the distances of each node in the given BFS tree, which
// is the returned format described in bfs.1.h
// Eg. in the following tree, whose root is "2":
//
// .---- 4
// v
// 2 <-- 3 <-- 1
// ^
// '---- 0 <-- 5
//
// The bfs tree is represented by the following 'parent' vector:
// [2, 3, 2, 2, 3, 0]
// And the distance vector should be:
// [1, 2, 0, 1, 2, 2]
//
// If a node was not reached by the BFS, its parent is -1, and its distance
// should also be -1.
vector<int> GetBfsDistances(const vector<int>& parents);
Comment faire pour obtenir une complexité de O(N), où N le nombre de noeuds ?
Test: make bfs.2
RENDU: bfs.2.cc
-
Implémentez la fonction GetShortestPathFromRootedTree()
décrite dans le fichier bfs.3.h:
#include <vector>
using std::vector;
// Returns the shortest path, from the source of a BFS to the given target node.
// The argument is the target node and the BFS "parent" tree.
// If the target node was not reached by the BFS, the returned path should be
// empty.
// Example: using the same example as in bfs.2.h, with BFS 'parent' tree:
// [2, 3, 2, 2, 3, 0]
// Then:
// - the shortest path to node #4 should be: [2, 3, 4]
// - the shortest path to node #0 should be: [2, 0]
// - the shortest path to node #5 should be: [2, 0, 5]
// - the shortest path to node #2 should be: [2]
vector<int> GetShortestPathFromRootedTree(const vector<int>& parent, int target);
Vous pourriez avoir besoin de la fonction reverse (#include <algorithm>) qui renverse l'ordre des éléments d'un vecteur : reverse(vec.begin(), vec.end())
Test: make bfs.3
RENDU: bfs.3.cc
