Skip to content

Instantly share code, notes, and snippets.

@BernardoGO
Created June 11, 2017 03:29
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save BernardoGO/462171e1935ee086df89a906b56dfc2e to your computer and use it in GitHub Desktop.
PUC Minas - Grafos 2014/1
//=====================================================================
// 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