Grafo

Representación por matriz de adyacencia
Es la forma más común de representación y la más directa. Consiste en una tabla de tamaño V x V, en que la que a[i][j] tendrá como valor 1 si existe una arista del nodo i al nodo j. En caso contrario, el valor será 0. Cuando se trata de grafos ponderados en lugar de 1 el valor que tomará será el peso de la arista. Si el grafo es no dirigido hay queasegurarse de que se marca con un 1 (o con el peso) tanto la entrada a[i][j] como la entrada a[j][i], puesto que se puede recorrer en ambos sentidos.
int V,A;
int a[maxV][maxV];

void inicializar()
{
int i,x,y,p;
char v1,v2;
// Leer V y Amemset(a,0,sizeof(a));
for (i=1; i<=A; i++)
{
scanf("%c %c %d\n",&v1,&v2,&p);
x=v1-'A'; y=v2-'A';
a[x][y]=p; a[y][x]=p;
}
}
Representación por lista de adyacencia
Otra forma de representar un grafo es por medio de listas que definen las aristas queconectan los nodos. Lo que se hace es definir una lista enlazada para cada nodo, que contendrá los nodos a los cuales es posible acceder. Es decir, un nodo A tendrá una lista enlazada asociada en la que aparecerá un elemento con una referencia al nodo B si A y B tienen una arista que los une. Obviamente, si el grafo es no dirigido, en la lista enlazada de B aparecerá la correspondiente referencia alnodo A.
Las listas de adyacencia serán estructuras que contendrán un valor entero (el número que identifica al nodo destino), así como otro entero que indica el coste en el caso de que el grafo sea ponderado. En el ejemplo se ha utilizado un nodo z ficticio en la cola (ver listas, apartado cabeceras y centinelas).
struct nodo
{
int v;
int p;
nodo *sig;
};

int V,A; // vértices yaristas del grafo
struct nodo *a[maxV], *z;

void inicializar()
{
int i,x,y,peso;
char v1,v2;
struct nodo *t;
z=(struct nodo *)malloc(sizeof(struct nodo));
z->sig=z;
for (i=0; i<V; i++)
a[i]=z;
for (i=0; i<A; i++)
{
scanf("%c %c %d\n",&v1,&v2,&peso);
x=v1-'A'; y=v2-'A';

t=(struct nodo *)malloc(sizeof(struct nodo));t->v=y; t->p=peso; t->sig=a[x]; a[x]=t;

t=(struct nodo *)malloc(sizeof(struct nodo));
t->v=x; t->p=peso; t->sig=a[y]; a[y]=t;
}
}
Búsqueda en profundidad
Se implementa de forma recursiva, aunque también puede realizarse con una pila. Se utiliza un array val para almacenar el orden en que fueron explorados los vértices. Para ello se incrementa una variableglobal id (inicializada a 0) cada vez que se visita un nuevo vértice y se almacena id en la entrada del array val correspondiente al vértice que se está explorando.
La siguiente función realiza un máximo de V (el número total de vértices) llamadas a la función visitar, que implementamos aquí en sus dos variantes: representación por matriz de adyacencia y por listas de adyacencia.
int id=0;
int val[V];

voidbuscar()
{
int k;
for (k=1; k<=V; k++)
val[k]=0;
for (k=1; k<=V; k++)
if (val[k]==0) visitar(k);
}

void visitar(int k) // matriz de adyacencia
{
int t;
val[k]=++id;
for (t=1; t<=V; t++)
if (a[k][t] && val[t]==0) visitar(t);
}

void visitar(int k) // listas de adyacencia
{
struct nodo *t;
val[k]=++id;
for (t=a[k]; t!=z;t=t->sig)
if (val[t->v]==0) visitar(t->v);
}
 
El resultado es que el array val contendrá en su i-ésima entrada el orden en el que el vértice i-ésimo fue explorado. Es decir, si tenemos un grafo con cuatro nodos y fueron explorados en el orden 3-1-2-4, el array val quedará como sigue:
val[1]=2; // el primer nodo fue visto en segundo lugar
val[2]=3; // el segundo nodo fue visto en...