English version
#include <vector>
using std::vector;
// Un graphe dirigé est un ensemble de noeuds, liés par des arcs.
// Chaque arc a une direction: il va d'un noeud vers un autre.
// Dans cette implementation, les noeuds sont les entiers {0 .. num_nodes-1}.
//
// Par exemple, ce graphe:
//
// 0 <--- 1 <--> 3 ---> 4
// ^ | \ ^
// | v `----'
// '----- 2
//
// Peut être obtenu en faisant:
// DirectedGraph g(5);
// g.AddArc(1, 0);
// g.AddArc(1, 3);
// g.AddArc(3, 1);
// g.AddArc(2, 0);
// g.AddArc(1, 2);
// g.AddArc(3, 4);
// g.AddArc(3, 4);
//
class DirectedGraph {
public:
// Après sa construction, un graphe n'a initialement pas d'arcs.
explicit DirectedGraph(int num_nodes);
int NumNodes() const; // Renvoie le nombre de noeuds
void AddArc(int from, int to); // Ajoute un arc from → to
// Renvoie le nombre d'arcs sortant du noeud "node".
// Dans l'exemple ci-dessus, OutDegree(1) = 3, OutDegree(4) = 0.
int OutDegree(int node) const;
// Renvoie tous les voisins sortants de "node", i.e. tous les
// noeuds X qui ont été ajoutés avec AddAdrc(node, X).
const vector<int>& Neighbors(int node) const;
private:
// TODO
};rm test.tar.gz; wget --no-cache http://fabien.viger.free.fr/oc/td1/test.tar.gz tar xf test.tar.gz make g1RENDU: graph.h, graph.cc
#include "graph.h"
// Un graph non dirigé est comme un graph dirigé, mais ses arcs sont appelés
// "arêtes" et n'ont pas de direction: une arête (a, b) est matérialisée à la
// fois dans la liste d'adjacence de a et dans celle de b.
class UndirectedGraph {
public:
explicit UndirectedGraph(int num_nodes);
void AddEdge(int a, int b); // Ajoute une arête au graphe.
int NumNodes() const;
int NumEdges() const;
int Degree(int node) const;
const vector<int>& Neighbors(int node) const;
private:
// TODO
// INDICE: Utilisez un DirectedGraph, et stockez-y chaque arête (a, b) comme 2
// arcs a→b et b→a !
};make u1RENDU: ugraph.h, ugraph.cc
#include "ugraph.h"
// Renvoie le nombre de triplets ordonnés i<j<k tels que
// (i,j), (j,k) et (k,i) sont des arêtes du graphe.
int NumTriangles(const UndirectedGraph& graph);
#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);#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);#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);#include "vgraph.h"
// Runs a Dijkstra search on the graph, starting from node "src".
// See https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm .
// Returns the same "parent" vector as BFS() in bfs.1.h.
vector<int> Dijkstra(const DirectedGraph& graph, int src);