Skip to content

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.

Resources