Graph traversal (05_XBPDG)
- Coefficient : 1
- Hourly Volume: 16.0h (including 9.0h supervised)
- Labo : 9h supervised (and 1.5h unsupervised)
- Out-of-schedule personal work : 5.5h
AATs Lists
Description
Directed and undirected graphs:
- Theoretical elements: definitions, representations, adjacency matrix;
- Properties: paths, connectivity, strong connectivity, transitive closure;
Traversal:
- Breadth-first search, depth-first search;
- Shortest path in a weighted or unweighted graph: Ford and Dijkstra algorithms;
- A* algorithm.
Learning Outcomes AAv (AAv)
- AAv1 [heures: 16, B2,B3] : At the end of the course, each student will be able to correctly implement the relevant mathematical tools to solve optimal path calculation problems (depth, breadth, shortest via Ford or Dijkstra) in directed or undirected graphs, weighted or unweighted.
Assessment methods
Continuous assessment using the ENIBEXAM work environment used in the lab, and an assessment at the end of the course.
Key Words
Graphs, graph paths.
Prerequisites
Algorithms and Python-type language.