Exercícios de Grafos III

O método a seguir irá ler uma matriz de Incidência e armazenar o grafo em uma Lista de Adjacência:

void matrizIncidencia(){
int x, y;

for ( int i = 1; i<= no; i++){
for ( int j = 1; i<=aresta ; j++){
if(matriz[j][i]!=0){
if(x!=0)
y=matriz[j][i];
else
x=matriz[j][i];
}
}
lista->setAresta(x, y, 1, 1 );
}
}

Exercícios sobre Grafos II

O exercício a seguir, irá ler uma matriz de incidência e armazenar o grafo e uma matriz de Adjacência.

Lembrando que este também necessita do arquivo txt que segue abaixo:


1

4

4
3
2
1

4

0 1 A 0
2 0 B 1
3 1 C 0
2 3 D 0

indice do nó para impressão
Qtde nos
nos
.
.
.
qtde arestas
n1 n2 aresta direção



Código:


using namespace std;
class node; // classe NODE
typedef node *ptrno;

class node;

typedef node *ptrno;

class node
{
private:
int vertice,peso;
ptrno prox;
public:
node(){
peso=0;vertice=0; prox=NULL;
}
void setPeso(int p){
peso=p;
}
void setVertice(int v){
vertice=v;
}
void setProx(node *p){
prox=p;
}
node *getProx(){
return prox;
}
};


class Grafo{
private:
int qtdnos;
int **matriz;
ptrno lista;
int *pesos;
public:
Grafo(){
qtdnos=0;
pesos=NULL;
matriz=NULL;
};

void lerArquivoIncidencia(int indice);
};


void Grafo::lerArquivoIncidencia(int indice){
int tamanho,n1,n2,aresta,direcao,qtdaresta,gambiarra;

cin>>tamanho; //le a qtd de NO do grafo
cin>>numerodono >>numerodono >>numerodono >>numerodono ;
cin>>qtdaresta;

matriz = new int*[qtdaresta]; //criacao do vetor q representa
colunas
for(int i = 0; i < tamanho; i++){
matriz[i] = new int[tamanho];
}


for(int k = 0; k < qtdaresta; k++){
for(int l = 0; l < tamanho; l++){
matriz[k][l] = 0;
}
}


for (int n=0;n < qtdaresta;n++){
cin>>n1;
cin>>n2;
cin>>aresta;
cin>>direcao;
matriz[n1][aresta]=1;
matriz[n2][aresta]=1;
}

for (int o=0;o < tamanho;o++){
for (int p=0;p < qtdaresta;p++){
cout << matriz[o][p]<< " ";
}
cout<< endl;
}
cout<< endl;
cout<< "O no " << indice << " tem os seguintes nos adjacentes: " << endl;


for(int r=0;r < qtdaresta;r++){
if(matriz[indice][r]==1){
for(int s=0;s < tamanho;s++){

if(( matriz[s][r]==1)&&(s!=indice))
cout << s <<" ";
}
}
}
}

int main(){
Grafo grafo1;
grafo1.lerArquivoIncidencia(1);
getchar();
}

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;

}