#include <iostream>
#include <cstdlib>
using namespace std;
class nodo {
public:
char nombre;
int status;
int grado;
nodo *next;
};
void muestra_lista(nodo *);
nodo *agrega_adyacente(nodo *,char,int);
nodo *anchura (char,nodo *);
int main() {
int Nnodo,
g=0,i,j,k,z,sum=0,ppeso;
bool c=false;
char Nini;
cout << "Ingrese cantidad de nodos: ";
cin >> Nnodo;
nodo *milista = new nodo[Nnodo];
int *grado = new int[Nnodo];
int **madj = new int*[Nnodo];
for(j=0;j<Nnodo;j++){
madj[j]= new int[Nnodo];
}
for(i=0;i<Nnodo;i++) {
milista[i].nombre = 'A'+i;
milista[i].next = NULL;
}
if(Nnodo!=1) cout << "nSI=1 y NO=0n";
for(i=0;i<Nnodo;i++) {
for (j=0;j<Nnodo;j++) {madj[i][j]=0;}}
for(i=0;i<Nnodo;i++) {
g=0;
for(j=0;j<Nnodo;j++) {
if(i!=j) {
int es_adj;
cout << "nNodo " << char('A'+i) << " adyacente al nodo " << char('A'+j) << " :";
cin >> es_adj;
if(es_adj) {
madj[i][j]=1;
if(Nnodo==1) {cout << "Peso del arco (" << i+1 << "," << j+1 <<") : ";
cin >> ppeso;}
agrega_adyacente(&milista[i],'A'+j,ppeso);
g++;
}}}
milista[i].grado=g;
sum=sum+g;
}
cout << "nnNodo | Adyacentes...n";
for(i=0;i<Nnodo;i++) {
cout << char('A'+i) << " |";
muestra_lista(milista[i].next);
cout << endl;
}
cout << "nBUSQUEDA EN ANCHURAn";
cout<<"Nodo inicial: ";
cin>>Nini;
cout << "nCola: ";
nodo *cola=NULL,*aux;
for(i=0;i<Nnodo;i++) {milista[i].status=1;}
for(i=0;i<Nnodo;i++) {
if(milista[i].nombre==Nini) {
milista[i].status=2;
cola=anchura(milista[i].nombre,cola);
}}
while(cola!=NULL) { //
for(i=0;i<Nnodo;i++) {
if(milista[i].nombre==cola->nombre) {
milista[i].status=3;
cout<<milista[i].nombre << " ";
aux=&milista[i];
aux=aux->next;
z=milista[i].grado;
}}
for(i=0;i<z;i++) { //trabaja con los adyacentes de A
for(j=0;j<Nnodo;j++) { //revisa los 5 para ver si son adyacentes
if(aux->nombre==milista[j].nombre) { //pregunta si B (y luego E) coincide con el puntero aux
if(milista[j].status==1) { // pregunta si es estado 1, 2 o 3 para...
cola=anchura(milista[j].nombre,cola); //vuelve a cambiar el puntero cola para q apunte a lo q apunta B (y luego E)
milista[j].status=2; //...cambiar el estado de 1 a 2
}}}
aux=aux->next;
}
cola=cola->next;
}
cout << endl;
cin.get();
return 0; //
}
void muestra_lista(nodo *lista) {
while(lista != NULL) {
cout << " -> " << lista->nombre;
lista = lista->next;
}}
nodo *agrega_adyacente(nodo *lista,char nombre,int ppeso) {
nodo *aux = lista;
nodo *nuevo = new nodo;
nuevo->nombre = nombre;
nuevo->next = NULL;
if(lista == NULL) {
lista = nuevo;
} else {
while(aux->next != NULL) {
aux = aux->next;
}
aux->next = nuevo;
}
return lista;
}
nodo *anchura (char nombre,nodo *lista) {
nodo *aux = lista;
nodo *nuevo = new nodo;
nuevo->nombre = nombre;
nuevo->next = NULL;
if(lista == NULL) {
lista = nuevo;
} else {
while(aux->next != NULL) {
aux = aux->next;
}
aux->next = nuevo;
}
return lista;
}
