Παράσταση

Ένας γράφος μπορεί εύκολα να παρασταθεί με δύο διαφορετικούς τρόπους:

πίνακα γειτνίασης (adjacency matrix).
λίστα γειτνίασης (adjacency list).

Και οι δύο τρόποι προϋποθέτουν ένα μονοσήμαντο σύστημα αρίθμησης των κόμβων.

Πίνακας γειτνίασης

Σε έναν γράφο με ν κόμβους ο πίνακας ν*ν γειτνίασης περιέχει 1 στις θέσεις (κ,λ) όπου υπάρχει ακμή από τον κόμβο κ στον κόμβο λ.

Παράδειγμα για γράφο 100 κόμβων:

/*
 * Adjacency matrix for a graph of 100 nodes
 */
static int adjmatrix[100][100];

main()
{
	int a, b;

	/* Read edges and connect them */
	while (scanf(%d %d", &a, &b) == 2)
		adjmatrix[a][b] = adjmatrix[b][a] = 1;
}

Λίστα γειτνίασης

Κάθε κόμβος συσχετίζεται με μια συνδεδεμένη λίστα γειτνίασης η οποία περιέχει τα ονόματα των άλλων κόμβων με τους οποίους συνδέεται ο συγκεκριμένος κόμβος. Οι λίστες για όλους τους κόμβους ν μπορούν να ξεκινούν από έναν μονοδιάστατο πίνακα μήκους ν ή από μια άλλη συνδεδεμένη λίστα.

Παράδειγμα για γράφο 10 κόμβων:

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

/*
 * Adjacency list for a graph of 10 nodes
 */
struct s_adjlist {
	int node;
	struct s_adjlist *next;
};

static struct s_adjlist *adj[10];

main()
{
	int a, b;
	struct s_adjlist *p;
	int i;

	/* Read edges and connect them */
	while (scanf("%d %d", &a, &b) == 2) {
		p = (struct s_adjlist *)malloc(sizeof(struct s_adjlist));
		p->node = b;
		p->next = adj[a];
		adj[a] = p;
		p = (struct s_adjlist *)malloc(sizeof(struct s_adjlist));
		p->node = a;
		p->next = adj[b];
		adj[b] = p;
	}
}