Modul 4 [Pengenalan Graf]
Graf adalah data struktur non-linear yang terdiri atas beberapa vertex/node (V) dan edge/garis (E). Graf biasanya dilambangkan dengan G(V, E).
Contoh implementasi graf dapat dilihat pada gambar berikut.
Sumber gambar: techiedelight.com
V = {1, 2, 3, 4, 5, 6}
E = {(1, 4), (1, 6), (2, 6), (4, 5), (5, 6)}
Berikut adalah pengertian dari komponen/tipe-tipe graf
| Terminologi | Pengertian |
|---|---|
Vertex |
unit dasar dari graf |
Edge |
garis yang menghubungkan 2 vertex |
Weight |
berat / panjang dari suatu edge |
Weighted graph |
graf dengan setiap edge-nya memiliki berat |
Unweighted graph |
graf dengan setiap edge-nya tidak memiliki berat |
Directed graph |
graf dimana edge nya memiliki arah |
Undirected graph |
graf dimana edge-nya tidak memiliki arah |
Path |
Urutan dari vertex dan edge yang menghubungkan 2 vertex |
Cycle |
path yang dimulai dan diakhiri pada 1 buah vertex yang sama |
Beberapa implementasi graf dalam kehidupan sehari-hari:
- Umum digunakan oleh compiler untuk menggambarkan alokasi sumber daya ke proses atau menunjukkan analisis aliran data, dll.
- Umum digunakan untuk menggambarkan grafik jaringan, atau grafik semantik atau bahkan untuk menggambarkan aliran komputasi.
- Digunakan untuk membangun sistem transportasi khususnya jaringan jalan. Contoh populer: peta Google yang secara ekstensif menggunakan graph.
Beberapa kelebihan dari graf:
- Mudah diimplementasikan untuk mencari rute terdekat, tetangga dari vertex/node, dan sebagainya
- Membantu dalam mengorganisir data
Kekurangan dari graf:
- Menggunakan banyak pointer sehingga program dapat menjadi kompleks
- Dapat menggunakan memory yang besar
Terdapat beberapa cara yang biasa digunakan untuk merepresentasikan graf, yaitu:
Kita bisa merepresentasikan graf dengan menggunakan array 2 dimensi Adjmat[V][V] dengan AdjMat[i][j] bernilai 1 apabila terdapat edge yang menghubungkan vertex i dan j, bernilai 0 jika tidak ada edge.
Nilai AdjMat[i][j] bisa bernilai weight dari suatu edge untuk weighted graf.
Contoh Adjacency Matrix
- Unweighted & Undirected Graph
Sumber gambar: softwaretestinghelp.com
- Unweighted & Directed Graph
Sumber gambar: softwaretestinghelp.com
- Weighted & Directed Graph
Sumber gambar: softwaretestinghelp.com
Untuk implementasi pada codingan, dapat menggunakan array 2 Dimensi (sudah jarang digunakan)
Masalah utama dari penggunaan adjacency matrix adalah penggunaan memory sebanyak
Solusi dari masalah itu adalah Adjacency List. Ide dari perepresentasian dengan menggunakan Adjacency list adalah dengan hanya menyimpan daftar dari vertex-vertx lain yang memiliki edge yang terhubung dengan suatu vertex.
Contoh Adjacency List:
- Unweighted & Undirected Graph
Sumber gambar: softwaretestinghelp.com
- Unweighted & Directed Graph
Sumber gambar: softwaretestinghelp.com
Weighted Graph
#include<bits/stdc++.h>
using namespace std;
void addEdge(vector<pair <int, int>> adj[],int u,int v, int weight){
adj[u].push_back(make_pair(v, weight));
// Jika undirected, maka dipush ke 2 2 nya
// adj[v].push_back(make_pair(u, weight));
}
void printGraph(vector<pair <int, int>> adj[],int V){
// Loop sebanyak jumlah vertex
for (int v = 0; v < V; v++){
cout << "\n Adjacency list of vertex "
<< v << "\n head";
for (int i = 0; i < adj[v].size(); i++){
// Karena pakai <pair <int, int>>, jadi untuk ngeprint bisa menggunakan .first dan .second
cout<<" --> "<< adj[v][i].first << " " << adj[v][i].second;
}
printf("\n");
}
}
int main(){
// Jumlah Vertex
int V = 5;
vector<pair <int, int>> adj[V];
addEdge(adj, 0, 1, 2);
addEdge(adj, 0, 4, 3);
addEdge(adj, 1, 3, 4);
addEdge(adj, 2, 4, 2);
addEdge(adj, 1, 2, 3);
printGraph(adj, V);
return 0;
}Unweighted Graph
#include<bits/stdc++.h>
using namespace std;
void addEdge(vector<int> adj[],int u,int v){
adj[u].push_back(v);
// Jika undirected, maka dipush ke 2 2 nya
// adj[v].push_back(u)
}
void printGraph(vector<int> adj[],int V){
// Loop sebanyak jumlah vertex
for (int v = 0; v < V; v++){
cout << "\n Adjacency list of vertex "
<< v << "\n head";
for (int i = 0; i < adj[v].size(); i++){
cout<<" --> "<<adj[v][i];
}
printf("\n");
}
}
int main(){
// Jumlah Vertex
int V = 5;
vector<int> adj[V];
addEdge(adj, 0, 1);
addEdge(adj, 0, 4);
addEdge(adj, 1, 3);
addEdge(adj, 2, 4);
addEdge(adj, 1, 2);
printGraph(adj, V);
return 0;
}