# Tugas Pendahuluan Modul 8 - Graph

Pembuat Soal: RE

Nama : Reinathan Ezkhiel Kurniawan
NPM  : 2406397675

## Part 1 - Teori (60 poin)

### 1. Apa itu struktur data Graph? Jelaskan mengenai Undirected Graph dan Directed Graph! <span style="color:red;">(10 poin)</span>

Struktur data *Graph* merupakan struktur data non-linear yang terdiri dari **vertex**(**node**) dan **edge**(sisi) yang menghubungkan antar *vertex*. *Graph* digunakan untuk merepresentasikan hubungan antar objek pada kehidupan nyata seperti topologi jaringan komputer,jalur peta, dsbg.

**Undirected Graph** merupakan *Graph* yang *edge*nya tidak memiliki arah sehingga hubungannya bersifat dua arah. misal ada *edge* u dan v, maka u akan terhubung dengan v begitu juga sebaliknya.

**Directed Graph** merupakan sebuah *Graph* yang memiliki arah yang ditunjukkan dengan simbol panah pada setiap *edge*nya. Dengan demikian, pada setiap sisi tercermin hubungan satu arah, sehingga apabila terdapat *edge* u dan v maka hubungan harus ditentukan secara spesifik(u terhubung dengan v belum tentu v terhubung ke u).

### Referensi:
- GeeksforGeeks, “Graph Data Structure And Algorithms,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/. [Diakses: 13-Nov-2025]
- TutorialsPoint, “Graph Data Structure,” TutorialsPoint. [Online]. Available: https://www.tutorialspoint.com/data_structures_algorithms/graph_data_structure.htm. [Diakses: 13-Nov-2025]

---

### 2. Sebutkan dan jelaskan 2 jenis representasi Graph serta bandingkan keduanya! <span style="color:red;">(10 poin)</span>

Terdapat dua cara untuk merepresentasikan *Graph* :
* Dengan menggunakan **Adjacency Matrix** : Menggunakan matriks 2D berbentuk persegi (NxN). Matriks[u][v]=1 apabila terdapat *edge*, selain itu 0. Kelebihan pendekatan ini adalah cepat memeriksa apakah terdapat sebuah *edge* pada sebuah *vertex* (O(1)). Kekurangannya, pendekatan ini boros memori.
* Dengan menggunakan **Adjacency List** : Pada setiap *vertex* menyimpan daftar *vertex* yang terhubung dengan *vertex* tersebut. Kelebihannya, pendekatan ini lebih menghemat memori untuk sebuah *graph* yang sisinya tidak banyak (*sparse*). Kekurangannya, pengecekan *edge* lebih lambat,tergantung banyaknya relasi (*degree*) sebuah *vertex*.

### Referensi:
- GeeksforGeeks, “Graph and its representations,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/graph-and-its-representations/. [Diakses: 13-Nov-2025]
- Programiz, “Graph Representation in Data Structure,” Programiz. [Online]. Available: https://www.programiz.com/dsa/graph-adjacency-matrix. [Diakses: 13-Nov-2025]

---

### 3. Jelaskan mengenai `std::stack` dan `std::queue` dan cara kerjanya! Apa peran keduanya dalam pendekatan BFS dan DFS iteratif? <span style="color:red;">(15 poin)</span>

* `std::stack` merupakan struktur data LIFO (*Last In, First Out*, mendahulukan *child* daripada *parent*/*root*) dengan operasi utama `push()`, `pop()`, `top()`. Pada DFS iteratif, *stack* digunakan untuk menjelajahi *node* sedalam mungkin terlebih dahulu.
* `std::queue` merupakan struktur data FIFO (*First In, First Out*,mendahulukan*parent*/*root* daripada *child* ) dengan operasi utama `push()`, `pop()`, `front()`. Pada BFS, *queue* digunakan untuk menjelajahi *node* berdasarkan *level*.

### Referensi:
- GeeksforGeeks, “Stack in C++ STL,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/stack-in-cpp-stl/. [Diakses: 13-Nov-2025]
- GeeksforGeeks, “Queue in C++ STL,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/queue-cpp-stl/. [Diakses: 13-Nov-2025]

---

### 4. Jelaskan mengenai traversal BFS dan DFS dan bandingkan antara keduanya! <span style="color:red;">(15 poin)</span>

* Traversal BFS (*Breadth First Search*) akan mengunjungi *node* berdasarkan *level*. Penelusuran dimulai dari **root**. Traversal menggunakan struktur data *queue*. Cocok untuk mencari sebuah **shortest path** pada *graph* tak berbobot (*unweighted graph*). Penggunaan memori akan lebih besar karena pencarian dibatasi oleh *level* dan akan terus berlanjut ke *level* selanjutnya.
* Traversal DFS (*Depth First Search*) akan menjelajahi sedalam mungkin sebelum mengunjungi sebueh *parent* atau kembali ke **root**. Traversal menggunakan struktur data **stack** (dengan iterasi) atau **rekursi**. Traversal ini lebih cocok sigunakan untuk mendeteksi *cylce*, *topological sort*, dsbg. Penggunaan memori akan lebih kecil karena pencarian diawali dengan *node* terdalam sebelum masuk ke struktur data utama.
### Referensi:
- GeeksforGeeks, “Breadth First Search (BFS),” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/. [Diakses: 13-Nov-2025]
- GeeksforGeeks, “Depth First Search (DFS),” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/. [Diakses: 13-Nov-2025]

---

### 5. Jelaskan perbedaan antara pendekatan iteratif dan rekursif pada DFS! <span style="color:red;">(10 poin)</span>

* **DFS Iteratif** : Pendekatan ini menggunakan **stack**(`std::stack`) dan lebih aman untuk diimplementasikan pada *graph* besar karena tidak tergantung *call stack*. Implementasi sedikit lebih panjang daripada DFS Rekursif tapi lebih fleksibel.
* **DFS Iteratif** : Pendekatan ini menggunakan *call stack system* . Pendekatan ini lebih *simple* dan lebih mudah untuk diimplementasikan. Namun terdapat risiko **stack overflow** jika digunakan pada *graph* yang berukuran besar.

### Referensi:
- GeeksforGeeks, “Iterative Depth First Traversal,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/iterative-depth-first-traversal/. [Diakses: 13-Nov-2025]
- GeeksforGeeks, “Depth First Search (DFS),” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/. [Diakses: 13-Nov-2025]

---

## Part 2 - Praktik (40 poin)

**Daem** adalah atmin channel **Muse Indonesia**. Baru-baru ini, ia sedang mengurus lisensi anime terkutuk yang akan ditayangkan. Saat sedang melakukan QC terhadap takarir, ia menemukan bahwa hubungan karakter antar anime tersebut cukup kompleks, sehingga ia pun menggambarkannya dalam **Graph** dan mempostingnya di Instagram.


**Budi** melihat post tersebut dan penasaran dengan anime yang akan ditayangkan. Akan tetapi, karena dikeroyok 5 praktikum, ia **tidak punya waktu** untuk menonton 26 episode anime tersebut. Di saat yang sama, ia sedang mempelajari materi **Graph** di mata kuliah Alprog. Ia pun mencoba untuk membuat program untuk **mengamati Graph hubungan karakter** di atas.

### Bantu Budi untuk melengkapi program di bawah! <span style="color:red;">(25 poin)</span>

#include <iostream>
#include <vector>
#include <list>
#include <queue> 
#include <stack> 
#include <string> 
#include <map>  
#include <set>

class Graph {
private:
    std::map<std::string, std::list<std::string>> adj;
    bool directed = false;

public:
    Graph(bool directed) {
        this->directed = directed;
    }

    void addEdge(std::string u, std::string v) {
        adj[u].push_back(v);

        if (!directed) {
            adj[v].push_back(u);
        }
    }

    void BFS(std::string startNode) {
        std::queue<std::string> qeue; 
        std::set<std::string> visited;
        qeue.push(startNode);
        visited.insert(startNode);

        std::cout << "BFS dari " << startNode << " : ";
        while (!qeue.empty()) { 
            std::string node = qeue.front(); 
            qeue.pop(); 
            std::cout << node << " ";

            for(auto &neighbor : adj[node]) {
                if(visited.count(neighbor) == 0) {
                    visited.insert(neighbor);
                    qeue.push(neighbor);
                }
            }
        }
        std::cout << "\n";

    }

    void DFS(std::string startNode) {
       std::stack<std::string> steck; 
       std::set<std::string> visited;
       steck.push(startNode);
       std::cout << "DFS dari " << startNode << " : ";

       while(!steck.empty()){
        std::string node = steck.top();
        steck.pop();

        if(visited.count(node) == 0) {
            visited.insert(node);
            std::cout << node << " ";

            for(auto it = adj[node].rbegin(); it != adj[node].rend(); it++) {
                if(!visited.count(*it)) {
                    steck.push(*it);
                }
            }
        }
        
       }

       std::cout << "\n";
    }
};


int main() {
    Graph g(true); // Directed graph

    g.addEdge("Miuna", "Hikari");
    g.addEdge("Hikari", "Manaka");
    g.addEdge("Manaka", "Tsumugu");
    g.addEdge("Tsumugu", "Chisaki");
    g.addEdge("Chisaki", "Hikari");
    g.addEdge("Sayu", "Kaname");
    g.addEdge("Kaname", "Chisaki");
    
    g.BFS("Miuna");
    g.BFS("Hikari");
    g.BFS("Manaka");
    g.BFS("Tsumugu");

    g.DFS("Chisaki");
    g.DFS("Sayu");
    g.DFS("Kaname");
    g.DFS("Miuna");
    
    
    
    return 0;
}

**Screenshot Output:**

---

### Analisis <span style="color:red;">(15 poin)</span>

#### 1. Setelah menguji program di atas, apakah mungkin program melakukan traversal ke semua node? Mengapa? [5 poin]

Traversal bisa mencapai semua *node* jika seluruh *node* **terhubung** oleh arah panah yang konsisten pada *directed graph*. Pada gambar, *graph* nya *not strongly connected* karena beberapa *node* tidak memiliki jalur masuk atau keluar ke *node* lainnya. Misal seperti Miuna dan Hikari - Manaka dan Tsumugu hanya hubungan satu arah. Karena tiap *edge* hanya satu arah maka program tidak bisa menjangkau seluruh *node* dari satu *starting node*.

---

#### 2. Pada mode directed graph, apakah terdapat perbedaan antara output BFS dan DFS? Jelaskan secara singkat! [5 poin]

Pada **BFS**, ia mengunjungi *node* berdasarkan **level** dan menggunakan **queue** sehingga pola `visited` pada Output melebar pada satu *level* baru masuk ke dalam. Pada **DFS**, ia mengunjungi *node* sedalam mungkin terlebih dahulu menggunakan **stack** sehingga pola `visited` nya menyusuri rantai terdalam baru mundur (strategi penjelajahan berbeda).

---

#### 3. Coba ubah line `Graph g(true);` menjadi `Graph g(false);`. Apa yang berubah? Jelaskan secara singkat! [5 poin]

`g(false)` akan membuat graf menjadi **undirected grapph** sehingga setiap *edge* otomatis menjadi dua arah dan semua hubungan "Suka" menjadi hubungan timbal balik. Dampaknya pada traversal adalah Graf menjadi sepenuhnya terhubung dan akan lebih besar kemungkinan semua *node* bisa dikunjungi, BFS di *node* manapun bisa mengunjungi *node* dengan jumlah lebih banyak.

**Screenshot Output dengan traversal semua *node* dikunjungi (mengubah jadi*false*)**

---

#### <span style="color:red;">Bonus:</span> Setelah mengamati Graph beserta output program, coba analisis karakter manakah yang paling mungkin tidak mendapatkan pasangan di akhir cerita! [+5 poin]

**Miuna** dan **Sayu** karena tidak ada yang menyukai kedua karakter tersebut, hanya hubungan satu arah ke karakter yang mereka sukai.

---

## <span style="color:red;">NOTE:</span> Pelajari implementasi DFS secara rekursif untuk mempermudah pengerjaan CS!