Γράφοι

Διομήδης Σπινέλλης
 Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Ορισμοί

Παράσταση

Ένας γράφος μπορεί εύκολα να παρασταθεί με δύο διαφορετικούς τρόπους:
  1. πίνακα γειτνίασης (adjacency matrix).
  2. λίστα γειτνίασης (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;
	}
}

Πρόσθετοι ορισμοί

Προτάσεις σε συνεκτικούς μη κυκλικούς γράφους

Οι παρακάτω προτάσεις είναι ισοδύναμες για πεπερασμένους γράφους με ν > 0 κόμβους:
  1. Ο γράφος Γ είναι συνεκτικός και μη κυκλικός.
  2. Αν διαγραφεί οποιαδήποτε ακμή ο γράφος θα πάψει να είναι συνεκτικός.
  3. Δύο διαφορετικοί κόμβοι συνδέονται από μια και μόνο μια απλή διαδρομή.
  4. Ο γράφος είναι μη κυκλικός και περιέχει ν - 1 ακμές.
  5. Ο γράφος είναι συνεκτικός και περιέχει ν - 1 ακμές.

Ψάξιμο κατά βάθος

Για να επισκευθούμε όλους τους κόμβους ενός γράφου με ν κόμβους χρειαζόμαστε έναν πίνακα λογικών μεταβλητών μιας διάστασης και μήκους ν ο οποίος περιέχει την τιμή "αληθές" για τους κόμβους τους οποίους έχουμε επισκευθεί. Η συστηματική επίσκεψη όλων των κόμβων γίνεται σύμφωνα με τα παρακάτω βήματα:
  1. Φυλάμε την τιμή "ψευδές" στον πίνακα επισκέψεων.
  2. Επισκεπτόμαστε όλους τους κόμβους που δεν έχουμε επισκευτεί.

Η επίσκεψη ενός κόμβου γίνεται σύμφωνα με τα παρακάτω βήματα:
  1. Σημειώνουμε στον πίνακα ότι έχουμε επισκευθεί τον κόμβο.
  2. Επισκεπτόμαστε όλους τους συνδεδεμένους κόμβους που δεν έχουμε επισκευθεί.
Το παρακάτω παράδειγμα περιέχει υλοποίηση για λίστα γειτνίασης: 
#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];
static int visited[10];

/*
 * Visit the nodes starting from node printing their value using
 * depth first search 
 */
static void
visit(int node)
{
	struct s_adjlist *p;

	visited[node] = 1;
	printf("%d\n", node);
	for (p = adj[node]; p != NULL; p = p->next)
		if (!visited[p->node])
			visit(p->node);
}

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;
	}
	/* Depth first search/print of the graph */
	for (i = 0; i < 10; i++)
		visited[i] = 0;
	for (i = 0; i < 10; i++)
		if (!visited[i])
			visit(i);
}
Αν το πρόγραμμα διαβάσει το γράφο: 
2 3
3 8
8 6
4 9
θα τυπώσει την παρακάτω σειρά επίσκεψης: 
0
1
2
3
8
6
4
9
5
7

Εφαρμογές

Βιβλιογραφία

Creative Commons License  Τελευταία αλλαγή: Δευτέρα, 2 Αυγούστου 2004 12:26 πμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».