Ich habe mich über eine schnell zu schreibende Implementierung eines Graphen in C++ gewundert. Die Datenstruktur muss einfach zu manipulieren sein und Graph-Algorithmen (wie BFS, DFS, Kruskal, Dijkstra...) verwenden. Ich brauche diese Implementierung für eine Algorithmen-Olympiade, also je einfacher die Datenstruktur zu schreiben ist, desto besser.
Können Sie solche DS vorschlagen (Hauptstrukturen oder Klassen und was darin enthalten sein wird). Ich weiß, dass eine Adjacency-Liste und eine Adjacency-Matrix die Hauptmöglichkeiten sind, aber ich meine ein detaillierteres Codebeispiel.
Zum Beispiel habe ich über diese DS nachgedacht, als ich das letzte Mal einen Graphen für DFS implementieren musste:
struct Edge {
int start;
int end;
struct Edge* nextEdge;
}
und verwendete dann ein Array der Größe n, das an seiner i'ten Stelle die Edge List(struct Edge) enthält, die die Kanten repräsentiert, die im i'ten Knoten beginnen.
Aber beim Versuch, diesen Graphen mit DFS zu bearbeiten, musste ich einen 50-zeiligen Code mit etwa 10 while-Schleifen schreiben.
Welche 'guten' Implementierungen gibt es?
Nachfolgend ist eine Implementierung der Graphdatenstruktur in C++ als Adjacency List dargestellt.
Ich habe STL-Vektor für die Darstellung von Knoten und STL-Paar für die Bezeichnung der Kante und des Zielknotens verwendet.
#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;
struct vertex {
typedef pair<int, vertex*> ve;
vector<ve> adj; //cost of edge, destination vertex
string name;
vertex(string s) : name(s) {}
};
class graph
{
public:
typedef map<string, vertex *> vmap;
vmap work;
void addvertex(const string&);
void addedge(const string& from, const string& to, double cost);
};
void graph::addvertex(const string &name)
{
vmap::iterator itr = work.find(name);
if (itr == work.end())
{
vertex *v;
v = new vertex(name);
work[name] = v;
return;
}
cout << "\nVertex already exists!";
}
void graph::addedge(const string& from, const string& to, double cost)
{
vertex *f = (work.find(from)->second);
vertex *t = (work.find(to)->second);
pair<int, vertex *> edge = make_pair(cost, t);
f->adj.push_back(edge);
}
Es hängt wirklich davon ab, welche Algorithmen Sie implementieren müssen, es gibt kein Patentrezept (und das sollte keine Überraschung sein... die allgemeine Regel über Programmierung ist, dass es keine allgemeine Regel gibt ;-) ).
Am Ende stelle ich gerichtete Multigraphen oft mit Knoten-/Kantenstrukturen mit Zeigern dar... genauer gesagt:
struct Node
{
... payload ...
Link *first_in, *last_in, *first_out, *last_out;
};
struct Link
{
... payload ...
Node *from, *to;
Link *prev_same_from, *next_same_from,
*prev_same_to, *next_same_to;
};
Mit anderen Worten: Jeder Knoten hat eine doppelt verknüpfte Liste von eingehenden Links und eine doppelt verknüpfte Liste von ausgehenden Links. Jede Verknüpfung kennt einen "von"- und einen "zu"-Knoten und ist gleichzeitig in zwei verschiedenen doppelt verknüpften Listen enthalten: der Liste aller Verknüpfungen, die von demselben "von"-Knoten ausgehen, und der Liste aller Verknüpfungen, die an demselben "zu"-Knoten ankommen.
Die Zeiger prev_same_from
und next_same_from
werden verwendet, wenn man die Kette aller Links verfolgt, die vom selben Knoten ausgehen; die Zeiger prev_same_to
und next_same_to
werden stattdessen verwendet, wenn man die Kette aller Links verwaltet, die zum selben Knoten zeigen.
Es ist eine Menge Zeigerarbeit (wenn Sie also Zeiger nicht lieben, vergessen Sie es einfach), aber Abfrage- und Aktualisierungsoperationen sind effizient; zum Beispiel ist das Hinzufügen eines Knotens oder einer Verknüpfung O(1), das Entfernen einer Verknüpfung ist O(1) und das Entfernen eines Knotens x ist O(deg(x)).
Natürlich kann dieser Ansatz je nach Problem, Größe der Nutzlast, Größe des Graphen und Dichte des Graphen überfordernd oder zu speicherintensiv sein (zusätzlich zur Nutzlast hat man 4 Zeiger pro Knoten und 6 Zeiger pro Link).
Eine ähnlich strukturierte vollständige Implementierung findet sich hier.
Die häufigsten Darstellungen sind wahrscheinlich diese beiden:
Von diesen beiden ist die Adjazenzmatrix die einfachste, solange es Ihnen nichts ausmacht, ein (möglicherweise riesiges) n * n
-Array zu haben, wobei n
die Anzahl der Scheitelpunkte ist. Abhängig vom Basistyp des Arrays können Sie sogar Kantengewichte für die Verwendung z.B. in Algorithmen zur Ermittlung des kürzesten Weges speichern.