Graphes et algorithme
Discovering and exploring graphs: part 1
Common thread problem and rules of the game
Common thread
Organization of the course
A “toy example”
Exo - Modeling the data with a graph
Course - Graph
Reminder on sets
First definition of a graph
Visual representation of a graph
Successor map (neighborhood)
Exo - Memory representation of a graph
Cours - Memory representation of a graph
Memory representation for the vertices of a graph
Memory representation of a subset of vertices: linked list and Boolean array
Memory representation of a graph using an array of linked lists
Memory reresentation of a graph by Boolean matrix
Memory reresentation of a graph by an array of arcs
Exo - One way graphs
Course - Symmetric and graphs
Exo - Implementing a first graph algorithm
Course - SYM Algorithm: computing the symmetric of a graph
General Knowledge Bonus - Some remarkable graphs
Discovering and exploring graphs: part 2
Common thread problem and rules of the game
Fil rouge
Organization of the course
A “toy example”: reminder
Exo - Successor search: dilation algorithm
Course - Exploration of successors: dilation
Exo - Paths
Course - Paths
Exo - Partial search
Course - Partial search of a graph
Exo - Graph search
Course - Graph search
Exo - Coding graph search algorithms
Course - Graph search algorithm
Course - Naive graph search algorithm
Course - Breadth-first search algorithm
Exo - Connectivity
Course - Connectivity
Connectivity (and strong connectivity)
Connected components (and strongly connected components)
A remarkable property of connected and strongly connected components
Exo - Coding connected component algorithm
Course - Connected Component and Strongly Connected Component Algorithms
Regroupement de données avec des graphes
Présentation du problème fil rouge et règles du jeu
Fil rouge
Organisation du cours
Exercices : cyber-profiler et composantes
\(k\)
-liées
Shortest paths
Goal and organization
Lecture notes
Exercises (understanding the lecture and discovering backtracking)
Practical work
Building and optimizing a spy network - part 1: arborescence
Common thread problem and rules of the game
Common thread
Organization of the course
A “toy example”
Exo - Modeling the data with a graph
Course - Edge-weighted graph
Exo - Sending a secret message without redundancy
Course - Trees and arborescences
Trees
Arborescences
Memory representation of an arborescence
Building and optimizing a spy network - part 2: minimum spanning tree
Common thread
Organization of the course
A “toy example”
Exo - Optimal solution for the toy example
Course - Minimum spanning tree
Situation
Formalization with graphs
Maximum spanning tree
Exo - Computing minimum spanning trees
Course - Kruskal’s Algorithm
Generic scheme for computing minimum spanning trees
Kruskal’s Algorithm
Choix des structures de données et Analyse de complexité
Proof of correctness of Kruskal’s Algorithm
To go further…
Graphes et algorithme
Docs
»
Index
Index