¡Urgente! ! ! ! ! Diseño del curso de estructura de datos.

> p=p->nextarc;

devolver p->adjvex;

}else

devolver -1;

}

//…………………… Recorrido en profundidad del gráfico………………

void DFS(ALGraph gra,int i){

visitado[i]=1;

int we1;

cout<

para (nosotros=firstadjvex(gra,gra.vertices[i]);nosotros>=0;nosotros=nextadjvex(gra,gra.vertices[i],nosotros)){

nosotros1=nosotros; p>

if(visitado[nosotros]==0)

DFS(gra,nosotros);

nosotros=nosotros1;

}

}

void DFSTravers(ALGraph gra){

int i;

for(i=0;i

visitó[i]=0;

}

para(i=0;i

if(visitado[i]==0)

DFS(gra,i);

}

cout<

}

//……………………………………………………………………………………

//…… …………Definición de cola y operaciones básicas……………………

typedef struct qnode{

int data;

estructura qnode * siguiente;

}qnode,*queueptr;

estructura typedef{

queueptr front;

queueptr rear;

}linkqueue;

//...Inicializa la cola...

void initqueue(linkqueue &q){

q.rear=(queueptr)malloc (sizeof(qnode));

q.front=q.rear;

q.front->next=NULL;

}

//...En cola...

int enqueue(linkqueue &q,int e){

queueptr p;

p=(queueptr )malloc(sizeof(qnode)); //El sistema genera el nodo qnode y lo asigna a p

if(!p)

devolver 0;

else{

p->data=e;

p->next=NULL;

q.rear ->siguiente=p;

q.rear=p;

devolver 1;

}

}

//...quitar de cola...

int quitar de cola(cola de enlace &q,int &e){

queueptr p;

if(q.front==q.rear)

devuelve 0;

p=q.front ->siguiente;

e=p->datos;

q.front->siguiente=p->siguiente;

if(q.rear= =p)

q.rear=q.front;

gratis(p);

devuelve 1;

}

//... Determinar si la cola está vacía...

int queueempty(linkqueue q){

if(q.front==q.rear )

devuelve 1;

devuelve 0;

}

//……………………………… …… ……………………………………

//…………Recorrido en amplitud del gráfico………………

void BFSTravers (ALGraph gra){

int i,e;

linkqueue q;

for(i=0;i

visitado[i]=0;

initqueue(q); //La cola adjunta almacena los vértices con una longitud de ruta de 1 2... que han sido visitados

for(i=0;i

if(!visited[i]){

visitó[i]=1;

cout<

enqueue(q,i);

while(!queueempty(q)){

dequeue(q,e);

for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra. vértices[e] ],nosotros)){

if(!visitamos[nosotros]){

visitamos[nosotros]=1;

cout<< gra.vertices[ nosotros].data<<" ";

enqueue(q,nosotros);

}

}

}

}

cout<

}

//……………………Encuentra las ramas conectadas del gráfico…… …………

void DFSTraversFL(ALGraph gra){

int i,count=1;

for(i=0; i

visitó[i]=0;

}

for(i=0;i

if(visited[i]==0){

cout<<"La rama conectada "<

DFS (gra,i);

// Para un gráfico conectado, solo necesita comenzar desde un vértice y realizar un recorrido en profundidad para acceder a todos los vértices

cout<

count++;

}

}

}

//……………………Utilice el algoritmo de Prim para encontrar el árbol de expansión mínimo………… ……

void PRIM(ALGraph gra,int g[][MAX_VERTEX_NUM],int n){

int lowcost[MAX_VERTEX_NUM],prevex[MAX_VERTEX_NUM];

int i ,j,k,min;

for(i=2;i<=n;i++){

bajo costo[i]=g[1][i ];

prevex[i]=1;

}

lowcost[1]=0;

for(i=2 ;i<= n;i++){

min=INFINITY;

k=0;

for(j=2;j<=n;j++ )

if(bajo costo[j]

min=bajo costo[j];

k=j;

}

cout<

bajo costo[k]=0;

for(j=2;j<=n;j++)

if(g[k ][j]

lowcost[j]=g[k][j];

prevex[j]=k;

}

cout<

}

}

//…………Encuentra el camino más corto…… ……

void ShortPath(MGraph G,char ch){ //Implementación del algoritmo de Dijkstra, de un punto determinado a otros puntos

int i,j,min,k,t ,w;

int v=0;

int final[MAX_VERTEX_NUM];

int bajo costo[MAX_VERTEX_NUM];

int q [MAX_VERTEX_NUM] [MAX_VERTEX_NUM];

k=LocateVex(G,ch);

for(i=0;i

final [i]=0;

lowcost[i]=G.arcs[k][i].adj;

for(j=0;j

q[i][j]=0;

if(lowcost[i]

q[i][ k]= 1;

q[i][i]=1;

}

}

bajo costo[k]= 0;

final[k]=1;

for(i=0;i

i++){

min=INFINITY;

for(j=0;j

if(!final[j])

if(bajo costo[j]

min=bajo costo[j];

v=j;

}

final[v]=1;

for(w=0;w

if(!final[w]&& (min+G.arcs[v][w].adj

lowcost[w]=min+G.arcs[v][w].adj; p>

for(t=0;t

q[w][t]=q[v][t];

q [w][w]=1;

}

}

for(i=0;i

if(i!=k){

cout<

cout << "Ruta más corta:";

if(lowcost[i]

for(j=0;j

if(q[i][j]&&j!=i)

cout<

cout<

cout<<"Longitud: "<

}else

cout<<"¿Tiene no existe "<

}

}

}

typedef estructura CSNode{

datos de caracteres;

estructura CSNode *firstchild,*nextsibling;

}CSNode,*CSTree;

//……………………Profundidad- primer árbol de expansión… ………………

void DFSTree(ALGraph gra,int v,CSTree &T){ //Salida secuencial después de la búsqueda en profundidad

visitado[v] =1;

int w,first=1;

CSTree p,q;

for(w=firstadjvex(gra,gra.vertices[v] );w>= 0;w=nextadjvex(gra,gra.vertices[v],w))

if(!visited[w]){

p=(CSTree )malloc(sizeof( CSNode));

p->data=gra.vertices[w].data;

p->firstchild=NULL;

p->ne

xtsibling=NULL;

if(first){

T->firstchild=p;

first=0;

}else

q->nextsibling=p;

q=p;

DFSTree(gra,w,q);

}

}

void DFSForest(ALGraph gra,CSTree &T){

T=NULL;

CSTree p,q;

int v;

for(v=0;v

visitó[v]=0;

for (v=0;v

if(!visited[v]){

p=(CSTree)malloc(sizeof(CSNode));

p->data=gra.vertices[v].data;

p->firstchild=NULL;

p->nextsibling=NULL;

p>

if(!T)

T=p;

else

q->nextsibling=p;

q=p;

DFSTree(gra,v,p);

}

}

// ………… ………Recorrido de preorden del árbol de expansión en profundidad………………

void Preorder(CSTree T){

if(T){

cout<data<<" ";

Reserva (T->primer hijo);

Reserva (T->siguiente hermano);

}

cout<

}

//……………………Encuentra el camino más corto entre u y v… ……… ………

void shortdistance(MGraph G){

int i,u,v,w,S,E;

char start, end;

int Distancia[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

cout<<"Por favor, introduzca dos vértices:";

cin>>start>>end ;

while(LocateVex(G,start)>=G.vexnum||LocateVex(G,end)>=G.vexnum){

cout<<"Sin vértice asociado encontró ! Vuelva a ingresar: ";

cin>>start>>end;

}

for(i=0;i

G.arcs[i][i].adj=0;

for(u=0;u

para (v=0;v

/p>

Distancia[u][v]=G.arcs[u][v].adj;

for(u=0;u

for(v=0;v

for(w=0;w

if(Distancia[ u][w]+Distancia[w][v]

Distancia[u][v]=Distancia[u][w]+Distancia[w][ v];

S=LocateVex(G,inicio);

E=LocateVex(G,fin);

if(Distancia[S][E ]==INFINITY)

cout<

else

El camino más corto desde cout<

}

//……………………Encontrar el camino más corto entre todos los vértices………………

void shortdistance(MGraph G){ //Implementación del algoritmo de Freud, dos vértices cualesquiera

int i,j,u,v,w;

int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

for(i=0; i

G.arcs[i][i].adj=0;

for(u=0;u

for(v=0;v

D[u][v]=G.arcs[u][v].adj;

for(u=0;u

for(v=0;v

for(w = 0;w

if(D[u][w]+D[w][v]

D[u][v]=D[u][w]+D[w][v];

for(i=0;i

for(j=0;j

if(D[i][j]==INFINITY)

cout<

else

cout<

}

void main(){

int i,j;

char ch='y';

MGraph G;