C++'da bir grafiğin hızlıca yazılabilecek bir uygulamasını merak ediyordum. Veri yapısının çizge algoritmalarını (BFS, DFS, Kruskal, Dijkstra... gibi) manipüle etmek ve kullanmak için kolay olmasına ihtiyacım var. Bu uygulamaya bir algoritma olimpiyatı için ihtiyacım var, bu yüzden veri yapısını yazmak ne kadar kolay olursa o kadar iyi.
Böyle bir DS önerebilir misiniz (ana yapılar veya sınıflar ve içlerinde ne olacak). Bir Bitişiklik listesi ve Bitişiklik matrisinin ana olasılıklar olduğunu biliyorum, ancak daha ayrıntılı bir kod örneği demek istiyorum.
Örneğin, en son DFS için bir grafik uygulamam gerektiğinde bu DS hakkında düşündüm:
struct Edge {
int start;
int end;
struct Edge* nextEdge;
}
ve ardından i'inci düğümde başlayan kenarları temsil eden Kenar Listesini (struct Edge) içeren n boyutlu bir dizi kullanılır.
ancak bu grafik üzerinde DFS yapmaya çalışırken yaklaşık 10 while döngüsü içeren 50 satırlık bir kod yazmak zorunda kaldım.
Hangi 'iyi' uygulamalar var?
Aşağıda Grafik Veri Yapısının C++'da Bitişiklik Listesi olarak bir uygulaması bulunmaktadır.
Köşelerin gösterimi için STL vektörünü ve kenar ve hedef köşeyi göstermek için STL çiftini kullandım.
#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);
}
Bu gerçekten hangi algoritmaları uygulamanız gerektiğine bağlıdır, sihirli bir değnek yoktur (ve bu sürpriz olmamalıdır... programlama hakkındaki genel kural, genel bir kuralın olmamasıdır ;-) ).
Yönlendirilmiş multigrafları genellikle işaretçilerle düğüm/kenar yapıları kullanarak temsil ediyorum... daha spesifik olarak:
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;
};
Diğer bir deyişle, her düğümün çift bağlantılı bir gelen bağlantılar listesi ve çift bağlantılı bir giden bağlantılar listesi vardır. Her bağlantı from
ve to
düğümlerini bilir ve aynı zamanda iki farklı çift bağlantılı listede yer alır: aynı from
düğümünden çıkan tüm bağlantıların listesi ve aynı to
düğümüne gelen tüm bağlantıların listesi.
Aynı düğümden** çıkan tüm bağlantıların zincirini takip ederken prev_same_from
ve next_same_from
işaretçileri kullanılır; bunun yerine aynı düğüme işaret eden tüm bağlantıların zincirini yönetirken prev_same_to
ve next_same_to
işaretçileri kullanılır.
Çok fazla işaretçi çevirme işlemi vardır (bu yüzden işaretçileri sevmiyorsanız bunu unutun) ancak sorgulama ve güncelleme işlemleri verimlidir; örneğin bir düğüm veya bağlantı eklemek O(1), bir bağlantıyı kaldırmak O(1) ve bir x düğümünü kaldırmak O(deg(x))'dir.
Tabii ki probleme, yük boyutuna, grafik boyutuna, grafik yoğunluğuna bağlı olarak bu yaklaşım aşırı yorucu veya bellek için çok fazla talepkar olabilir (yüke ek olarak düğüm başına 4 işaretçi ve bağlantı başına 6 işaretçi vardır).
Benzer bir yapının tam uygulaması burada bulunabilir.
En yaygın temsiller muhtemelen bu ikisidir:
Bu ikisi arasında bitişiklik matrisi en basit olanıdır, yeter ki (muhtemelen çok büyük) bir n * n
dizisine sahip olmayı umursamayın, burada n
köşe sayısıdır. Dizinin temel türüne bağlı olarak, örneğin en kısa yol bulma algoritmalarında kullanmak için kenar ağırlıklarını bile saklayabilirsiniz.