fbpx

Struktur Data : Contoh Program Graph dalam Bahasa C

Buat fungsi untuk mencari garis/edge dengan bobot terkecil dari suatu graph berbobot. mencarinya dari adjacency list.


Kode Program

#include <stdio.h>
#include <stdlib.h>
#define N 6 //for example the maximum node is 6

//Data structure to save adjacency list from node in graph
struct node
{
    int dest, weight;
    struct node* next;
};
typedef struct node *ptrnode;

//Data structure to save graph object
struct graph
{
    //pointer of array to node to represent the adjacency list
    ptrnode head[N];
};
typedef struct graph *ptrgraph;

//Data structure to save graph edge
struct edge
{
    int src, dest, weight;
};

//function to make adjacency list from certain edge
ptrgraph createGraph(struct edge edges[], int n)
{
    //memory allocation to save data structure of graph
    ptrgraph graph = (ptrgraph)malloc(sizeof(struct graph));

    //initialize all head pointer to NULL
    for (int i = 0; i < N; i++)
    {
        graph->head[i] = NULL;
    }

    //add an edge one by one
    for (int i = 0; i < n; i++)
    {
        //take source and destination from node
        int src = edges[i].src;
        int dest = edges[i].dest;
        int weight = edges[i].weight;

        //make a new node form src to dest
        ptrnode newnode = (ptrnode)malloc(sizeof(struct node));
        newnode->dest = dest;
        newnode->weight = weight;

        //point newnode to head
        newnode->next = graph->head[src];

        //point head to newnode
        graph->head[src] = newnode;
    }
    return graph;
}

//function to print the representation of adjacency list
void printGraph(ptrgraph graph)
{
    int i;
    for (i = 0; i < N; i++)
    {
        //print node and all of node that connected
        ptrnode ptr = graph->head[i];
        while (ptr != NULL)
        {
            printf("%d -> %d (%d)\t", i, ptr->dest, ptr->weight);
            ptr = ptr->next;
        }
        printf("\n");
    }
}
//search the smallest weight from adjacency list
int minWeight(ptrgraph graph)
{
    int i, src, dest;
    int min = 10000000;
    for (i = 0; i < N; i++)
    {
        ptrnode ptr = graph->head[i];
        while (ptr != NULL)
        {
            if (ptr->weight < min)
            {
                min = ptr->weight;
                src = i;
                dest = ptr->dest;
            }
            ptr = ptr->next;
        }
    }
    printf("Edges with the smallest weight is (%d)\nOn the node connecting the vertices %d and %d\n", min, src, dest);
}

//main function
void main()
{
    //input some pair of array from x to y
    struct edge edges[] = {{0, 1, 6}, {1, 2, 7}, {2, 0, 5}, {2, 1, 4}, {3, 2, 10}, {4, 5, 1}, {5, 4, 4}};

    //count of edge
    int n = sizeof(edges) / sizeof(edges[0]);

    //make a graph
    ptrgraph graph = createGraph(edges, n);

    //print graph
    printGraph(graph);

    minWeight(graph);
}


Output


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Graph, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up