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;

}

Proposta:

Definir a classe Grafos composta numa matriz adjacente.

class grafo {

int qtde; //QTD de nós
int *v; //Vetor peso
int **m; //Matriz de Adjacencia
int i,j;

public:

void madj(){
qtde=0;
v=NULL;
m=NULL;
}
void madj(int tam){
qtde=tam;
v= new(int[tam]);
*m=new(int[tam);

for(i=0;i< i="0;i<" j="0;j<">

MATRIZ DE ADJACÊNCIA

A matriz de adjacência é uma matriz de N x N (onde N é o número de vértices do grafo).

Ela inicialmente é preenchida toda com 0 e quando há uma relação entre o vértice do x (número da coluna)
com o do y (número da linha), matriz[x][y] é marcado um 1.


A matriz de adjacência mostra o relacionamento entre os nós de um grafo.

Se um nó a for adjacente a um nó b, então na matriz de adjacência M as entradas M[a,b]
e M[b,a] serão diferentes de 0.

O valor armazenado nestas entradas indicarão a quantidade de arestas existentes entre os vértices a e b.

Matriz Adjacente:

GRAFOS

O artigo de Leonhard Euler, publicado em 1736, sobre o problema das Sete Pontes de Königsberg, é considerado o primeiro resultado da teoria dos grafos. É também considerado um dos primeiros resultados topológicos na geometria; isto é, não dependente de quaisquer medidas. Isso ilustra a profunda conexão entre a teoria dos grafos e topologia.

Ponte de Konigsberg e a sua Representação Gráfica feita por Euler.

Um grafo é um conjunto de pontos, chamados vértices (ou nodos ou nós), conectados por linhas, chamadas de arestas (ou arcos).

Um grafo com 6 vértices e 7 arestas.

Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um grafo direcionado, ou dígrafo.

Nós = { A, B, C, D, E, F, G, H }
Arcos: E = {(A,A), (A,B), (A,C), (A,D), (C,D), (C,F), (E,G)}

Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial ou "o ponto".

Conceitos básicos de Teoria dos Grafos

Um laço (loop) num grafo ou num digrafo é uma aresta e em E cujas terminações estão no mesmo vértice. Um digrafo ou grafo é chamado simples se não tem laços e existe no máximo uma aresta entre quaisquer dois vértices.

Exemplo de Grafo

O grafo acima é um grafo simples com o conjunto de vértices V = {1, 2, 3, 4, 5, 6} e um conjunto de arestas E = {(1,2), (1,5), (2,3), (2,5), (3,4), (4,5), (4,6)}.

Uma aresta conecta dois vértices; esses dois vértices são ditos como incidentes à aresta.

A valência (ou grau) de um vértice é o número de arestas incidentes a ele, com loops contados duas vezes. No grafo de exemplo os vértices 1 e 3 possuem uma valência de 2, os vértices 2, 4 e 5 têm a valência de 3 e o vértice 6 tem a valência de 1. Se E é finito, então a valência total dos vértices é o dobro do número de arestas.

Em um dígrafo, distingue-se o grau de saída (o número de arestas saindo de um vértice) e o grau de entrada (o número de arestas entrando em um vértice). O grau de um vértice é igual à soma dos graus de saída e de entrada.

Dois vértices são considerados adjacentes se uma aresta existe entre eles. No grafo acima, os vértices 1 e 2 são adjascentes, mas os vértices 2 e 4 não são. O conjunto de vizinhos de um vértice consiste de todos os vértices adjascentes a ele. No grafo-exemplo, o vértice 1 possui 2 vizinhos: vértice 2 e vértice 5. Para um grafo simples, o número de vizinhos de um vértice é igual à sua valência.

Na computação, um grafo finito direcionado ou não-direcionado (com, digamos, n vértices) é geralmente representado por sua matriz de adjacência: uma matriz n-por-n cujo valor na linha i e coluna j fornece o número de arestas do i-ésimo ao j-ésimo vértices.

Um caminho é uma sequência de vértices tal que de cada um dos vértices existe uma aresta para o vértice seguinte. Um caminho é chamado simples se nenhum dos vértices no caminho se repete. O comprimento do caminho é o número de arestas que o caminho usa, contando-se arestas múltiplas múltiplas vezes. O custo de um caminho num grafo balanceado é a soma dos custos das arestas atravessadas. Dois caminhos são independentes se não tiverem nenhum vértice em comum, excepto o primeiro e o último.

No grafo de exemplo, (1, 2, 5, 1, 2, 3) é um caminho com comprimento 5, e (5, 2, 1) é um caminho simples de comprimento 2.

Se for possível estabelecer um caminho de qualquer vértice para qualquer outro vértice de um grafo, diz-se que o grafo é conexo. Se for sempre possível estabelecer um caminho de qualquer vértice para qualquer outro vértice mesmo depois de remover k-1 vértices, então diz-se que o grafo está k-conexo. Note que um grafo está k-conexo se, e somente se, contém k caminhos independentes entre qualquer par de vértices. O grafo de exemplo acima é conexo (e portanto 1-conexo), mas não é 2-conexo.

Um ciclo (ou circuito) é um caminho que começa e acaba com o mesmo vértice. Ciclos de comprimento 1 são laços. No grafo de exemplo, (1, 2, 3, 4, 5, 2, 1) é um ciclo de comprimento 6. Um ciclo simples é um ciclo que tem um comprimento pelo menos de 3 e no qual o vértice inicial só aparece mais uma vez, como vértice final, e os outros vértices aparecem só uma vez. No grafo acima, (1, 5, 2, 1) é um ciclo simples. Um grafo chama-se acíclico se não contém ciclos simples.

Uma árvore é um grafo simples acíclico e conexo. Às vezes, um vértice da árvore é distinto e chamado de raiz.

Um subgrafo de um grafo G é um grafo cujo conjunto dos vértices é um subconjunto do conjunto de vértices G, cujo conjunto de arestas é um subconjunto do conjunto de arestas de G, e cuja função w é uma restrição da função de G.

Um grafo parcial de um grafo G é um subgrafo com o mesmo conjunto de vértices que G. Uma árvore parcial é um grafo parcial que é árvore. Todo grafo tem pelo menos uma árvore parcial.

O grafo nulo é o grafo cujos conjuntos de vértices e de arestas são vazios.

Um conjunto independente em um grafo é um conjunto de vértices não adjacentes entre si. No exemplo acima, os vértices 1, 3 e 6 formam um conjunto independente e 3, 5 e 6 são outro conjunto independente.

Tipos de Árvores

As árvores binárias podem apresentar 4 tipos particulares.
1- Árvore degenerada : é semelhante a uma lista enncadeada pois apresenta apenas um nó por nível.
2- Heap : Nó raiz apresenta valor menor do que os nós filhos.
3- Árvore Completa : Os nós filhos existem somente o penúltimo e último nível da árvore
4- Árvore Cheia : Nós filhos aparecem somente no último nível.


Neste exercício, será criada uma árvore, no qual os valores serão inseridos pelo próprio programador, e o programa irá retornar uma resposta: Se esta árvore é degenerada.


#ifndef _BTREE_H
#define _BTREE_H

#include
#include
#include
#include
using namespace std;

class node; // prototipo da classe node

typedef node *ptrno; // criando um tipo de dados ptrno ponteiro para node

/*
Construcao da classe node.
*/

class node{
private:
int valor;
ptrno esq, dir;
public:
node(){valor=0; esq=dir=NULL;}
node(int v){valor=v; esq=dir=NULL;}
void setValor(int v){valor=v;}
void setEsq(ptrno e){esq=e;}
void setDir(ptrno d){dir=d;}
int getValor(){return valor;}
ptrno getEsq(){return esq;}
ptrno getDir(){return dir;}
};

class btree{
private:
ptrno raiz;
// as chamadas recursivas sao privadas e soh podem ser executadas a partir de metodos do objeto.
void push(ptrno &, int);
void showCentral(ptrno);
void showPreOrdem(ptrno);
void showPosOrdem(ptrno);
void showFolhas(ptrno);
bool isDegenerada(ptrno);
public:
btree(){raiz = NULL;}
ptrno getRaiz(){return raiz;}
// a seguir, as interfaces de funcoes recursivas
void push(int v);
void showCentral();
void showPreOrdem();
void showPosOrdem();
void showFolhas();
void isDegenerada();
};

// interface publica da funcao recursiva push (insere um novo nó na btree)
void btree::push(int v){
push(raiz, v);
}

// rotina push a ser chamada pela interface publica (insere um novo no na subarvore cuja raiz eh r
void btree::push(ptrno &r, int v){
ptrno aux;
if (r!=NULL){ // se o no atual nao for NULL, a insercao deve ser feita em uma das subarvores (esq ou dir)
if (v > r->getValor()){ // v eh maior que o valor do no e deve ser inserido na subarvore direita
aux=r->getDir();
push(aux, v);
r->setDir(aux);
}
else{ // v nao eh maior que o valor do no e deve ser inserido na subarvore esquerda
aux=r->getEsq();
push(aux, v);
r->setEsq(aux);
} // note que o objeto aux eh utilizado para recuperar possiveis alteracoes na subarvore
}
else{ // o trecho seguinte eh executado se no caminhamento pela arvore cairmos em um node NULL (r==NULL),
// o que indica que eh a posicao onde o valor deve ser inserido
aux=new(node); // usando construtor da classe node, valor=0, esq=dir=NULL (vide node())
aux->setValor(v);
r=aux;
}
}

void btree::showCentral(){
showCentral(raiz);
}

void btree::showCentral(ptrno r){ // caminhamento ESQ - RAIZ - DIR
if(r!=NULL){
showCentral(r->getEsq()); // imprime toda a subarvore ESQ com caminhamento central
cout <<>getValor() << " "; // imprime o valor armazenado na raiz showCentral(r->getDir()); // imprime toda a subarvore DIR com caminhamento central
}
}

void btree::showPreOrdem(){
showPreOrdem(raiz);
}

void btree::showPreOrdem(ptrno r){ // caminhamento RAIZ - ESQ - DIR
if(r!=NULL){
cout <<>getValor() << " "; showPreOrdem(r->getEsq());
showPreOrdem(r->getDir());
}
}

void btree::showPosOrdem(){
showPosOrdem(raiz);
}

void btree::showPosOrdem(ptrno r){ // caminhamento ESQ - DIR - RAIZ
if(r!=NULL){
showPosOrdem(r->getEsq());
showPosOrdem(r->getDir());
cout <<>getValor() << " "; } } void btree::showFolhas(){ showFolhas(raiz); } void btree::showFolhas(ptrno r){ // imprime folhas por caminhamento ESQ - RAIZ - DIR if(r!=NULL){ showFolhas(r->getEsq()); // imprime toda as folhas da subarvore ESQ com caminhamento central
if(r->getEsq()==NULL && r->getDir()==NULL) cout <<>getValor() << " "; // imprime o valor armazenado na raiz, se ela for folha showFolhas(r->getDir()); // imprime toda as folhas da subarvore DIR com caminhamento central
}
}
void btree::isDegenerada(){
if(isDegenerada(raiz) == true){
cout << "A arvore eh degenerada!"; } else { cout << "A arvore NAO eh degenerada!"; } } bool btree::isDegenerada(ptrno r){ // caminhamento ESQ - RAIZ - DIR if(r!=NULL){ cout << "Valor " <<>getValor() << " | "; if(r->getEsq() == NULL){
cout << "A esquerda eh NULL | "; } else { cout << "A esquerda NAO eh NULL | "; } if(r->getDir() == NULL){
cout << "A direita eh NULL | "; } else { cout << "A direita NAO eh NULL | "; } if( (r->getEsq() == NULL && r->getDir() != NULL) || (r->getEsq() != NULL && r->getDir() == NULL) ){
cout <<>getEsq() != NULL){
cout <<>getEsq());
} else {
cout <<>getDir());
}
} else if(r->getEsq() == NULL && r->getDir() == NULL){
cout <<>



using namespace std;

int main()
{
btree a1; // criando o objeto a1 da classe btree

// as linhas seguintes estao inserindo valores no objeto b1 usando o metodo push

a1.push(60);
a1.push(30);
a1.push(90);
a1.push(20);
a1.push(40);
a1.push(70);
a1.push(65);
a1.push(85);
a1.push(35);
a1.push(15);
a1.push(115);
a1.push(75);
a1.push(100);
a1.push(25);
a1.push(45);


// a seguir serao impressos na tela os valores armazenados no objeto a1
// usando as tres modalidades de caminhamento.

cout << "Caminhamento Central: ESQ - RAIZ - DIR" << endl; cout << endl;
a1.showCentral(); cout << endl; cout << endl;
cout << "Caminhamento PreOrdem: RAIZ - ESQ - DIR" << endl; cout << endl;
a1.showPreOrdem(); cout << endl; cout << endl;
cout << "Caminhamento PosOrdem: ESQ - DIR - RAIZ" << endl; cout << endl;
a1.showPosOrdem(); cout << endl; cout << endl;
a1.isDegenerada(); cout << endl; cout << endl;
cout << "Imprime Folhas da Arvore" << endl; cout << endl;

a1.showFolhas();

cout << "Programa executado!" << endl;
getch();
return 0;

}