l'Algorithmie Avancée en Informatique: Développer les graphes : Définitions, représentations (matrices d'adjacence, listes d'adjacence)

Notions Fondamentales

1. Définition d'un Graphe

Un graphe $G$ est constitué d'un ensemble de nœuds (ou sommets) $V$ et d'un ensemble d'arêtes $E$ qui relient des paires de nœuds.

Graphe non orienté : Les arêtes n'ont pas de direction. Si u et v sont des nœuds et (u, v) est une arête, alors (u, v) est équivalente à (v, u).
Graphe orienté : Les arêtes ont une direction. Si (u, v) est une arête, alors (u, v) est différent de (v, u).

Représentations des Graphes

2. Matrice d'Adjacence

Une matrice d'adjacence est une matrice carrée de taille n × n, où n est le nombre de nœuds. Les éléments de la matrice indiquent la présence ou l'absence d'arêtes entre les nœuds.

Non orienté : La matrice est symétrique.
Orienté : La matrice peut ne pas être symétrique.

Exemple de Code en JavaScript :

// Création d'une matrice d'adjacence pour un graphe non orienté
function createAdjacencyMatrix(n) {
    let matrix = new Array(n).fill(0).map(() => new Array(n).fill(0));
    return matrix;
}

// Ajout d'une arête dans une matrice d'adjacence
function addEdge(matrix, u, v) {
    matrix[u][v] = 1;
    matrix[v][u] = 1; // Pour un graphe non orienté
}

// Affichage de la matrice d'adjacence
function printMatrix(matrix) {
    for (let row of matrix) {
        console.log(row.join(' '));
    }
}

// Exemple d'utilisation
let n = 5;
let adjMatrix = createAdjacencyMatrix(n);
addEdge(adjMatrix, 0, 1);
addEdge(adjMatrix, 0, 4);
addEdge(adjMatrix, 1, 2);
addEdge(adjMatrix, 1, 3);
addEdge(adjMatrix, 1, 4);
addEdge(adjMatrix, 2, 3);
addEdge(adjMatrix, 3, 4);
printMatrix(adjMatrix);

// Output:
// 0 1 0 0 1
// 1 0 1 1 1
// 0 1 0 1 0
// 0 1 1 0 1
// 1 1 0 1 0

3. Liste d'Adjacence

Une liste d'adjacence utilise un tableau où chaque élément est une liste qui contient les voisins d'un nœud donné. Cette représentation est plus efficace en termes de mémoire pour les graphes clairsemés.

Exemple de Code en JavaScript :

// Création d'une liste d'adjacence pour un graphe non orienté
function createAdjacencyList(n) {
    let list = new Array(n).fill(null).map(() => []);
    return list;
}

// Ajout d'une arête dans une liste d'adjacence
function addEdge(list, u, v) {
    list[u].push(v);
    list[v].push(u); // Pour un graphe non orienté
}

// Affichage de la liste d'adjacence
function printAdjacencyList(list) {
    for (let i = 0; i < list.length; i++) {
        console.log(`${i} -> ${list[i].join(', ')}`);
    }
}

// Exemple d'utilisation
let n = 5;
let adjList = createAdjacencyList(n);
addEdge(adjList, 0, 1);
addEdge(adjList, 0, 4);
addEdge(adjList, 1, 2);
addEdge(adjList, 1, 3);
addEdge(adjList, 1, 4);
addEdge(adjList, 2, 3);
addEdge(adjList, 3, 4);
printAdjacencyList(adjList);

// Output:
// 0 -> 1, 4
// 1 -> 0, 2, 3, 4
// 2 -> 1, 3
// 3 -> 1, 2, 4
// 4 -> 0, 1, 3

Exemples Vulgarisés

4. Matrice d'Adjacence : Le Plan de la Ville

Exemple :

Imagine que tu es un urbaniste et que tu dois planifier les routes d'une petite ville. Les intersections de la ville sont des nœuds et les routes sont des arêtes. Tu dessines un tableau où chaque case indique si une route existe entre deux intersections.

Exemple de Code en JavaScript :

// Création d'un plan de ville avec une matrice d'adjacence
function createCityPlan(n) {
    let plan = new Array(n).fill(0).map(() => new Array(n).fill(0));
    return plan;
}

// Ajout d'une route entre deux intersections
function addRoad(plan, u, v) {
    plan[u][v] = 1;
    plan[v][u] = 1; // Pour une route bidirectionnelle
}

// Affichage du plan de la ville
function printCityPlan(plan) {
    for (let row of plan) {
        console.log(row.join(' '));
    }
}

// Exemple d'utilisation
let n = 4; // Nombre d'intersections
let cityPlan = createCityPlan(n);
addRoad(cityPlan, 0, 1);
addRoad(cityPlan, 1, 2);
addRoad(cityPlan, 2, 3);
addRoad(cityPlan, 3, 0);
addRoad(cityPlan, 1, 3);
printCityPlan(cityPlan);

// Output:
// 0 1 0 1
// 1 0 1 1
// 0 1 0 1
// 1 1 1 0

5. Liste d'Adjacence : Le Réseau Social des Amis

Exemple :

Imagine que tu crées un réseau social pour suivre les amitiés entre les stagiaires d'une école. Chaque enfant est un nœud, et une amitié entre deux stagiaires est une arête. Tu utilises des listes pour noter qui sont les amis de chaque enfant.

Exemple de Code en JavaScript :

// Création d'un réseau social avec une liste d'adjacence
function createSocialNetwork(n) {
    let network = new Array(n).fill(null).map(() => []);
    return network;
}

// Ajout d'une amitié entre deux enfants
function addFriendship(network, u, v) {
    network[u].push(v);
    network[v].push(u); // Pour une amitié bidirectionnelle
}

// Affichage du réseau social
function printSocialNetwork(network) {
    for (let i = 0; i < network.length; i++) {
        console.log(`${i} -> ${network[i].join(', ')}`);
    }
}

// Exemple d'utilisation
let n = 4; // Nombre d'enfants
let socialNetwork = createSocialNetwork(n);
addFriendship(socialNetwork, 0, 1);
addFriendship(socialNetwork, 1, 2);
addFriendship(socialNetwork, 2, 3);
addFriendship(socialNetwork, 3, 0);
addFriendship(socialNetwork, 1, 3);
printSocialNetwork(socialNetwork);

// Output:
// 0 -> 1, 3
// 1 -> 0, 2, 3
// 2 -> 1, 3
// 3 -> 2, 0, 1

Ce cours permet de comprendre les graphes, leurs définitions et leurs représentations principales, à travers des exemples classiques et des histoires amusantes pour rendre l'apprentissage plus engageant. Les matrices d'adjacence et les listes d'adjacence sont des outils puissants pour modéliser et manipuler des graphes dans divers contextes.

Modifié le: mardi 18 février 2025, 06:03