# Tugas Pendahuluan Modul 8 - Graph

Pembuat Soal: RE

Nama : Ahmad Malik Prasetyo
NPM  : 2406416270

## 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>

Graph adalah struktur data non-linear yang terdiri dari gabungan nodes yang saling terhubung melalui edges.
- Undirected Graph, node terhubung degan edge bersifat dua arah
- Directed Graph, node terhubung dengan edge hanya bisa dilalui satu arah

### Referensi:
- GeeksforGeeks, “Graph Algorithms,” GeeksforGeeks, Jan. 17, 2024. https://www.geeksforgeeks.org/dsa/graph-data-structure-and-algorithms/
- “Struktur Data Graph: Pengertian, Jenis, dan Kegunaannya,” Sep. 16, 2022. https://www.trivusi.web.id/2022/07/struktur-data-graph.html

---

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

- Adjacency Matrix adalah graph yang menggunakan matrix dengan setiap node menunjukkan ada atau tidaknya edge antara dua node. Ini menmerlukan memori yang sangat besar, O(V²) sehingga tidak efisien
- Adjacency List adalah graph yang menggunakan sebuah list yang hanya berisi node-node yang terhubung dengannya. Memori yang digunakan dengan metode ini jauh lebih efisien dibanding matrix.

### Referensi:
- GeeksforGeeks, “Graph and its representations,” GeeksforGeeks, Nov. 13, 2012. https://www.geeksforgeeks.org/dsa/graph-and-its-representations/
- baeldung, “Graph Data Structures | Baeldung on Computer Science,” www.baeldung.com, Apr. 29, 2020. https://www.baeldung.com/cs/graphs

---

### 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>

`stack` adalah container adaptor dengan prinsip LIFO(Last-In, First-Out) dimana elemen terakhir akan dikeluarkan pertama. Ini mengguakan DFS untuk menyimpan node-node yang dikunjungi menggunakan LIFO.

`queue` adalah container adaptor dengan prinsip FIFO(First-In, First-Out) dimana elemen pertama juga akan dikeluarkan pertama. Ini mengguakan BFS dimana urutan yang dikeluarkan berdasarkan urutan levelnya.

### Referensi:
- Cplusplus.com, 2022. https://cplusplus.com/reference/stack/stack/
- GeeksforGeeks, “Stack in C++ STL,” GeeksforGeeks, Dec. 07, 2015. https://www.geeksforgeeks.org/cpp/stack-in-cpp-stl/

---

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

BFS (Breadth First Search) adalah traversal dengan prinsip untuk mencari seberapa lebar sebuah level sebelum melanjutkan ke level selanjutnya.

DFS (Depth First Search) adalah traversal dengan prinsip untuk mencari seberapa dalam/level paling bawah dari node kiri pada graph sebelum melebar ke node-node kanan.

### Referensi:
- GeeksforGeeks, “BFS vs DFS for Binary Tree,” GeeksforGeeks, Feb. 22, 2016. https://www.geeksforgeeks.org/dsa/bfs-vs-dfs-binary-tree/
- “Difference Between BFS and DFS,” BYJUS. https://byjus.com/gate/difference-between-bfs-and-dfs/

---

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

Rekursif pada DFS menggunakan call stack sistem untuk menelusuri graph secara mendalam. Setiap node memanggil DFS pada tetangganya yang belum dikunjungi, dan proses “return” terjadi otomatis saat fungsi selesai. Cara ini sederhana dan mudah ditulis, tetapi dapat menyebabkan stack overflow jika graph sangat dalam.

Iteratif menggunakan stack buatan untuk meniru perilaku recursive. Node awal dimasukkan ke dalam stack, lalu selama stack tidak kosong, node dipop, diproses, dan tetangganya didorong kembali ke stack. Metode ini lebih aman untuk graph besar karena tidak bergantung pada call stack.

Keduanya memiliki kompleksitas waktu yang sama, O(V + E), tetapi iteratif memberi kontrol memori yang lebih baik.

### Referensi:
- S. Sryheni, “Introduction to Depth First Search Algorithm (DFS) | Baeldung on Computer Science,” www.baeldung.com, Sep. 22, 2020. https://www.baeldung.com/cs/depth-first-search-intro
- GeeksforGeeks, “Depth First Search or DFS for a Graph,” GeeksforGeeks, Mar. 15, 2012. https://www.geeksforgeeks.org/dsa/depth-first-search-or-dfs-for-a-graph/

---

## 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) {
        //TODO: Implementasikan BFS iteratif (dengan std::queue)
        //      Gunakan std::set<std::string> untuk 'visited'
        std::set<std::string> visited;
        std::queue<std::string> queue;

        visited.insert(startNode);
        queue.push(startNode);

        std::cout << "BFS dari " << startNode << ": ";

        while (!queue.empty()) {
            std::string u = queue.front();
            queue.pop();
            std::cout << u << " ";

            for (std::string v : adj[u]) {
                if (visited.find(v) == visited.end()) {
                    visited.insert(v);
                    queue.push(v);
                }
            }
        }

        std::cout << std::endl;
    }

    void DFS(std::string startNode) {
        //TODO: Implementasikan DFS iteratif (dengan std::stack)
        //      Gunakan std::set<std::string> untuk 'visited'
        std::set<std::string> visited;
        std::stack<std::string> string;

        string.push(startNode);

        std::cout << "DFS dari " << startNode << ": ";

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

            if (visited.find(u) == visited.end()) {
                visited.insert(u);
                std::cout << u << " ";
            }

            for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) {
                if (visited.find(*it) == visited.end()) {
                    string.push(*it);
                }
            }
        }

        std::cout << std::endl;
    }
};


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

    // TODO: Masukkan semua node ke Graph sesuai gambar
    //       Gunakan addEdge untuk menghubungkan node-node tersebut
    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");
    
    // TODO: Uji function DFS dan BFS yang kamu buat
    //       Gunakan minimal 2 starting node yang berbeda
    std::cout << "Test DFS" << std::endl;
    g.DFS("Miuna");
    g.DFS("Chisaki");

    std::cout << "Test BFS" << std::endl;
    g.BFS("Sayu");
    g.BFS("Tsumugu");
    
    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]

Tidak, karena menggunakan directed graph maka node Miuna dan Sayu tidak bisa dikunjungi selain menjadi startNode

---

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

Karena menggunakan directed graph, maka output akan sama.

---

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

`(false)` mengubah graph menjadi undirected graph

---

#### <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]


Dapat dilihat dari test DFS dan BFS bahwa dua node yang hanya dikunjungi bila menjadi sebuah startNode adalah Miuna dan Sayu. Karena pada directed graph, tidak ada panah yang menunjukkan hubungan yang berakhir pada node keduanya.

---

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