Grafrepresentation: grannlistor

En graf består av noder (vertices) och kanter (edges). Till skillnad från träd kan grafer ha cykler och separata komponenter. Kanter kan vara riktade eller oriktade och bära vikter såsom avstånd eller kostnad. Välj representation utifrån operationerna.

Grannlista eller matris

I en grannlista lagrar varje nod sina grannar. En graf med V noder och E kanter kräver O(V + E) lagring för listorna med vanlig indexering. En grannmatris har V gånger V positioner och använder O(V²) minne även för glesa grafer. Med matris kan man kontrollera om en viss kant finns på O(1), men att hitta alla grannar kostar normalt O(V).

Litet exempel

För en oriktad graf med kanterna A-B, A-D och B-C får vi A: [B, D], B: [A, C], C: [B], D: [A]. Varje oriktad kant finns i två grannlistor. En riktad kant A → B finns bara i A:s utgående lista om ingen separat omvänd representation lagras.

C#

C# | AdjacencyList.cs

// Undirected graph: 0-A, 1-B, 2-C, 3-D
var adjacency = new List<int>[]
{
    new() { 1, 3 }, // A
    new() { 0, 2 }, // B
    new() { 1 },    // C
    new() { 0 }     // D
};

C++

C++ | AdjacencyList.cpp

#include <vector>
// Undirected graph: 0-A, 1-B, 2-C, 3-D
std::vector<std::vector<int>> adjacency = {
    {1, 3}, // A
    {0, 2}, // B
    {1},    // C
    {0}     // D
};

Sökning och fallgropar

BFS och DFS behöver komma åt varje nods grannar. Grannlistor låter algoritmerna undersöka kanter i förhållande till deras antal. I en frånkopplad graf når en enda startnod bara sin komponent. Vill du täcka alla komponenter måste du starta om från varje obesökt nod. Bestäm hur dubblettkanter, självloopar och ogiltiga nodindex ska hanteras innan extern indata behandlas.

Övning: Rita en cykel med fyra noder, skriv grannlistorna och förklara varför en naiv rekursiv sökning utan visited-markering kan fortsätta för alltid.

Läs vidare om BFS och DFS.