Graph Tugas minggu 14

 Nama : Fakhrian Elanta

Kelas : Struktur Data D

NRP : 5025251019

Graph merupakan sebuah tipe data yang dimana suatu elemen terhubung dengan elemen lain menggunakan edge. Dalam graph sendiri terdapat : Vertex/Node, Edge, dan weight(Jika graph tersebut memiliki beratan untuk edgenya).

BFS

BFS merupakan salah satu cara traversal graph yang dimana traversal dilakukan dengan mengunjungi semua "tetangga" atau node yang terkoneksi langsung oleh node yang sedang ditelusuri

#include<bits/stdc++.h>

using namespace std;

map<int, bool> visited;

void bfs(int start, map<int, vector<int>> neighbour){

    queue<int> q;

    q.push(start);

    visited[start] = true;

    cout<<start<<" ";

    while(!q.empty()){

        int temp = q.front();

        q.pop();

        for(auto isi : neighbour[temp]){

            if(visited[isi]==true)continue;

            visited[isi] = true;

            q.push(isi);

            cout<<isi<<" ";

        }

    }

}

int main(){

    map<int, vector<int>> hubungan;

    int N;

    cout<<"Masukan banyaknya hubungan: ";

    cin>>N;

    int awal;

    while(N--){

        cout<<"Masukan yang berhubungan(x y): ";

        int x, y;

        cin>>x>>y;

        hubungan[x].push_back(y);

        hubungan[y].push_back(x);

    }

    cout<<"Masukkan nilai awal untuk bfs: ";

    cin>>awal;

    bfs(awal, hubungan);

}

Studi kasus : Pengambilan Mata Kuliah

#include <iostream>

#include <vector>

#include <map>

#include <string>

#include <set>

using namespace std;

void DFS(string nodeSaatIni, map<string, vector<string>>& graph, set<string>& dikunjungi) {

   

    dikunjungi.insert(nodeSaatIni);

   

    for (string tetangga : graph[nodeSaatIni]) {

       

        if (dikunjungi.find(tetangga) == dikunjungi.end()) {

            cout << "- " << tetangga << endl;

           

            DFS(tetangga, graph, dikunjungi);

        }

    }

}

int main() {

   

    int N;

    cout << "Masukkan banyaknya mahasiswa yang terdata: ";

    cin >> N;

    set<string> daftarMahasiswa;

    for (int i = 0; i < N; i++) {

        cout << "Masukkan nama mahasiswa ke-" << i + 1 << " : ";

        string c;

        cin >> c;

        daftarMahasiswa.insert(c);

    }

    cout << endl;

   

    map<string, vector<string>> pengambilMatkul;

    int took;

    cout << "Masukkan berapa banyak pengambilan matkul yang terjadi: ";

    cin >> took;

   

    while (took--) {

        cout << "Masukkan nama mahasiswa lalu matkul yang diambil (pisah spasi): ";

        string mhs, matkul;

        cin >> mhs >> matkul;

       

       

        pengambilMatkul[matkul].push_back(mhs);

    }

    cout << endl;

   

    string matkulDicari;

    cout << "Masukkan nama matkul yang ingin dicek pengambilnya: ";

    cin >> matkulDicari;

   

    set<string> dikunjungi;

    cout << "\n=== HASIL PENCARIAN DFS UNTUK MATKUL " << matkulDicari << " ===" << endl;

   

   

    if (pengambilMatkul.find(matkulDicari) != pengambilMatkul.end()) {

        DFS(matkulDicari, pengambilMatkul, dikunjungi);

    } else {

        cout << "(Tidak ada mahasiswa yang mengambil matkul ini / Matkul tidak terdata)" << endl;

    }

    return 0;

}