Vereinfachter PageRank in C++ mit Adjazenzliste

Einführung: Was ist PageRank und warum ist es heute noch relevant?

Im späten 20. Jahrhundert entwickelten Larry Page und Sergey Brin an der Stanford University den PageRank-Algorithmus, um die Relevanz von Webseiten zu bestimmen. Heute, im Mai 2026, ist PageRank nicht nur ein historischer Meilenstein, sondern auch die Grundlage vieler moderner Suchmaschinen und Empfehlungssysteme. Ob du nun eine Suchmaschine für ein Schulprojekt baust oder die Prinzipien hinter Googles Ranking verstehen willst – dieser Algorithmus ist ein Muss.

In diesem Tutorial lernst du, wie du einen vereinfachten PageRank-Algorithmus in C++ implementierst. Wir verwenden eine Adjazenzliste, um das Web als gerichteten Graphen darzustellen, und berechnen die Ränge mittels Power-Iterationen. Der Fokus liegt auf der praktischen Umsetzung, nicht auf der Theorie – du wirst einen funktionierenden Code schreiben, der aus Eingabedaten die PageRank-Werte berechnet.

Das Problem verstehen: Web als Graph

Stell dir das Internet als einen riesigen gerichteten Graphen vor: Jede Webseite ist ein Knoten, jeder Hyperlink eine Kante. Die Idee hinter PageRank ist einfach: Eine Seite ist wichtig, wenn viele wichtige Seiten auf sie verlinken. Der Algorithmus berechnet die Wichtigkeit (den Rang) jeder Seite iterativ.

In diesem Projekt (typisch für Kurse wie COP3530) bekommst du eine Liste von Paaren from_page to_page und eine Anzahl von Power-Iterationen p. Deine Aufgabe ist es, die Ränge nach p Iterationen zu berechnen und alphabetisch sortiert auszugeben.

Warum Adjazenzliste und nicht Adjazenzmatrix?

Für große Graphen mit Millionen von Knoten (wie das echte Web) ist eine Adjazenzmatrix viel zu speicherintensiv. Eine Adjazenzliste speichert nur die vorhandenen Kanten und ist daher effizienter. In diesem Projekt wird die Verwendung einer Adjazenzmatrix sogar mit Punktabzug bestraft – also bleiben wir bei der Liste.

Schritt 1: Datenstrukturen entwerfen

Zunächst brauchen wir eine Klasse Graph, die die Adjazenzliste und die Ränge verwaltet. Wir verwenden std::unordered_map für die Knoten (Webseiten-URLs) und std::vector für die ausgehenden Kanten.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <iomanip>

class Graph {
private:
    std::unordered_map<std::string, std::vector<std::string>> adjList;
    std::unordered_map<std::string, double> rank;
    std::unordered_map<std::string, int> outDegree;
public:
    void addEdge(const std::string& from, const std::string& to);
    void PageRank(int p);
    void printRanks();
};

Die rank-Map speichert den aktuellen Rang jedes Knotens, und outDegree die Anzahl der ausgehenden Kanten (wird für die Verteilung benötigt).

Schritt 2: Kanten hinzufügen

Die Methode addEdge fügt eine gerichtete Kante hinzu. Beachte: Wenn ein Knoten keine ausgehenden Kanten hat, bleibt sein outDegree 0 – das ist wichtig für die Rangberechnung.

void Graph::addEdge(const std::string& from, const std::string& to) {
    adjList[from].push_back(to);
    outDegree[from]++;
    // Stelle sicher, dass auch der Zielknoten in den Maps existiert
    if (rank.find(from) == rank.end()) rank[from] = 0.0;
    if (rank.find(to) == rank.end()) rank[to] = 0.0;
    if (outDegree.find(to) == outDegree.end()) outDegree[to] = 0;
}

Schritt 3: PageRank-Algorithmus implementieren

Der Algorithmus startet mit gleichen Rängen für alle Seiten: 1/N, wobei N die Anzahl der Knoten ist. Dann führen wir p Power-Iterationen durch. In jeder Iteration berechnen wir den neuen Rang jedes Knotens als Summe der Beiträge aller eingehenden Kanten. Der Beitrag einer Seite u zu einer Seite v ist rank[u] / outDegree[u].

void Graph::PageRank(int p) {
    int N = rank.size();
    double initialRank = 1.0 / N;
    for (auto& pair : rank) {
        pair.second = initialRank;
    }
    for (int iter = 0; iter < p; ++iter) {
        std::unordered_map<std::string, double> newRank;
        for (auto& pair : rank) {
            newRank[pair.first] = 0.0;
        }
        // Für jede Seite u, verteile ihren Rang an ihre Nachbarn
        for (const auto& pair : adjList) {
            const std::string& u = pair.first;
            const auto& neighbors = pair.second;
            if (outDegree[u] == 0) continue; // keine ausgehenden Kanten
            double contribution = rank[u] / outDegree[u];
            for (const std::string& v : neighbors) {
                newRank[v] += contribution;
            }
        }
        // Seiten ohne eingehende Kanten erhalten Rang 0 (oder Dämpfungsfaktor – hier vereinfacht)
        rank = newRank;
    }
}

Hinweis: In der vereinfachten Version wird kein Dämpfungsfaktor verwendet (wie im Original). Das ist für dieses Projekt ausreichend. Für eine vollständige Implementierung müsstest du einen Dämpfungsfaktor (z.B. 0.85) und Teleportation berücksichtigen.

Schritt 4: Ausgabe der Ränge

Die Ränge werden in alphabetischer Reihenfolge der URLs ausgegeben, auf zwei Dezimalstellen gerundet.

void Graph::printRanks() {
    std::vector<std::string> pages;
    for (const auto& pair : rank) {
        pages.push_back(pair.first);
    }
    std::sort(pages.begin(), pages.end());
    for (const std::string& page : pages) {
        std::cout << page << " " << std::fixed << std::setprecision(2) << rank[page] << std::endl;
    }
}

Schritt 5: Hauptprogramm

Die Eingabe erfolgt über std::cin. Zuerst wird die Anzahl der Zeilen und die Anzahl der Power-Iterationen eingelesen, dann die Kanten.

int main() {
    int n, p;
    std::cin >> n >> p;
    Graph g;
    std::string from, to;
    for (int i = 0; i < n; ++i) {
        std::cin >> from >> to;
        g.addEdge(from, to);
    }
    g.PageRank(p);
    g.printRanks();
    return 0;
}

Beispiel und Test

Angenommen, die Eingabe ist:

5 2
a b
b c
c a
a c
c b

Dann gibt es 3 Knoten (a, b, c) und 5 Kanten. Nach 2 Power-Iterationen sollten die Ränge ungefähr gleich sein (0.33). Teste deinen Code mit verschiedenen Eingaben, um sicherzustellen, dass er korrekt funktioniert.

Häufige Fehler und Tipps

Vergiss nicht, Knoten ohne ausgehende Kanten zu behandeln: Sie tragen nicht zum Rang anderer Seiten bei. In der Schleife solltest du outDegree[u] == 0 überspringen.
Runde auf zwei Dezimalstellen: Verwende std::setprecision(2) und std::fixed.
Alphabetische Sortierung: Die Ausgabe muss in aufsteigender alphabetischer Reihenfolge der URLs erfolgen.
Teste mit den öffentlichen Testfällen: Lade deinen Code auf Gradescope hoch und überprüfe die Ergebnisse.

Warum ist das heute noch relevant? Ein Blick auf 2026

Im Jahr 2026 ist PageRank immer noch ein zentrales Konzept in der Suchmaschinenoptimierung (SEO) und in Empfehlungssystemen. Viele moderne KI-gestützte Apps nutzen ähnliche iterative Algorithmen, um Inhalte zu ranken – von personalisierten Newsfeeds bis hin zu Videoplattform-Empfehlungen. Wenn du verstehst, wie PageRank funktioniert, hast du einen Vorteil beim Verständnis von Graph-Algorithmen und verteilten Systemen.

Fazit

Du hast jetzt eine funktionierende Implementierung des vereinfachten PageRank-Algorithmus in C++. Dieses Projekt deckt grundlegende Konzepte wie Adjazenzlisten, iterative Berechnungen und Rangverteilung ab. Experimentiere mit verschiedenen Graphen und erweitere den Algorithmus um einen Dämpfungsfaktor, um die volle PageRank-Version zu erhalten. Viel Erfolg bei deinem Projekt!