Version française
#include <vector>
using std::vector;
// A directed graph is a set of nodes, linked by arcs. Arcs are directed: they
// go from a node to another node.
// In this implementation, the nodes are the integers {0 .. num_nodes-1}.
//
// For example, the following graph:
//
// 0 <--- 1 <--> 3 ---> 4
// ^ | \ ^
// | v `----'
// '----- 2
//
// Can be obtained by:
// 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:
// At construction, the graph has no arcs.
explicit DirectedGraph(int num_nodes);
int NumNodes() const;
void AddArc(int from, int to);
// Returns the number of arcs originating from "node".
// In the example above, OutDegree(1) = 3, OutDegree(4) = 0.
int OutDegree(int node) const;
// Returns all the destination nodes that were added with arcs
// originating from "node".
// In the example above, Neighbors(1) is {0, 2, 3} and Neighbors(2) is {0}.
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 g1TO SUBMIT: graph.h, graph.cc
#include "graph.h"
// An undirected graph is just like a directed graph, but arcs are called
// "edges" and they don't have a direction: an edge (a, b) is present both
// in the adjacency list of a and the adjacency list of b.
class UndirectedGraph {
public:
explicit UndirectedGraph(int num_nodes);
void AddEdge(int a, int b);
int NumNodes() const;
int NumEdges() const;
int Degree(int node) const;
const vector<int>& Neighbors(int node) const;
private:
// TODO
// HINT: Use a DirectedGraph where you store each edge (a, b) as two arcs
// a->b and b->a !
};make u1TO SUBMIT: ugraph.h, ugraph.cc
#include "ugraph.h"
// Returns the number of sorted triples of nodes i<j<k such that
// (i,j), (j,k) and (k,i) are edges of the graph.
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);