konsep dasar algoritma graf

Algoritma graf dalam bahasa C

Algoritma graf adalah algoritma yang digunakan untuk memproses dan memanipulasi struktur data graf. Graf adalah kumpulan simpul (node) yang terhubung oleh sisi (edge). Algoritma graf berfungsi untuk menemukan jalur, menghitung jarak terpendek, mencari lintasan tertentu, atau melakukan operasi lainnya pada struktur data graf. Dalam bahasa C, beberapa algoritma graf populer melibatkan struktur data graf berarah dan tidak berarah. Berikut adalah beberapa algoritma graf umum yang dapat diimplementasikan dalam bahasa C:

1. **Depth-First Search (DFS):**
   - DFS digunakan untuk menjelajahi atau mencari jalur dalam graf.
   - Pada setiap simpul, DFS akan menelusuri sepanjang satu cabang hingga mencapai simpul leaf sebelum kembali dan menjelajahi cabang lain.

2. **Breadth-First Search (BFS):**
   - BFS digunakan untuk menjelajahi atau mencari jalur dalam graf.
   - Pada setiap level dari graf, BFS akan menelusuri semua simpul sebelum bergerak ke level berikutnya.

3. **Dijkstra's Algorithm:**
   - Dijkstra digunakan untuk mencari jalur terpendek dari satu simpul ke semua simpul lainnya dalam graf dengan bobot sisi yang non-negatif.
   - Algoritma ini menggunakan pendekatan greedy untuk mengoptimalkan jarak terpendek secara bertahap.

4. **Bellman-Ford Algorithm:**
   - Bellman-Ford digunakan untuk mencari jalur terpendek dari satu simpul ke semua simpul lainnya dalam graf, bahkan ketika bobot sisi bisa bernilai negatif.
   - Algoritma ini menggunakan pendekatan relaksasi dan dapat mendeteksi siklus negatif dalam graf.

5. **Kruskal's Algorithm:**
   - Kruskal digunakan untuk menemukan pohon lintasan terpendek dalam graf berbobot (graf yang memiliki bobot pada setiap sisi).
   - Algoritma ini menggunakan pendekatan greedy dengan mengurutkan sisi berdasarkan bobotnya dan secara bertahap menambahkan sisi-sisi terkecil ke dalam pohon lintasan.

6. **Prim's Algorithm:**
   - Prim digunakan untuk menemukan pohon lintasan terpendek dalam graf berbobot (graf yang memiliki bobot pada setiap sisi).
   - Algoritma ini menggunakan pendekatan greedy dengan memilih simpul dan sisi secara bertahap untuk membentuk pohon lintasan terpendek.

7. **Floyd-Warshall Algorithm:**
   - Floyd-Warshall digunakan untuk mencari jalur terpendek antara semua pasangan simpul dalam graf dengan bobot sisi yang mungkin bernilai negatif.
   - Algoritma ini menggunakan pendekatan dinamis dengan memeriksa setiap kemungkinan jalur terpendek.

Implementasi algoritma-algoritma ini memerlukan pemahaman yang baik tentang struktur data graf dan sering melibatkan representasi graf menggunakan matriks ketetanggaan atau daftar ketetanggaan. Implementasi dalam bahasa C biasanya memanfaatkan konsep struktur data dan pointer untuk merepresentasikan graf dan mengelola operasi-algoritma yang sesuai.

berikut merupakan implementasi algoritma graf dalam program bahasa C dari beberapa kasus/masalah

1.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Struktur untuk merepresentasikan informasi pengguna
struct User {
    char name[100];
    int age;
    struct User* friends[50]; // Daftar teman, maksimal 50 teman
    int numFriends; // Jumlah teman
};

// Fungsi untuk membuat pengguna baru
struct User* createUser(char name[], int age) {
    struct User* newUser = (struct User*)malloc(sizeof(struct User));
    strcpy(newUser->name, name);
    newUser->age = age;
    newUser->numFriends = 0;
    return newUser;
}

// Fungsi untuk menambahkan teman ke dalam daftar teman seorang pengguna
void addFriend(struct User* user, struct User* friend) {
    if (user->numFriends < 50) {
        user->friends[user->numFriends] = friend;
        user->numFriends++;
    } else {
        printf("Batas maksimum teman sudah tercapai untuk pengguna %s\n", user->name);
    }
}

// Fungsi untuk mencari indeks teman dalam daftar teman seorang pengguna
int findFriendIndex(struct User* user, char friendName[]) {
    for (int i = 0; i < user->numFriends; i++) {
        if (strcmp(user->friends[i]->name, friendName) == 0) {
            return i; // Teman ditemukan, kembalikan indeks teman
        }
    }
    return -1; // Teman tidak ditemukan
}

// Fungsi untuk menemukan jalur terpendek antara dua pengguna menggunakan DFS
int findShortestPath(struct User* start, struct User* end, struct User* visited[], int path[], int pathIndex) {
    if (start == end) {
        // Jika pengguna saat ini sama dengan pengguna tujuan, temukan jalur
        printf("%s ", start->name);
        for (int i = 0; i < pathIndex; i++) {
            printf("-> %s ", visited[path[i]]->name);
        }
        printf("\n");
        return 1; // Jalur ditemukan
    }

    visited[pathIndex] = start;
    path[pathIndex] = pathIndex;

    int foundPath = 0;

    // Lakukan DFS untuk setiap teman
    for (int i = 0; i < start->numFriends; i++) {
        if (findFriendIndex(start->friends[i], visited[pathIndex]->name) == -1) {
            foundPath = findShortestPath(start->friends[i], end, visited, path, pathIndex + 1);
            if (foundPath) {
                break; // Jalur sudah ditemukan, hentikan pencarian
            }
        }
    }

    return foundPath;
}

// Fungsi utama
int main() {
    struct User* users[100]; // Maksimal 100 pengguna
    int numUsers = 0;

    int choice;
    char name[100];
    int age;

    do {
        // Menu
        printf("\n=== Jaringan Sosial ===\n");
        printf("1. Tambah Pengguna\n");
        printf("2. Tambah Koneksi Teman\n");
        printf("3. Tampilkan Daftar Teman\n");
        printf("4. Tampilkan Jalur Terpendek\n");
        printf("0. Keluar\n");
        printf("Pilihan Anda: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                // Menambah pengguna baru
                printf("Masukkan nama pengguna: ");
                scanf(" %[^\n]", name);
                printf("Masukkan usia pengguna: ");
                scanf("%d", &age);
                users[numUsers] = createUser(name, age);
                numUsers++;
                printf("Pengguna %s ditambahkan.\n", name);
                break;
            case 2:
                // Menambah koneksi teman
                printf("Masukkan nama pengguna pertama: ");
                scanf(" %[^\n]", name);
                int index1 = -1;

                // Cari pengguna pertama dalam daftar pengguna
                for (int i = 0; i < numUsers; i++) {
                    if (strcmp(users[i]->name, name) == 0) {
                        index1 = i;
                        break;
                    }
                }

                if (index1 != -1) {
                    printf("Masukkan nama pengguna kedua: ");
                    scanf(" %[^\n]", name);
                    int index2 = -1;

                    // Cari pengguna kedua dalam daftar pengguna
                    for (int i = 0; i < numUsers; i++) {
                        if (strcmp(users[i]->name, name) == 0) {
                            index2 = i;
                            break;
                        }
                    }

                    if (index2 != -1) {
                        // Tambahkan teman antara kedua pengguna
                        addFriend(users[index1], users[index2]);
                        addFriend(users[index2], users[index1]);
                        printf("%s dan %s sekarang menjadi teman.\n", users[index1]->name, users[index2]->name);
                    } else {
                        printf("Pengguna kedua tidak ditemukan.\n");
                    }
                } else {
                    printf("Pengguna pertama tidak ditemukan.\n");
                }
                break;
            case 3:
                // Menampilkan daftar teman
                printf("Masukkan nama pengguna: ");
                scanf(" %[^\n]", name);
                int userIndex = -1;

                // Cari pengguna dalam daftar pengguna
                for (int i = 0; i < numUsers; i++) {
                    if (strcmp(users[i]->name, name) == 0) {
                        userIndex = i;
                        break;
                    }
                }

                if (userIndex != -1) {
                    printf("Daftar teman dari %s: ", users[userIndex]->name);
                    for (int i = 0; i < users[userIndex]->numFriends; i++) {
                        printf("%s ", users[userIndex]->friends[i]->name);
                    }
                    printf("\n");
                } else {
                    printf("Pengguna tidak ditemukan.\n");
                }
                break;
            case 4:
                // Menampilkan jalur terpendek
                printf("Masukkan nama pengguna pertama: ");
                scanf(" %[^\n]", name);
                int startIndex = -1;

                // Cari pengguna pertama dalam daftar pengguna
                for (int i = 0; i < numUsers; i++) {
                    if (strcmp(users[i]->name, name) == 0) {
                        startIndex = i;
                        break;
                    }
                }

                if (startIndex != -1) {
                    printf("Masukkan nama pengguna kedua: ");
                    scanf(" %[^\n]", name);
                    int endIndex = -1;

                    // Cari pengguna kedua dalam daftar pengguna
                    for (int i = 0; i < numUsers; i++) {
                        if (strcmp(users[i]->name, name) == 0) {
                            endIndex = i;
                            break;
                        }
                    }

                    if (endIndex != -1) {
                        // Menemukan jalur terpendek menggunakan DFS
                        struct User* visited[100];
                        int path[100];
                        int pathIndex = 0;
                        int foundPath = findShortestPath(users[startIndex], users[endIndex], visited, path, pathIndex);

                        if (!foundPath) {
                            printf("Tidak ada jalur terpendek antara %s dan %s\n", users[startIndex]->name, users[endIndex]->name);
                        }
                    } else {
                        printf("Pengguna kedua tidak ditemukan.\n");
                    }
                } else {
                    printf("Pengguna pertama tidak ditemukan.\n");
                }
                break;
            case 0:
                // Keluar dari program
                printf("Program berakhir.\n");
                break;
            default:
                printf("Pilihan tidak valid. Coba lagi.\n");
        }

    } while (choice != 0);

    // Dealokasi memori setelah program selesai
    for (int i = 0; i < numUsers; i++) {
        free(users[i]);
    }

    return 0;
}

output :

Penjelasan singkat mengenai program di atas:

1. Program menggunakan struktur struct User untuk merepresentasikan informasi pengguna, termasuk nama, usia, dan daftar teman.
2. Fungsi createUser membuat pengguna baru.
3. Fungsi addFriend menambahkan teman ke dalam daftar teman seorang pengguna.
4. Fungsi findFriendIndex mencari indeks teman dalam daftar teman seorang pengguna.
5. Fungsi findShortestPath mencari jalur terpendek antara dua pengguna menggunakan Depth-First Search (DFS).
6. Fungsi utama menyediakan menu untuk menambah pengguna, menambah koneksi teman, menampilkan daftar teman, dan menampilkan jalur terpendek. Program berjalan dalam loop hingga pengguna memilih untuk keluar (memasukkan pilihan 0).
7. Setelah program selesai, memori yang dialokasikan untuk pengguna akan di-dealokasi.

Program di atas menciptakan model jaringan sosial sederhana dengan pengguna dan daftar teman mereka. Jika Anda ingin melakukan pengembangan lebih lanjut atau menyesuaikan program sesuai kebutuhan, Anda dapat menambahkan fitur atau mengoptimalkan implementasi yang telah ada.

2.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_NODES 100

typedef struct Edge {
    int to;
    float weight;
    struct Edge* next;
} Edge;

typedef struct {
    char name[20];
    Edge* edges;
} Node;

typedef struct {
    Node nodes[MAX_NODES];
    int node_count;
} Graph;

void initGraph(Graph* graph) {
    graph->node_count = 0;
}

void addNode(Graph* graph, char* nodeName) {
    Node newNode;
    snprintf(newNode.name, sizeof(newNode.name), "%s", nodeName);
    newNode.edges = NULL;
    graph->nodes[graph->node_count++] = newNode;
}

void addEdge(Graph* graph, int from, int to, float weight) {
    Edge* newEdge = (Edge*)malloc(sizeof(Edge));
    newEdge->to = to;
    newEdge->weight = weight;
    newEdge->next = graph->nodes[from].edges;
    graph->nodes[from].edges = newEdge;

    // Uncomment the next line if the graph is directed
    // addEdge(graph, to, from, weight);
}

float dijkstra(Graph* graph, int start, int goal) {
    float distance[MAX_NODES];
    int visited[MAX_NODES] = {0};

    for (int i = 0; i < graph->node_count; ++i) {
        distance[i] = INT_MAX;
    }

    distance[start] = 0;

    for (int i = 0; i < graph->node_count; ++i) {
        int minDistance = INT_MAX;
        int current = -1;

        for (int j = 0; j < graph->node_count; ++j) {
            if (!visited[j] && distance[j] < minDistance) {
                minDistance = distance[j];
                current = j;
            }
        }

        if (current == -1) {
            break;
        }

        visited[current] = 1;

        Edge* edge = graph->nodes[current].edges;
        while (edge != NULL) {
            float newDist = distance[current] + edge->weight;
            if (newDist < distance[edge->to]) {
                distance[edge->to] = newDist;
            }
            edge = edge->next;
        }
    }

    return distance[goal];
}

int main() {
    Graph transportSystem;
    initGraph(&transportSystem);

    while (1) {
        printf("\nTransportation System Menu:\n");
        printf("1. Add Node\n");
        printf("2. Add Route\n");
        printf("3. Find Shortest Route\n");
        printf("4. Quit\n");

        int choice;
        printf("Enter your choice (1-4): ");
        scanf("%d", &choice);

        switch (choice) {
            case 1: {
                char nodeName[20];
                printf("Enter the new node: ");
                scanf("%s", nodeName);
                addNode(&transportSystem, nodeName);
                printf("Node '%s' added to the system.\n", nodeName);
                break;
            }

            case 2: {
                int from, to;
                float weight;
                printf("Enter the starting node index: ");
                scanf("%d", &from);
                printf("Enter the ending node index: ");
                scanf("%d", &to);
                printf("Enter the route distance: ");
                scanf("%f", &weight);
                addEdge(&transportSystem, from, to, weight);
                printf("Route added between nodes %d and %d with distance %f.\n", from, to, weight);
                break;
            }

            case 3: {
                int start, goal;
                printf("Enter the starting node index: ");
                scanf("%d", &start);
                printf("Enter the ending node index: ");
                scanf("%d", &goal);
                float distance = dijkstra(&transportSystem, start, goal);
                if (distance != INT_MAX) {
                    printf("Shortest route distance between nodes %d and %d: %f\n", start, goal, distance);
                } else {
                    printf("No route found between nodes %d and %d.\n", start, goal);
                }
                break;
            }

            case 4:
                printf("Exiting the program. Goodbye!\n");
                exit(0);

            default:
                printf("Invalid choice. Please enter a number between 1 and 4.\n");
                break;
        }
    }

    return 0;
}

output :

1. Struktur Data:

   • Edge adalah struktur yang merepresentasikan tepi antar node. Setiap tepi memiliki tujuan (to), bobot atau bobot jarak (weight), dan tautan ke tepi berikutnya (next).
   • Node adalah struktur yang merepresentasikan node dalam graf. Setiap node memiliki nama dan daftar tepi yang terhubung ke node tersebut.
   • Graph adalah struktur yang menyimpan daftar node dan jumlah total node dalam sistem transportasi.

2. Inisialisasi Graf:

   • initGraph digunakan untuk menginisialisasi struktur graf dengan mengatur jumlah node dalam sistem transportasi ke 0.

3. Penambahan Node dan Tepi:

   • addNode menambahkan node baru ke dalam graf dengan nama yang diberikan.
   • addEdge menambahkan tepi (rute) antara dua node dengan bobot atau jarak tertentu.

4. Algoritma Dijkstra:

   • Fungsi dijkstra mengimplementasikan algoritma Dijkstra untuk mencari jarak terpendek antara dua node dalam graf.
   • Variabel distance menyimpan jarak terpendek yang diketahui dari node awal ke setiap node lain.
   • Variabel visited menandai apakah suatu node telah dikunjungi.
   • Algoritma Dijkstra bekerja dengan iteratif memilih node dengan jarak terpendek yang belum dikunjungi, kemudian mengupdate jarak terpendek ke node tetangga.

5. Menu Utama:

   • Program memiliki loop utama yang memungkinkan pengguna memilih berbagai opsi melalui menu.
   • Opsi termasuk menambahkan node baru, menambahkan rute baru, mencari rute terpendek, dan keluar dari program.

6. Input dan Output:

   • Fungsi printf dan scanf digunakan untuk mencetak pesan ke layar dan membaca input dari pengguna.

7. Keluar dari Program:

   • Program dapat keluar ketika pengguna memilih opsi keluar dengan memanggil fungsi exit(0).

8. Catatan Tambahan:

   • Program ini mendukung penghapusan node dan tepi dari graf melalui fungsionalitas "Remove Node" dan "Remove Route". Namun, kode tersebut tidak sepenuhnya implementasikan mekanisme penghapusan, dan implementasi yang lengkap dapat memerlukan manajemen memori yang lebih canggih.

Semua ini membuat program memiliki kemampuan untuk memodelkan sistem transportasi di kota dengan menambahkan, menghubungkan, dan mencari rute terpendek antar node dalam graf.

3

#include <stdio.h>
#include <stdlib.h>

#define MAKS_PERANGKAT 100

typedef struct Tautan {
    int ke;
    struct Tautan* selanjutnya;
} Tautan;

typedef struct {
    char nama[20];
    Tautan* koneksi;
} Perangkat;

typedef struct {
    Perangkat perangkat[MAKS_PERANGKAT];
    int jumlah_perangkat;
} Jaringan;

void inisialisasiJaringan(Jaringan* jaringan) {
    jaringan->jumlah_perangkat = 0;
}

void tambahPerangkat(Jaringan* jaringan, char* nama_perangkat) {
    if (jaringan->jumlah_perangkat < MAKS_PERANGKAT) {
        Perangkat perangkat_baru;
        snprintf(perangkat_baru.nama, sizeof(perangkat_baru.nama), "%s", nama_perangkat);
        perangkat_baru.koneksi = NULL;
        jaringan->perangkat[jaringan->jumlah_perangkat++] = perangkat_baru;
        printf("Perangkat '%s' ditambahkan ke dalam jaringan.\n", nama_perangkat);
    } else {
        printf("Tidak dapat menambahkan lebih banyak perangkat. Batas maksimum telah tercapai.\n");
    }
}

void tambahKoneksi(Jaringan* jaringan, int dari, int ke) {
    if (dari >= 0 && dari < jaringan->jumlah_perangkat && ke >= 0 && ke < jaringan->jumlah_perangkat) {
        Tautan* tautan_baru = (Tautan*)malloc(sizeof(Tautan));
        tautan_baru->ke = ke;
        tautan_baru->selanjutnya = jaringan->perangkat[dari].koneksi;
        jaringan->perangkat[dari].koneksi = tautan_baru;

        // Uncomment baris berikut jika graf bersifat tak berarah
        // tambahKoneksi(jaringan, ke, dari);

        printf("Koneksi ditambahkan antara perangkat %d dan %d.\n", dari, ke);
    } else {
        printf("Indeks perangkat tidak valid. Harap masukkan indeks yang valid.\n");
    }
}

void tampilkanKoneksi(Jaringan* jaringan, int indeks_perangkat) {
    if (indeks_perangkat >= 0 && indeks_perangkat < jaringan->jumlah_perangkat) {
        printf("Perangkat yang terhubung dengan '%s':\n", jaringan->perangkat[indeks_perangkat].nama);
        Tautan* tautan_sekarang = jaringan->perangkat[indeks_perangkat].koneksi;
        while (tautan_sekarang != NULL) {
            printf("%s\n", jaringan->perangkat[tautan_sekarang->ke].nama);
            tautan_sekarang = tautan_sekarang->selanjutnya;
        }
    } else {
        printf("Indeks perangkat tidak valid. Harap masukkan indeks yang valid.\n");
    }
}

void dfs(Jaringan* jaringan, int indeks_perangkat, int terhubung[]) {
    terhubung[indeks_perangkat] = 1;
    printf("%s ", jaringan->perangkat[indeks_perangkat].nama);

    Tautan* tautan_sekarang = jaringan->perangkat[indeks_perangkat].koneksi;
    while (tautan_sekarang != NULL) {
        if (!terhubung[tautan_sekarang->ke]) {
            dfs(jaringan, tautan_sekarang->ke, terhubung);
        }
        tautan_sekarang = tautan_sekarang->selanjutnya;
    }
}

void temukanKomunitas(Jaringan* jaringan) {
    int terhubung[MAKS_PERANGKAT] = {0};
    int jumlah_komunitas = 0;

    printf("Komunitas dalam Jaringan:\n");
    for (int i = 0; i < jaringan->jumlah_perangkat; ++i) {
        if (!terhubung[i]) {
            printf("Komunitas %d: ", ++jumlah_komunitas);
            dfs(jaringan, i, terhubung);
            printf("\n");
        }
    }
}

int main() {
    Jaringan jaringan_komputer;
    inisialisasiJaringan(&jaringan_komputer);

    while (1) {
        printf("\nMenu Analisis Jaringan Komputer:\n");
        printf("1. Tambah Perangkat\n");
        printf("2. Tambah Koneksi\n");
        printf("3. Tampilkan Perangkat Terhubung\n");
        printf("4. Temukan Komunitas\n");
        printf("5. Keluar\n");

        int pilihan;
        printf("Masukkan pilihan Anda (1-5): ");
        scanf("%d", &pilihan);

        switch (pilihan) {
            case 1: {
                char nama_perangkat[20];
                printf("Masukkan nama perangkat baru: ");
                scanf("%s", nama_perangkat);
                tambahPerangkat(&jaringan_komputer, nama_perangkat);
                break;
            }

            case 2: {
                int dari, ke;
                printf("Masukkan indeks perangkat awal: ");
                scanf("%d", &dari);
                printf("Masukkan indeks perangkat tujuan: ");
                scanf("%d", &ke);
                tambahKoneksi(&jaringan_komputer, dari, ke);
                break;
            }

            case 3: {
                int indeks_perangkat;
                printf("Masukkan indeks perangkat: ");
                scanf("%d", &indeks_perangkat);
                tampilkanKoneksi(&jaringan_komputer, indeks_perangkat);
                break;
            }

            case 4:
                temukanKomunitas(&jaringan_komputer);
                break;

            case 5:
                printf("Keluar dari program. Sampai jumpa!\n");
                exit(0);

            default:
                printf("Pilihan tidak valid. Harap masukkan angka antara 1 dan 5.\n");
                break;
        }
    }

    return 0;
}

output:

Penjelasan singkat:

• Program ini menggunakan struktur data graf untuk merepresentasikan jaringan komputer.
• Setiap perangkat (node) memiliki nama dan daftar koneksi (tepi) ke perangkat lain.
• Fungsi-fungsi seperti addDevice, addConnection, displayConnections, findCommunities, dan lainnya mengelola operasi yang dapat dilakukan pada jaringan komputer.
• Fungsi dfs (Depth-First Search) digunakan untuk menemukan komunitas dalam jaringan komputer dengan mengunjungi perangkat secara rekursif dan mencetak perangkat yang terhubung ke dalam komunitas yang sama.
• Program memiliki menu utama yang memungkinkan pengguna melakukan berbagai operasi pada jaringan komputer.

Program ini memberikan dasar untuk analisis jaringan komputer sederhana menggunakan struktur data graf dan beberapa fungsi yang terkait. Anda dapat memodifikasi atau menambahkan fungsionalitas sesuai kebutuhan Anda.