Implementasi Graph di C++ dapat dilakukan dengan beberapa cara bergantung pada representasi yang diinginkan:
- Adjacency Matrix: Menggunakan matriks dua dimensi untuk mewakili koneksi antara simpul.
- Adjacency List: Menggunakan daftar untuk menyimpan tetangga dari setiap simpul, biasanya diimplementasikan dengan
vectoratauunordered_map.
Berikut adalah implementasi dasar kedua metode tersebut:
1. Representasi Graph dengan Adjacency Matrix
Adjacency Matrix menggunakan matriks (n×n), di mana nn adalah jumlah simpul. Nilai di matriks menunjukkan apakah ada edge antara dua simpul.
Implementasi:
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
vector<vector<int>> adjMatrix;
int numVertices;
public:
Graph(int vertices) : numVertices(vertices) {
adjMatrix.resize(vertices, vector<int>(vertices, 0));
}
void addEdge(int u, int v) {
adjMatrix[u][v] = 1;
adjMatrix[v][u] = 1; // Jika graph tidak berarah
}
void printGraph() {
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}
};
int main() {
Graph g(5); // Graph dengan 5 simpul
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(3, 4);
cout << "Adjacency Matrix:" << endl;
g.printGraph();
return 0;
}Kelebihan:
- Mudah diimplementasikan.
- Waktu akses edge adalah O(1).
Kekurangan:
- Boros ruang untuk graph yang jarang (sparse).
2. Representasi Graph dengan Adjacency List
Adjacency List lebih hemat ruang karena hanya menyimpan tetangga dari simpul yang memiliki edge.
Implementasi:
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
vector<vector<int>> adjList;
public:
Graph(int vertices) {
adjList.resize(vertices);
}
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u); // Jika graph tidak berarah
}
void printGraph() {
for (int i = 0; i < adjList.size(); i++) {
cout << i << ": ";
for (int neighbor : adjList[i]) {
cout << neighbor << " ";
}
cout << endl;
}
}
};
int main() {
Graph g(5); // Graph dengan 5 simpul
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(3, 4);
cout << "Adjacency List:" << endl;
g.printGraph();
return 0;
}Kelebihan:
- Hemat ruang untuk graph yang jarang (sparse).
- Mudah untuk menyimpan weighted graph.
Kekurangan:
- Akses edge antara dua simpul tertentu tidak secepat adjacency matrix (O(n) dalam skenario terburuk).
3. Representasi Weighted Graph
Weighted Graph memerlukan penyimpanan bobot di setiap edge. Representasi adjacency list sering digunakan untuk ini.
Implementasi Weighted Graph dengan Adjacency List:
#include <iostream>
#include <vector>
using namespace std;
class WeightedGraph {
private:
vector<vector<pair<int, int>>> adjList;
public:
WeightedGraph(int vertices) {
adjList.resize(vertices);
}
void addEdge(int u, int v, int weight) {
adjList[u].emplace_back(v, weight);
adjList[v].emplace_back(u, weight); // Jika graph tidak berarah
}
void printGraph() {
for (int i = 0; i < adjList.size(); i++) {
cout << i << ": ";
for (auto& neighbor : adjList[i]) {
cout << "(" << neighbor.first << ", " << neighbor.second << ") ";
}
cout << endl;
}
}
};
int main() {
WeightedGraph g(5); // Graph dengan 5 simpul
g.addEdge(0, 1, 10);
g.addEdge(0, 4, 20);
g.addEdge(1, 2, 30);
g.addEdge(1, 3, 40);
g.addEdge(1, 4, 50);
g.addEdge(2, 3, 60);
g.addEdge(3, 4, 70);
cout << "Weighted Adjacency List:" << endl;
g.printGraph();
return 0;
}Perbandingan Representasi Graph
| Representasi | Keunggulan | Kelemahan |
|---|---|---|
| Adjacency Matrix | Akses edge cepat (O(1)). | Boros memori untuk graph sparse (O(V2)). |
| Adjacency List | Hemat memori untuk graph sparse. | Akses edge lambat dalam skenario terburuk (O(V)). |
| Weighted Graph | Mudah menambahkan bobot ke adjacency list. | Membutuhkan struktur data tambahan. |
Jika Anda ingin implementasi tambahan seperti traversal (DFS/BFS) atau algoritma berbasis graph (Dijkstra, MST, dll.), beri tahu saya! 😊
Leave a Reply