Estructura de datos (C) Iteración de gráficos y clasificación topológica
#include
#include
#include
#include
#include
#include
#include
#include
/* Código de estado del resultado de la función*/
#define TRUE 1
#define FALSO 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 Debido a que el valor de OVERFLOW se ha definido como 3 en math.h, elimine esta línea */
typedef int Status /* Status es el tipo de función y su; El valor es la función. El código de estado del resultado, como OK, etc.
*/
typedef int Boolean; es un tipo booleano, su valor es VERDADERO o FALSO */
typedef int Boolean es un tipo booleano, su valor es VERDADERO o FALSO; */
/* .................................*/
# define MAX_VERTEX_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind; /* {DirectedGraph,DirectedNet,UndirectedGraph,UndirectedNet}*/
typedef struct ArcNode
{{
int adjvex; /* La posición del vértice apuntado por este arco*/
struct ArcNode *nextarc /* Puntero al siguiente arco*/
InfoType *info; /* Puntero al peso de la red) */
}ArcNode /* Nodo de tabla
typedef struct
{
Datos VertexType; /* Información del vértice*/
ArcNode *firstarc /* La dirección del primer nodo de la tabla, un puntero al primer arco que depende del vértice*/
}VNode,AdjList [MAX_VERTEX_NUM];/* Nodo principal*/
estructura typedef
{
vértices de AdjList;
int vexnum, arcnum; /* Los números de vértice y arco del gráfico actual**
int kind;/* El indicador de tipo del gráfico*/
}ALGraph;
/* ..................*/
/* ...... ..... .............*/
/* ALGraphAlgo.cpp Operaciones básicas de almacenamiento de listas de adyacencia de gráficos (la estructura de almacenamiento es ALGraphDef.h)*/
int LocateVex(ALGraph G,VertexType u)
{ /* Condición inicial: el gráfico G existe, u y los vértices en G tienen las mismas características*/
/* Resultado: Si el vértice u existe en G, devuelve la posición del vértice en el gráfico; de lo contrario, devuelve -1 */
int i;
for(i=). 0;i< G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
if(strcmp(u ,G.vertices [i].data)==0)
devuelve i;
devuelve -1;
}
Status CreateGraph(ALGraph &G)
{ /* Utilice la estructura de almacenamiento de la tabla de conexiones vecinas para construir un gráfico G sin información relevante (use una función para construir 4 gráficos).
*/
int i,j,k;
int w; /* pesos */
VertexType va,vb;
ArcNode *p;
printf("Ingrese el tipo de gráfico (gráfico dirigido:0,red dirigida:1, gráfico no dirigido:2,red no dirigida:3):vexnum),&(G. arcnum));
printf("Ingrese el valor de %d vértices (<%d caracteres):\n",G.vexnum,MAX_NAME);
for( i =0;i
{
scanf("%s",G.vertices[i] . datos);
G.vertices[i].firstarc=NULL;
}
if(G.vertices[i].kind==1 | |G.kind==3) /* net**
printf("Ingrese los pesos, finales de arco y comienzos de arco de cada arco (lado) en orden (espacio como intervalo).\ n ");
else /* Figura*/
printf("Ingrese el peso, los extremos del arco y las cabezas del arco (con espacios como intervalo) de cada arco (borde) en orden :\n");
for(k=0;k
{
if( G.kind==1||G.kind==3) /* net*/
scanf("%d%s%s",&w,va , vb);
else /* Imagen*/
scanf("%s%s",va,vb);
i=LocateVex(G , va /* ArcTail*/
j=LocateVex(G,vb); /* ArcHead*/
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
if(G.kind===1||G.kind= =3) /*net*/
{
p->info=(int *)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* diagrama*/
p->nextarc=G.vertices[i].firstarc; * Insertar encabezado */
G.vertices[i].firstarc=p;
if(G.kind>=2) /* Gráfico o red no dirigido, generado Segundo nodo de tabla *
else
p->info=NULL; /* Imagen*/
p->info=NULL /* Imagen */
p->info=NULL; /* Figura */
p->info=NULL;
/* G.p>{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
if(G .kind==3) /* Red no dirigida */
{
p->info=(int*) malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL /* Gráfico no dirigido*/
p->nextarc=G.firstarc; /* Insertar encabezado*/
G.vertices[j].firstarc=p;
}
}
return OK;
}
void DestroyGraph(ALGraph &G)
{ /* Condiciones iniciales: el gráfico G existe . Resultado:
{
if(p)
return p->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,VertexType v,VertexType w)
{ /* Condición inicial: el gráfico G existe, v es G Un vértice en v, w es un vértice adyacente de v*/
//* Resultado de la operación: Devuelve el número de secuencia del siguiente vértice adyacente de v (en relación con w). */
/* Si w es el último vértice adyacente de v, devuelve -1 */
ArcNode *p;
int v1,w1 ;
v1=LocateVex(G,v); /* v1 es el número de vértice v en el gráfico G*/
w1=LocateVex(G,w) /* w1 es el; número de vértice v en el gráfico G*/
w1=LocateVex(G,w, /* w1 es el número de vértice w en el gráfico G*/
p= G. vertices[v1].firstcrashvertices[v1].firstarc;
while(p&&p->adjvex!=w1) /* El puntero p no está vacío y el nodo de la tabla al que apunta no es w */< / p>
p=p-> nextarc;
if(!p||!p->nextarc) /* w no se encuentra o w es el último vértice adyacente*/
return -1;
else /* p->adjvex==w */
return p->nextarc-& gt;adjvex; Relativo a w) El número de secuencia del siguiente vértice adyacente */
}
Booleano visitado[MAX_VERTEX_NUM];/* Matriz de banderas visitadas (número global) */
void(*VisitFunc)(char* v); /* Variable de función (número global) */
void DFS(ALGraph G,int v)
{ /* Recorra recursivamente el gráfico G en profundidad primero comenzando desde el v-ésimo vértice.
Algoritmo 7.5 */
int w;
VertexType v1,w1;
strcpy(v1,* GetVex(G,v));
visited[v]=TRUE; /* Establece el indicador de visita en TRUE (visited)*/
VisitFunc(G.vertices[v].data /* Visita el v-ésimo vértice); * /
for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))
if(!p>void DFSTraverse(ALGraph G,void(*Visit)(char*))
{ /* Recorrido en profundidad del gráfico G. Algoritmo 7.4 */
int v;
VisitFunc=Visit; /* Utilice la variable global VisitFunc para que DFS no tenga que configurar el parámetro del puntero de función*/
for(v= 0;v
{ /* Recorrido en profundidad del gráfico G. v++)
visited[v]=FALSE /* Inicializar matriz de indicadores de acceso; */
for(v=0;v
if(!visited[v])
DFS(G,v ); /* en la llamada DFS no visitada en el vértice */
printf("\n");
}
typedef int QElemType; Tipo de cola */
#include "LinkQueueDef.h"
#include "LinkQueueAlgo.h"
void BFSTraverse( ALGraph G,void(*Visita) (char*))
{/* Recorre el gráfico G de forma no recursiva en amplitud. Utilice una cola auxiliar Q y una serie de indicadores visitados.
Algoritmo 7.6 */
int v,u,w;
VertexType u1,w1;
LinkQueue Q;
for(v =0;v
visited[v]=FALSE; /* Establecer valor inicial*/
InitQueue(Q); Cola auxiliar Q */
for(v=0;v
if(!visited[v]) /* v aún no ha sido visitado*/
{
visited[v]=TRUE;
Visit(G. vertices[v].data);
EnQueue(Q,v); /* v ingresa a la cola*/
while(!QueueEmpty(Q))/ * la cola no está vacía */
{
DeQueue(Q,u); /* Elimina el elemento principal de la cola y configúrelo en u */
strcpy(u1, *GetVex(G,u ));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy( w1,*GetVex(G,w ))))
if(!visited[w]) /* w es un vértice adyacente de u que aún no ha sido visitado*/
{
visitado [w]=TRUE;
Visita(G.vertices[w].data);
EnQueue(Q,w); * w está en la cola*
}
}
}
}
printf("\ n");
}
void Display(ALGraph G)
{ /* Genera la matriz de adyacencia G del gráfico */
int i;
ArcNode *p;
switch(G.kind)
{ case DG: printf(" Gráfico dirigido \n"); break;
case DN: printf("Red dirigida \n");
case AG: printf("Gráfico no dirigido \n");
caso AN: printf("Red no dirigida \n ");
}
printf("%d vértices:\n",G.vexnum);
for(i=0;i
printf("%s ",G.vertices[i].data);
printf("\n%d arcos(bordes):\n", G.arcnum);
for(i=0;i
{
p=G vértices[i].firstarc;
mientras(p)
{
si(G. kind<=1) /* Hay una dirección*/
{
printf("%s→%s ",G.vertices[i].data,G.vertices [p->adjvex].data);
if(G.kind==DN) /* estructura de malla ki
nd==DN) /* Net */
printf(":%d " ,*(p->info));
}
else /* sin dirección (evitar la salida dos veces) */
{
if(i
{
printf("%s-%s ",G. vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==AN) /* net**
printf(":%d ",*(p->info));
}
}
}