Created
June 11, 2017 03:29
Star
You must be signed in to star a gist
PUC Minas - Grafos 2014/1
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//===================================================================== | |
// BIBLIOTECAS | |
//===================================================================== | |
#include <iostream> | |
#include <fstream> | |
#include <stdio.h> | |
#include <unistd.h> | |
#include <vector> | |
using namespace std; | |
//===================================================================== | |
// DEFINICAO DE CONSTANTES | |
//===================================================================== | |
#define MAX_VERTICE 500 | |
#define MAX_INT 0x7FFFFFFF | |
#define NULO -1 | |
#define BRANCO 0 | |
#define PRETO 1 | |
//===================================================================== | |
// DEFINICAO DE TIPOS | |
//===================================================================== | |
typedef short boolean; | |
typedef int Vertice; | |
typedef int Peso; | |
struct Aresta | |
{ | |
Vertice vi, vj; | |
Peso peso; | |
}; | |
struct cel | |
{ | |
int vertice = NULO; | |
int peso = NULO; | |
cel *prox; | |
}; | |
typedef struct cel Celula; | |
class Lista | |
{ | |
public: | |
int size = 0; | |
int vertice = NULO; | |
Celula *raiz; | |
Lista() | |
{ | |
raiz = new Celula(); | |
} | |
void pop_back() | |
{ | |
size--; | |
} | |
void push_back(int v, int peso) | |
{ | |
Celula *px = new Celula(); | |
px->vertice = v; | |
px->peso = peso; | |
at(size)->prox = px; | |
size++; | |
} | |
Celula* at(int x) | |
{ | |
Celula* rtn = raiz; | |
for(int i = 0; i < x; i++) | |
{ | |
rtn = rtn->prox; | |
} | |
return rtn; | |
} | |
Celula* contains(int x) | |
{ | |
Celula* p; | |
for(p = raiz; p != NULL; p = p->prox) | |
{ | |
if(p->vertice == x) | |
{ | |
return p; | |
} | |
} | |
return p; | |
} | |
}; | |
//===================================================================== | |
// CLASSE GRAFO | |
//===================================================================== | |
class Grafo | |
{ | |
private: | |
int numVertice, | |
numAresta; | |
Peso matriz[MAX_VERTICE][MAX_VERTICE]; | |
Lista* adj[MAX_VERTICE]; | |
//-------------------------------------------------------------------- | |
// inserirAresta: Insere uma nova aresta. | |
//-------------------------------------------------------------------- | |
void inserirAresta(Vertice v1, Vertice v2, Peso peso) | |
{ | |
if(v1 > MAX_VERTICE) | |
{ | |
printf("ERRO! Vertice %i nao existe no grafico", v1); | |
return; | |
} | |
if(v2 > MAX_VERTICE) | |
{ | |
printf("ERRO! Vertice %i nao existe no grafico", v2); | |
return; | |
} | |
//if(matriz[v1][v2] == NULO){ | |
//matriz[v1][v2] = peso; | |
adj[v1]->push_back(v2, peso); | |
Celula *p; | |
//cout << "Vert : " <<v1 << endl; | |
//for (p = adj[v1]->raiz; p != NULL; p = p->prox) | |
// printf( "%d .. ", p->vertice); | |
//cout << endl; | |
//cout << adj[v1]->raiz->vertice << endl; | |
//cout << adj[v1]->raiz->prox->vertice << endl; | |
//cout << adj[v1]->raiz->prox->prox->vertice << endl; | |
//cout << adj[v1]->raiz->prox->prox->prox->vertice << endl; | |
if(peso != NULO) | |
numAresta++; | |
//} | |
}//------------------------------------------------------------------- | |
//-------------------------------------------------------------------- | |
// isAresta: Retorna true se existe a aresta. | |
//-------------------------------------------------------------------- | |
boolean isAresta(Vertice v1, Vertice v2) | |
{ | |
//return (matriz[v1][v2] != NULO); | |
return adj[v1]->contains(v2)->peso != NULO; | |
}//------------------------------------------------------------------- | |
//-------------------------------------------------------------------- | |
// getAresta: Retorna o peso da aresta. | |
//-------------------------------------------------------------------- | |
Peso getAresta(Vertice v1, Vertice v2) | |
{ | |
//return (matriz[v1][v2]); | |
return adj[v1]->contains(v2)->peso; | |
}//------------------------------------------------------------------- | |
//-------------------------------------------------------------------- | |
// excluirAresta: Exclui uma aresta. | |
//-------------------------------------------------------------------- | |
void excluirAresta(Vertice v1, Vertice v2) | |
{ | |
if(v1 > numVertice) | |
{ | |
printf("ERRO! Vertice %i nao existe no grafico",v1); | |
return; | |
} | |
if(v2 > numVertice) | |
{ | |
printf("ERRO! Vertice %i nao existe no grafico",v2); | |
return; | |
} | |
/* | |
if(matriz[v1][v2] != NULO) | |
{ | |
matriz[v1][v2] = NULO; | |
numAresta--; | |
} | |
*/ | |
if(adj[v1]->contains(v2)->peso != NULO) | |
{ | |
adj[v1]->pop_back(); | |
numAresta--; | |
} | |
}//------------------------------------------------------------------- | |
//-------------------------------------------------------------------- | |
// excluirTodasArestas: Exclui todas as arestas. | |
//-------------------------------------------------------------------- | |
void excluirTodasArestas() | |
{ | |
for(int i = 0; i < MAX_VERTICE; i++) | |
{ | |
matriz[i][i] = NULO; | |
for(int j = i + 1; j < MAX_VERTICE; j++) | |
{ | |
matriz[i][j] = matriz[j][i] = NULO; | |
} | |
} | |
numAresta = 0; | |
}//------------------------------------------------------------------- | |
//-------------------------------------------------------------------- | |
// setNumVertice: Altera a variavel numVertice. | |
//-------------------------------------------------------------------- | |
void setNumVertice(int nVertice) | |
{ | |
if(nVertice > MAX_VERTICE) | |
{ | |
printf("ERRO: Numero de vertices\n"); | |
return; | |
} | |
//cout << 2; | |
numVertice = nVertice; | |
//cout << 4; | |
}//------------------------------------------------------------------- | |
public: | |
//-------------------------------------------------------------------- | |
// Construtor | |
//-------------------------------------------------------------------- | |
Grafo() | |
{ | |
numVertice = 0; | |
excluirTodasArestas(); | |
}//------------------------------------------------------------------- | |
//-------------------------------------------------------------------- | |
// Destrutor | |
//-------------------------------------------------------------------- | |
~Grafo() | |
{ | |
}//------------------------------------------------------------------- | |
int getGrau(int v) | |
{ | |
return getGrau(v, true); | |
} | |
int getGrau(int v, bool entrada) | |
{ | |
int resp = 0; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
if(entrada) | |
{ | |
if(isAresta(i, v) == true) | |
{ | |
resp++; | |
} | |
} | |
else | |
{ | |
if(isAresta(v, i) == true) | |
{ | |
resp++; | |
} | |
} | |
} | |
return resp; | |
} | |
bool isPendente(int x) | |
{ | |
if( getGrau(x) == 1) return 1; | |
else return 0; | |
} | |
bool isIsolado(int x) | |
{ | |
if( getGrau(x) == 0) return 1; | |
else return 0; | |
} | |
bool isBipartido() | |
{ | |
int cor[numVertice]; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
cor[i] = -1; | |
} | |
cor[0] = 0; | |
bool isb = isBipartido(0, cor, 0); | |
return isb; | |
} | |
bool isBipartido(int v,int cor[],int corPai) | |
{ | |
cor[v] = !corPai; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
bool aresta = isAresta(i,v); | |
if(aresta && cor[i] != cor[v]) | |
{ | |
if(cor[i] == -1) | |
{ | |
if(!isBipartido(i, cor, cor[v])) return false; | |
} | |
} | |
else if(aresta && cor[i] == cor[v]) return false; | |
} | |
return true; | |
} | |
void profundidade() | |
{ | |
int isVisitado[numVertice]; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
isVisitado[i] = 0; | |
} | |
int numco = 0; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
if(isVisitado[i] == 0) | |
{ | |
numco++; | |
profundidade(i, isVisitado); | |
} | |
} | |
} | |
void profundidade(int v,int isVisitado[]) | |
{ | |
isVisitado[v] = 1; | |
cout << isVisitado[v] << " - "; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
bool aresta = isAresta(i,v); | |
if(aresta && isVisitado[i] == 0) | |
{ | |
profundidade(i, isVisitado); | |
} | |
} | |
} | |
void largura() | |
{ | |
int isVisitado[numVertice]; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
isVisitado[i] = 0; | |
} | |
vector<int> queve; | |
isVisitado[0] = 1; | |
queve.push_back(0); | |
cout << 0 << " - "; | |
while(queve.size() != 0) | |
{ | |
int resp = 0; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
if(isAresta(queve[0], i) == true) | |
{ | |
resp++; | |
if(isVisitado[i] == 0) | |
{ | |
queve.push_back(i); | |
isVisitado[i] = 1; | |
cout << i << " - "; | |
} | |
} | |
} | |
//cout << " erase " << queve[0] << " next " << queve[1]; | |
queve.erase( queve.begin() ); | |
} | |
} | |
void dijkstra() | |
{ | |
int Ve0 = 0; | |
int distania[numVertice]; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
distania[i] = 0; | |
} | |
int isVisitado[numVertice]; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
isVisitado[i] = 0; | |
} | |
isVisitado[0] = 1; | |
distania[0] = 0; | |
for(int i = 1; i < numVertice; i++) | |
{ | |
if(isAresta(Ve0 , i) == 1) distania [i] = getAresta(Ve0 , i); | |
else distania [i] = MAX_INT; | |
} | |
passo2: | |
int minsos = MAX_INT; | |
int minidx = -1 ; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
if(distania[i] < minsos && !isVisitado[i] && distania[i] != -1) | |
{ | |
minsos = distania[i] ; | |
minidx = i; | |
} | |
} | |
isVisitado[minidx] = 1; | |
//cout << "mindx; "<<minidx << endl; | |
int resp = 0; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
if(minidx == -1) break; | |
if(isAresta(minidx, i) == true) | |
{ | |
resp++; | |
if(isVisitado[i] == 0 && distania[minidx]+getAresta(minidx, i)< distania[i]) | |
{ | |
distania[i] = distania[minidx]+getAresta(minidx, i); | |
} | |
} | |
} | |
for(int i = 0; i < numVertice; i++) | |
{ | |
if(isVisitado[i] == 0 && minidx != -1) goto passo2; | |
} | |
for(int i = 0; i < numVertice; i++) | |
{ | |
if(distania[i] == MAX_INT) distania[i] = -1; | |
cout << "0->" << i << ": " << distania[i] << endl; | |
} | |
} | |
bool isCompleto() | |
{ | |
for(int i = 0; i < numVertice; i++) | |
{ | |
for(int x = 0; x < numVertice; x++) | |
{ | |
bool aresta = isAresta(i,x); | |
if(!aresta) | |
{ | |
return false; | |
} | |
} | |
} | |
return 1; | |
} | |
bool isRegular() | |
{ | |
int defGrau = getGrau(0); | |
for(int i = 1; i < numVertice; i++) | |
{ | |
if(defGrau != getGrau(i)) return 0; | |
} | |
return 1; | |
} | |
bool isBalanceado() | |
{ | |
for(int i = 0; i < numVertice; i++) | |
{ | |
if(getGrau(i, true) != getGrau(i, false)) return 0; | |
} | |
return 1; | |
} | |
bool isNull() | |
{ | |
int defGrau = 0; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
if(defGrau != getGrau(i)) return 0; | |
} | |
return 1; | |
} | |
bool isEuleriano() | |
{ | |
if(!isConexo()) return 0; | |
if(!isBalanceado()) return 0; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
if(!numIsPar(getGrau(i))) | |
{ | |
return 0; | |
} | |
} | |
return 1; | |
} | |
bool isArvore() | |
{ | |
if (!isConexo()) return false; | |
if (!isBipartido()) return false; | |
if(numAresta == numVertice-1) return true; | |
} | |
void kruskal() | |
{ | |
Aresta aa[numAresta]; | |
int numArresta = 0; | |
int minaresa = MAX_INT; | |
for(int x = 0; x < numVertice; x++) | |
{ | |
for(int y = 0; y < numVertice; x++) | |
{ | |
if(!isAresta(x,y)) continue; | |
int gtt = getAresta(x, y); | |
if(gtt > minaresa) continue; | |
if() | |
minaresa = gtt; | |
aa[numAresta].vi = x; | |
aa[numAresta].vj = y; | |
aa[numAresta].peso = gtt; | |
} | |
} | |
numArresta++; | |
cout << aa[numArresta-1].vj << " - "; | |
} | |
void prim() | |
{ | |
int vertices[MAX_VERTICE]; | |
int nxm = 1; | |
vertices[0] = 0; | |
Aresta aa[numAresta]; | |
while(nxm < numVertice) | |
{ | |
int menor = 999; | |
int menorInd = 0; | |
for(int x = 0; x < nxm; x++) | |
{ | |
for(int i = 0; i < numVertice; i++) | |
{ | |
if(isAresta(i, vertices[x]) == true) | |
{ | |
int a = getAresta(i, vertices[x]) ; | |
if(a < menor) | |
{ | |
for(int c = 0; c < numAresta; c++) | |
{ | |
if(aa[c].vi == i && aa[c].vj == vertices[x]) goto out; | |
} | |
for(int c = 0; c < numVertice; c++) | |
{ | |
if(vertices[c] == i) goto out; | |
} | |
menor = a; | |
menorInd = i; | |
aa[nxm-1].peso = menor; | |
aa[nxm-1].vi = i; | |
aa[nxm-1].vj = vertices[x]; | |
} | |
} | |
out: continue; | |
} | |
} | |
vertices[nxm] = menorInd; | |
nxm++; | |
cout << menorInd; | |
} | |
} | |
bool isUnicursal() | |
{ | |
int impar = 0; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
if(!numIsPar(getGrau(i))) | |
{ | |
impar++; | |
} | |
if(impar > 2) return 0; | |
} | |
if(impar == 2) | |
return 1; | |
else return 0; | |
} | |
bool numIsPar(int n) | |
{ | |
if(n % 2 == 0) return 1; | |
else return false; | |
} | |
int numComponentes() | |
{ | |
int isVisitado[numVertice]; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
isVisitado[i] = 0; | |
} | |
int numco = 0; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
if(isVisitado[i] == 0) | |
{ | |
numco++; | |
numComponentes(i, isVisitado); | |
} | |
} | |
cout << "Componentes: " << numco << endl; | |
} | |
int numComponentes(int v,int isVisitado[]) | |
{ | |
isVisitado[v] = 1; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
bool aresta = isAresta(i,v); | |
if(aresta && isVisitado[i] == 0) | |
{ | |
numComponentes(i, isVisitado); | |
} | |
} | |
} | |
bool isConexo() | |
{ | |
if(numComponentes() > 1 ) return 0; | |
return 1; | |
} | |
void printGrauVizinhos(int v) | |
{ | |
int grau = getGrau(v); | |
for(int i = 0; i < numVertice; i++) | |
{ | |
bool aresta = isAresta(i,v); | |
if(aresta) | |
{ | |
int grauAdj = getGrau(i); | |
cout << "Adjacente: " << i << ": " << grauAdj << endl; | |
} | |
} | |
} | |
void printPendentesAndIsolados() | |
{ | |
int pendente = 0; | |
int isolado = 0; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
if(isIsolado(i)) | |
{ | |
isolado++; | |
} | |
else if(isPendente(i)) | |
{ | |
pendente++; | |
} | |
} | |
cout << "Pendentes: " << pendente << endl; | |
cout << "Isolados: " << isolado << endl; | |
} | |
Grafo getComplementar() | |
{ | |
for(int i = 0; i < numVertice; i++) | |
{ | |
for(int x = 0; x < numVertice; x++) | |
{ | |
bool aresta = isAresta(i,x); | |
if(aresta) | |
{ | |
inserirAresta(i, x, NULO); | |
} | |
else if (i != x) | |
{ | |
inserirAresta(i, x, 1); | |
} | |
} | |
} | |
} | |
//-------------------------------------------------------------------- | |
// lerGrafo: Realiza a leitura do grafo no arquivo. | |
//-------------------------------------------------------------------- | |
bool lerGrafo() | |
{ | |
bool resp = 1; | |
int temp; | |
//cout << 1; | |
//excluirTodasArestas(); | |
for(int i = 0; i < MAX_VERTICE; i++) | |
{ | |
adj[i] = new Lista(); | |
} | |
//Ler o numero de vertices | |
cin >> temp; | |
setNumVertice(temp); | |
resp = (numVertice > 0) ? true : false; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
inserirAresta(i, i, NULO); | |
for(int j = i+1; j < numVertice; j++) | |
{ | |
cin >> temp; | |
inserirAresta(i, j, temp); | |
inserirAresta(j, i, temp); | |
} | |
} | |
return resp; | |
} | |
bool lerDigrafo() | |
{ | |
bool resp = 1; | |
int temp; | |
//cout << 1; | |
//excluirTodasArestas(); | |
for(int i = 0; i < MAX_VERTICE; i++) | |
{ | |
adj[i] = new Lista(); | |
} | |
//Ler o numero de vertices | |
cin >> temp; | |
setNumVertice(temp); | |
resp = (numVertice > 0) ? true : false; | |
for(int i = 0; i < numVertice; i++) | |
{ | |
inserirAresta(i, i, NULO); | |
for(int j = 0; j < numVertice; j++) | |
{ | |
cin >> temp; | |
inserirAresta(i, j, temp); | |
} | |
} | |
return resp; | |
} | |
//-------------------------------------------------------------------- | |
// imprimir: Imprime o grafo. | |
//-------------------------------------------------------------------- | |
void imprimir() | |
{ | |
int i = 0, j = 0; | |
printf("\nN = (%i)\n\t",numVertice); | |
for(i = 0; i < numVertice; i++) | |
{ | |
if (i >= 100) | |
{ | |
printf("\t(%i) ",i); | |
} | |
else if(i >= 10) | |
{ | |
printf("\t(0%i) ",i); | |
} | |
else | |
{ | |
printf("\t(00%i) ",i); | |
} | |
} | |
for(i = 0; i < numVertice; i++) | |
{ | |
if (i >= 100) | |
{ | |
printf("\n(%i) - ",i); | |
} | |
else if(i >= 10) | |
{ | |
printf("\n(0%i) - ",i); | |
} | |
else | |
{ | |
printf("\n(00%i) - ",i); | |
} | |
for(j = 0; j < numVertice; j++) | |
{ | |
if(adj[i]->contains(j)->peso == NULO) | |
{ | |
printf("\t. "); | |
} | |
else | |
{ | |
printf("\t%i ",adj[i]->contains(j)->peso); | |
} | |
} | |
} | |
printf("\n"); | |
}//------------------------------------------------------------------- | |
void imprimirVerticeAresta() | |
{ | |
cout << numVertice << " " << (numAresta/2) << "\n"; | |
} | |
void imprimirSeEBipartido() | |
{ | |
if(isBipartido()) | |
cout << "Bipartido" << "\n"; | |
else | |
cout << "Não Bipartido" << "\n"; | |
} | |
void InOutGrau() | |
{ | |
int vertice; | |
cin >> vertice; | |
int xx = getGrau(vertice); | |
cout << xx; | |
} | |
}; | |
//===================================================================== | |
// FUNCAO PRINCIPAL | |
//===================================================================== | |
int main(int argc, char **argv) | |
{ | |
Grafo *g = new Grafo; | |
while (g->lerGrafo() == true) | |
{ | |
cout << "lido" << endl; | |
//g->numComponentes(); | |
//g->getComplementar(); | |
//cout << g->isRegular() << endl; | |
//cout << g->isBalanceado() << endl; | |
g->dijkstra(); | |
g->imprimir(); | |
//g->imprimirVerticeAresta(); | |
//g->imprimirPendenteAndIsolado(); | |
//g->imprimirSeEBipartido(); | |
delete g; | |
g = new Grafo; | |
} | |
delete g; | |
return 0; | |
}//-------------------------------------------------------------------- |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment