Exercícios sobre Grafos

Temos aqui 3 exercícios resolvidos no mesmo código. As propostas são:

- Criar um metodo que verifique se o grafo é dirigido

- Construir um método que construa um grafo em Lista de Adjacência

- Construir um metodo que apartir de um grafo armazenado em uma lista
de adjacencia, apresente o grafo na tela na forma de matriz de
adjacencia

*** O programa a seguir precisa do arquivo txt. O arquivo segue abaixo: ***

8


0 8
1 7
2 6
3 5
4 4
5 3
6 2
7 1



7



0 2 1 0
2 3 3 0
3 7 5 0
5 7 2 0
6 7 9 0
2 5 4 0
3 7 6 0



LEGENDA:

QtdNos

NroNo/Valor

QtdArestas

No1/No2/Peso/Direcionado




Código:

class NoGrafo{
private:
int No, Peso, noEhDirigido;
NoGrafo *Aresta;
bool Dirigido;

public:
NoGrafo(){
Aresta = NULL;
No = 0;
noEhDirigido = 0;
Dirigido = false;
}

NoGrafo(int numero, int peso){
Aresta = NULL;
No = numero;
Peso = peso;
}

void setNo(int numero){
No = numero;
}

int getNo(){
return No;
}

void setPeso(int peso){
Peso = peso;
}

int getPeso(){
return Peso;
}

void setNoEhDirigido(int dirigido){
noEhDirigido = dirigido;
}

int getNoEhDirigido(){
return noEhDirigido;
}

void setAresta(NoGrafo *no){

NoGrafo *aux = getAresta();
if(aux == NULL){
Aresta = new NoGrafo(no->getNo(), no->getPeso());
}

else {
while(aux->getAresta() != NULL){
aux = aux->getAresta();
}

aux->Aresta = new NoGrafo(no->getNo(), no->getPeso());
}
}

NoGrafo *getAresta(){
return Aresta;
}

void imprimirAresta(){
NoGrafo *aux;
NoGrafo *aux2;
aux = getAresta();
if(aux != NULL){
while(aux != NULL){
cout << "-> [" << aux->getNo() << "] ";
aux = aux->getAresta();
}
}
cout << "-+";
}
};


class ListaGrafo{
private:
int qtdNos, qtdArestas;
NoGrafo *listaNosPrincipais;
bool ehDirigido;

public:
ListaGrafo(){
qtdNos = 0;
qtdArestas = 0;
ehDirigido = false;
}

void setQtdNos(int qtd){
qtdNos = qtd;
}

int getQtdNos(){
return qtdNos;
}

void setqtdArestas(int qtd){
qtdArestas = qtd;
}

int getqtdArestas(){
return qtdArestas;
}

void lerDadosDoArquivo(){
int qN;
int peso, numero;
int qtdArestas;
char Legenda;

cin >> qN;
cout << "\nEste grafo contem " << qN << " nos." << endl;
cout << "\nQue sao:"<< endl;
cout << "\nNoh\tPeso"<< endl;
setQtdNos(qN);
listaNosPrincipais = new NoGrafo[qN];

for(int i=0;i < getQtdNos(); i++){
cin >> numero;
cin >> peso;
listaNosPrincipais[numero].setNo(numero);
listaNosPrincipais[numero].setPeso(peso);
cout << "" << listaNosPrincipais[numero].getNo() << " \t"
<< listaNosPrincipais[numero].getPeso() << endl;
}
cin >> qtdArestas;
setqtdArestas(qtdArestas);
cout << "\nPossui " << getqtdArestas() << " arestas."<< endl;
cout << "\n" << endl;
for(int i=0; i < getqtdArestas(); i++){
int n1 = 0, n2 = 0, p = 0, d = 0;

cin >> n1;
cin >> n2;
cin >> p;
cin >> d;

listaNosPrincipais[n1].setAresta(new NoGrafo(n2, p));

if(d == 1){
ehDirigido = true;
listaNosPrincipais[n2].setAresta(new NoGrafo(n1, p));

listaNosPrincipais[n1].setNoEhDirigido(1);
listaNosPrincipais[n2].setNoEhDirigido(1);
}
}
}

void imprimirGrafoCompleto(){
cout << " LISTA DE ADJACENCIA" << endl;
cout << "\n" << endl;
for(int i = 0; i < getQtdNos(); i++){

cout << " [" << listaNosPrincipais[i].getNo() << "] ";
listaNosPrincipais[i].imprimirAresta();
cout << endl;
}
}

void isDirigido(){
if(ehDirigido == true){
cout <<"\n\t\t\t_________________________" << endl;
cout << "\n\t\t\tEste grafo EH DIRIGIDO!" << endl;
cout <<"\t\t\t_________________________" << endl;
}
else {
cout <<"\n\t\t\t____________________________" << endl;
cout << "\n\t\t\tEste grafo NAO EH DIRIGIDO! " << endl;
cout <<"\t\t\t____________________________" << endl;
}
}

void imprimirMatrizNaTela(){
NoGrafo *aux = NULL;
cout << "\n\n MATRIZ DE ADJACENCIA"<< endl;
cout << endl;
cout << " ";

for(int x = 0; x < getQtdNos(); x++){
cout << listaNosPrincipais[x].getNo() << " ";
}

cout << endl;

for(int x = 0; x < getQtdNos(); x++){

cout << listaNosPrincipais[x].getNo() << " ";

for(int i = 0; i < getQtdNos(); i++){
cout << " " <<
localizarNo(listaNosPrincipais[x].getAresta(), listaNosPrincipais[i].getNo()) << " ";
}

cout << endl;
}
}

int localizarNo(NoGrafo *primeiro, int indiceABuscar){
NoGrafo *aux = primeiro;
bool encontrou = false;
while(aux != NULL){
if(aux->getNo() == indiceABuscar){
encontrou = true;
break;
}
aux = aux->getAresta();
}

if(encontrou == true){
return 1;
}
else {
return 0;
}
}

};

int main(){
ListaGrafo *meuGrafo = new ListaGrafo();
meuGrafo->lerDadosDoArquivo();
meuGrafo->imprimirGrafoCompleto();
meuGrafo->isDirigido();
cout << endl;
meuGrafo->imprimirMatrizNaTela();
return 0;

}