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

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 $V^2$ memory untuk graph dengan vertex sebanyak V sehingga tidak cocok untuk graph dengan ukuran besar.

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;
}

• https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/
• https://www.techiedelight.com/terminology-and-representations-of-graphs/
• https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-graph/
• https://www.softwaretestinghelp.com/graph-implementation-cpp/