Implementació de Grafos Dirigits en Pascal: Arcos, Nodos i Recorrido en Profundidad

Implementació de grafos dirigits en Pascal

A continuació es presenta la implementació modular d'un grafo dirigit no ponderat mitjançant una matriu d'adjacència, juntament amb les operacions bàsiques sobre arcs, nodes i el recorregut en profunditat.

Unitat TArco

La unitat TArco defineix el tipus d'arc com un array de dos nodes, i les funcions per construir-lo i consultar-ne l'origen i el destí.

INTERFACE

USES TNodo;

TYPE TipoArco = ARRAY [1..2] OF TipoNodo;

PROCEDURE Construir (i, j: TipoNodo; VAR arco: TipoArco);

BEGIN
arco[1] := i;
arco[2] := j;
END;

FUNCTION Origen (arco: TipoArco): TipoNodo;

BEGIN
Origen := arco[1];
END;

FUNCTION Destino (arco: TipoArco): TipoNodo;

BEGIN
Destino := arco[2];
END;

Unitat TGrafoDirigido

Aquesta unitat implementa el grafo dirigit no ponderat. El grafo es representa amb un conjunt de nodes i una matriu d'adjacència de valors booleans.

INTERFACE

USES TElemento, TNodo, TArco(TipoNodo), TConjuntoNodos(TipoNodo), TConjuntoArcos(TipoArco);

TYPE
TipoMatrizAdyacencias = ARRAY[TipoNodo, TipoNodo] OF BOOLEAN;

TipoGrafo = RECORD
nodos: TipoConjuntoNodos;
matrizAdyacencias: TipoMatrizAdyacencias;
vector: ARRAY[1..MAX_NUM] OF TipoElemento (*)
END;

(*) Aquest vector només caldria si TipoElemento no és un tipus que serveixi com a índex d'array, i per permetre la correspondència (número, element). En la implementació següent no existeix aquest camp, i els nodes són de tipus TipoNodo 1..NUM_MAX_NODOS.

Implementació

IMPLEMENTATION

Creació i inserció

PROCEDURE CrearGrafoVacio (VAR grafo: TipoGrafo);

VAR
i, j: TipoNodo;

BEGIN
CrearConjuntoVacio (grafo.nodos);
FOR i := 1 TO NUM_MAX DO
FOR j := 1 TO NUM_MAX DO
grafo.matrizAdyacencias[i,j] := FALSE
END;

PROCEDURE InsertarNodo (nodo: TipoNodo; VAR grafo: TipoGrafo);

BEGIN
Poner(nodo, grafo.nodos)
END;

PROCEDURE InsertarArco (arco: TipoArco; VAR grafo: TipoGrafo);

VAR
i, j: TipoNodo;

BEGIN
i := Origen (arco);
j := Destino (arco);
IF EstaNodo(i, grafo) AND EstaNodo(j, grafo) THEN
grafo.matrizAdyacencias[i,j] := TRUE
ELSE
WRITELN('Error en Procedure InsertarArco: algun node de l''arc no està');
END;

Consultes i adjacències

FUNCTION EsGrafoVacio (grafo: TipoGrafo): BOOLEAN;

BEGIN
EsGrafoVacio := EsConjuntoVacio (grafo.nodos) (* no pot haver arcs els nodes dels quals no existeixen *)
END;

PROCEDURE Adyacentes (nodo: TipoNodo; grafo: TipoGrafo; VAR cjtoAdy: TipoConjuntoNodos);

VAR
aux: 1..NUM_MAX;

BEGIN
IF EstaNodo(nodo, grafo) THEN
BEGIN
CrearConjuntoVacio (cjtoAdy);
FOR aux := 1 TO NUM_MAX DO
IF grafo.matrizAdyacencias[nodo,aux] THEN
Poner(aux, cjtoAdy);
END
ELSE
WRITELN('Error en PROCEDURE Adyacentes: el node no està al graf');
END;

Esborrat

PROCEDURE BorrarNodo (nodo: TipoNodo; VAR grafo: TipoGrafo);

VAR
aux: TipoNodo;

BEGIN
(* Elimino el node del conjunt de nodes *)
Quitar (nodo, grafo.nodos);
(* Elimino les adjacències posant a zero els elements de la fila i de la columna del node *)
FOR aux := 1 TO NUM_MAX DO
grafo.matrizAdyacencias[nodo,aux] := FALSE;
FOR aux := 1 TO NUM_MAX DO
grafo.matrizAdyacencias[aux,nodo] := FALSE;
END;

PROCEDURE BorrarArco (arco: TipoArco; VAR grafo: TipoGrafo);

VAR
i, j: TipoNodo;

BEGIN
i := Origen (arco);
j := Destino (arco);
grafo.matrizAdyacencias[i,j] := FALSE
END;

Consulta de nodes i arcs

PROCEDURE Nodos (grafo: TipoGrafo; VAR cjtoN: TipoConjuntoNodos);

VAR
i: TipoNodo;

BEGIN
CrearConjuntoVacio (cjtoN);
FOR i := 1 TO NUM_MAX DO
IF Pertenece (i, grafo.nodos) THEN
Poner (i, cjtoN)
END;

PROCEDURE Arcos (VAR grafo: TipoGrafo; VAR cjtoArcos: TipoConjuntoArcos);

VAR
i, j: 1..MAX_NUM;
arco: TipoArco;

BEGIN
CrearConjuntoArcosVacio(cjtoArcos);
FOR i := 1 TO MAX_NUM DO
FOR j := 1 TO MAX_NUM DO
IF grafo.matrizAdyacencias[i, j] THEN
BEGIN
ConstruirArco(arco, i, j);
PonerConjuntoArcos(arco, cjtoArcos)
END
END;

Recorregut en profunditat

PROCEDURE RecorridoProfundidadGrafo ((*in*) grafo: TipoGrafo; (*in*) origen: TipoNodo; (*out*) VAR visitados: TipoConjuntoNodos);

VAR
adya: TipoConjuntoNodos;
aux: TipoNodo;

BEGIN
Poner (origen, visitados);
WriteLn (origen, ' ');
Adyacentes (origen, grafo, adya);
WHILE NOT EsConjuntoVacio (adya) DO
BEGIN
aux := Elegir (adya);
Quitar (aux, adya);
IF NOT Pertenece (aux, visitados) THEN
RecorridoProfundidadGrafo (grafo, aux, visitados)
END
END; (* RecorridoProfundidadGrafo *)