Gustavo Rodrigues Barcelos
Os arquivos estão separados em 3 pastas diferentes, todas compilam com o seguinte código:
gcc Main.c -o executavel1.1 Breve resumo da teoria de grafos
2. Estruturas de Grafos
2.1 Matriz de Adjacência
2.1.1 Inputs
2.1.2 Codificação
2.1.3 Execução
2.2 Matriz de Incidência
2.2.1 Inputs
2.2.2 Codificação
2.2.3 Execução
3. Métodos de Busca
3.1 BFS
3.1.1 Alteraçẽos de BFS para Matriz de Adjacência
3.1.2 Alteraçẽos de BFS para Matriz de Incidência
3.2 DFS
3.2.1 Alteraçẽos de DFS para Matriz de Adjacência
3.2.2 Alteraçẽos de DFS para Matriz de Incidência
3.3 Resultados obtidos
4. Comparações
4.1 Lista de Adjacência:
4.2 Matriz de Adjacência:
4.3 Matriz de Incidência:
4.4 Representações visuais dos resultados obtidos:
5 Conclusões
A atividade da disciplina: Algoritmos e estrutura de dados II tem como objetivo implementar as estruturas de grafos aprendidas em aula, sendo elas: Listas de Adjacência, Matriz de Adjacência e Matriz de Incidência. Para realização dessa atividade foi disponilizado a implentação do código: "Lista de Adjacência", a fim de servir como base de estudo e referência para implementação dos demais.
1.1 Breve resumo da teoria de grafos: [ 1 ]
A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são empregadas estruturas chamadas de grafos, G(V,E), onde V é um conjunto não vazio de objetos denominados vértices (ou nós) e E (do inglês edges - arestas) é um subconjunto de pares não ordenados de V.
As aplicações relacionadas a teoria de grafos são diversas e estão presentes em basicamente todos os lugares, grafos estão presentes em aparelhos GPS, nos diretórios de um computador, em redes sociais, em um mapa rodoviário, um sistema de distribuição de água ....
Representação Visual:
A imagem acima representa um grafo G(6,7). 6 Vértices e 7 arestas
Em computação os grafos podem ser representados de diversas formas, nesse tópico será abordado somente as estruturas implementadas: Matriz de Adjacência e Matriz de Incidência
Esse tipo de representação consiste em uma matriz N x N ( ADJ[N][N] ), na qual N é o número de vértices do grafo. As posições (i,j) da matriz representam se há ou não ligação entre os vétices indicados. Suponha que exista um grafo G, tal que G contenha pelo menos dois ou mais vértices, um vértice X(origem) e um vértice Y(destino), caso o valor contido na matirz ADJ na posição: ADJ[X][Y] for igual a 1, significa há uma aresta que parte de X e incide em Y.
A pasta: Matriz de Adjacencia contém um arquivo nomeado de "input.txt", que fornece os dados para formação de um grafo. As entradas são organizadas da seguinte forma:
| Instrução | Representação |
|---|---|
| A primeira linha indica o número de vértices do grafo |  |
| As demais linhas indicam os vértices e seus vértices adjacentes, começando pelo vértice 0. A segunda linha representa o vértice 0, a terceira o vértice 1.... |  |
| As linhas são compostas por colunas e cada coluna indica o vértice adjacente. |  |
| Todas as linhas são encerradas com o valor -1, esse valor não é computado e serve apenas como referência. |  |
-
Conteúdo armazenado em input.txt:
8 1 2 -1 0 3 -1 0 4 5 -1 1 -1 2 5 6 -1 2 4 6 7 -1 4 5 7 -1 5 6
-
Representação visual de input.txt:
Os códigos referentes a matriz de adjacência se encontram em: Matriz Adjacencia/Adj.h
A representação dessa estrutura na linguagem C se deu da seguinte forma:
struct Vertex{ //Estrutura que representa um Vértice
int value;
};
struct Graph{
int V; //Número de Vértices
int E; //Número de Arestas
vertex **adj; //Matriz de Adjacência
};A função InitializeGraph(char *adrees), sofreu algumas pequenas modificações comparadas com a Lista de adjacência. Na estrutura em si, a principal diferença foi no caminhamento entre os vértices adjacentes, o código agora 'caminha' na matriz de adjcência buscando os índices do vértices adjacentes. Além disso a leitura e inserção do arquivo input ocorre nessa etapa.
vertex InitializeVertex(int value){
vertex aux = malloc(sizeof(vertex));
aux->value = value;
return aux;
}
graph InitializeGraph(char *adrees){
FILE *arq;
int V; //Número de Vértices
int origem = 0, destino; //Variáveis auxiliares para leitura de arq
arq = fopen(adrees,"r");
/*Verificando se foi possível abrir o arquivo*/
if (arq == NULL){ printf("Erro: Nao foi possivel abrir o arquivo"); return NULL;}
fscanf(arq,"%d",&V); //Lendo o número de vértices
graph G = malloc(sizeof(graph));
G->V = V;
G->E = 0;
G->adj = (vertex **)calloc(V,sizeof(vertex));
for(int i = 0; i < V; i++)
G->adj[i] = (vertex *)calloc(V,sizeof(vertex));
for(int i = 0; i < V; i++)
for(int j = 0; j < V; j++)
G->adj[i][j] = InitializeVertex(0); //Atribuindo valores default a matriz
while (!feof(arq)){ //Leitura dos demais dados do arquivo
if(origem >= V) break;
fscanf(arq,"%d",&destino);
if(destino != -1)
GraphInsert(G,origem,destino);
else
origem++;
}
fclose(arq);
return G;
}A função: GraphInsert(graph G, int v1, int v2) insere as arestas ou conexões entre os vértices do grafo. Essa função recebe como parâmetro 2 índices de vértices, v1 indicando a origem e v2 o destino. Se os valores de v1 e v2 forem válidos a matriz ADJ[v1][v2] recebe 1.
void GraphInsert(graph G, int v1, int v2){
vertex origem = InitializeVertex(v1);
vertex destino = InitializeVertex(v2);
if( (origem->value >= G->V) || (destino->value >= G->V) ){ printf("\n\nErro, valores incompativeis.\n\n"); return; }
if(G->adj[origem->value][destino->value]->value == 0){
G->adj[origem->value][destino->value]->value = 1;
G->E++;
}
free(origem);
free(destino);
}Por fim, as funções: PrintMatrix(graph G) e PrintGraph(graph G) fornecem representação dos resultados obtidos:
void PrintMatrix(graph G){
printf("\n\n==================================================================================================");
printf("\n\n\tMatriz de Adjacencia:\n\n");
for(int i = 0; i < G->V; i++){
if(i == 0){
printf("\t\t ");
for(int j = 0; j < G->V; j++)
printf(" %d ",j);
printf("\n");
}
printf("\t\t");
for(int j = 0; j < G->V; j++){
if(j==0){
printf("%d-> ",i);
}
printf("[%d] ", G->adj[i][j]->value);
}
printf("\n");
}
}
void PrintGraph(graph G){
printf("\n\n\tVertices e Arestas:\n");
for(int i = 0; i < G->V; i++){
printf("\n\t\t%d-> ",i);
for(int j = 0; j < G->V; j++)
if(G->adj[i][j]->value == 1)
printf("%d ",j);
}
printf("\n\n\tInformacoes do Grafo:");
printf("\n\n\t\tNumero de vertices: %d", G->V);
printf(" Numero de arestas: %d",G->E);
printf("\n==================================================================================================\n");
}Ao compilar e executar o código de Matriz Adjacencia epesra-se com a leitura de "input.txt" obtem-se o seguinte resultado:
Esse tipo de representação consiste em uma matriz N x M (INC[N][M]), na qual N é o número de vértices e M o número de arestas do grafo. As posições (i,j) da matriz representa se há ou não incidencia da aresta no vétice indicado. Diferente da matriz de ajacência as conxões na matriz de incidência são representadas pelas colunas. Suponha que exista um grafo G, tal que G contenha pelo menos dois ou mais vértices, um vértice X(origem) e um vértice Y(destino), caso haja uma aresta J que parte de X e incide em Y a representação na matriz será indicada da seguinte forma: INC[X][J] = -1 e INC[Y][J] = 1. Dessa forma cada coluna contem somente no máximo 2 valores, -1 para idicar a origem da aresta e 1 para indicar o destino.
A pasta: Matriz de Incidencia contém um arquivo nomeado de "input.txt", que fornece os dados para formação de um grafo. As entradas são organizadas da seguinte forma:
| Instrução | Representação |
|---|---|
| A primeira linha indica o número de vértices do grafo seguido do número de arestas |  |
| As demais linhas indicam as arestas do grafo sendo o primeiro número o vértice de origem e o segundo o vértice de destino. |  |
-
Conteúdo armazenado em input.txt:
8 20 0 1 0 2 1 3 1 0 2 0 2 4 2 5 3 1 4 2 4 5 4 6 5 2 5 4 5 6 5 7 6 4 6 5 6 7 7 5 7 6
-
Representação visual de input.txt:
Os códigos referentes a matriz de adjacência se encontram em: Matriz Adjacencia/Adj.h
A representação dessa estrutura na linguagem C se deu da seguinte forma:
struct Vertex{ //Estrutura que representa um Vértice
int value;
};
struct Graph{
int V; //Número de Vértices
int E; //Número de Arestas
vertex **inc; //Matriz de Incidência
};A função InitializeGraph(char *adrees), sofreu algumas pequenas modificações comparadas com a Lista de adjacência. Na estrutura em si, a principal diferença foi no caminhamento entre os vértices adjacentes, o código agora 'caminha' na matriz de incidência buscando arestas que partem de um vértice e incidem em outro, além de caminhar nas colunas também caminha nas linhas para achar o índice do vértice incidente. Além disso a leitura e inserção do arquivo input ocorre nessa etapa.
vertex InitializeVertex(int value){
vertex aux = malloc(sizeof(vertex));
aux->value = value;
return aux;
}
graph InitializeGraph(char *adrees){
FILE *arq;
int V; //Número de Vértices
int E; //Número de arestas
int inci1 = 0, inci2=0; //Variáveis auxiliares para leitura de arq
int numAresta = 0;
arq = fopen(adrees,"r");
/*Verificando se foi possível abrir o arquivo*/
if (arq == NULL){ printf("Erro: Nao foi possivel abrir o arquivo"); return NULL;}
fscanf(arq,"%d" "%d",&V,&E); //Lendo o número de vértices e arestas
graph G = malloc(sizeof(graph));
G->V = V;
G->E = E;
G->inc = (vertex **)calloc(V,sizeof(vertex));
for(int i = 0; i < V; i++)
G->inc[i] = (vertex *)calloc(E,sizeof(vertex));
for(int i = 0; i < V; i++)
for(int j = 0; j < E; j++)
G->inc[i][j] = InitializeVertex(0); //Atribuindo valores default a matriz
while (!feof(arq)){ //Leitura dos demais dados do arquivo
if(inci1 >= V || inci2 >= V) break;
if(numAresta >= E) break;
fscanf(arq,"%d" "%d",&inci1, &inci2);
GraphInsert(G,numAresta,inci1,inci2);
numAresta++;
}
fclose(arq);
return G;
}A função: GraphInsert(graph G, int aresta, int v1, int v2) insere as origens e destino das arestas do grafo. Suponha que que a aresta 00 tem origem no vértice 1 e destino no vértice 7. Sua representação na matriz(INC) será: INC[1][00] = -1 e INC[7][00] = 1.
void GraphInsert(graph G, int aresta, int v1, int v2){
vertex inci1 = InitializeVertex(v1);
vertex inci2 = InitializeVertex(v2);
if( (inci1->value >= G->V) || (inci2->value >= G->V) || (aresta >= G->E) ){ printf("\n\nErro, valores incompativeis.\n\n"); return; }
if(G->inc[inci1->value][aresta]->value == 0){
G->inc[inci1->value][aresta]->value = -1;
G->inc[inci2->value][aresta]->value = 1;
}
free(inci1);
free(inci2);
}Por fim, as funções: PrintMatrix(graph G) e PrintGraph(graph G) fornecem representação dos resultados obtidos:
void PrintMatrix(graph G){
printf("\n\n==================================================================================================");
printf("\n\n\tMatriz de Incidencia:\n\n");
for(int i = 0; i < G->V; i++){
if(i == 0){
printf("\t\t ");
for(int j = 0; j < G->E; j++)
printf(" %.2d ",j);
printf("\n");
}
printf("\t\t");
for(int j = 0; j < G->E; j++){
if(j==0){
printf("%d-> ",i);
}
if(G->inc[i][j]->value >= 0) printf("[%.2d] ", G->inc[i][j]->value);
else printf("[%d] ", G->inc[i][j]->value);
}
printf("\n");
}
}
void PrintGraph(graph G){
printf("\n\n\tVertices e Arestas:\n");
for(int i = 0; i < G->V; i++){
printf("\n\t\t%d-> ",i);
for(int j = 0; j < G->E; j++)
if(G->inc[i][j]->value == -1)
printf("%d ",j);
}
printf("\n\n\tInformacoes do Grafo:");
printf("\n\n\t\tNumero de vertices: %d", G->V);
printf(" Numero de arestas: %d",G->E);
printf("\n==================================================================================================\n");
}Ao compilar e executar o código de Matriz Adjacencia epesra-se com a leitura de "input.txt" obtem-se o seguinte resultado:
Um algoritmo de busca (ou de varredura) é qualquer algoritmo que visita todos os vértices de um grafo andando pelos arcos de um vértice a outro. Há muitas maneiras de fazer uma tal busca. Cada algoritmo de busca é caracterizado pela ordem em que visita os vértices.[ 2 ]
3.1 BFS [3]
A implementação do algoritmo BFS coloca cada vértice do gráfo em uma de tres categorias:
- -1 -> Visitado (preto)
- 0 -> Não visitado (branco)
- 1 -> Em análise (Cinza)
O objetivo do algoritmo é marcar cada vértice como visitado, evitando ciclos. O algoritmo funciona da seguinte maneira:
- Define a cor branca para todos os vértices.
- Começa adicionando qualquer um dos vértices do gráfico no final de uma fila "em análise" e altera sua cor para cinza.
- Pegue o item da frente da fila e adiciona-o à lista de vértices visitados.
- Adiciona os vértices ajacentes ao vértice adicionado a lista de visitados na fila "em análise"
- Continua repetindo as etapas 2 e 3 até que a fila esteja vazia.
- Ao final da chamada recursiva altera a cor do vértice analisado para preto.
As alterações realizadas no método BFS, comparando com o método de Lista de Adjacencia foram poucas. Dentro do laço While, para percorrer os vértices adjacentes agora é necessário um laço for que caminha nas colunas da matriz adj:
void BFS(graph G, vertex v){
int cor[G->V]; // -1 = Preto, 0 = Branco, 1 = Cinza
int d[G->V];
int pi[G->V];
Fila *f =FFVazia();
printf("\n\n\tMetodo de busca BFS: \n");
for(int i = 0; i < G->V; i++)
if(i != v->value){
cor[i] = 0;
d[i] = -1; //Infinito
pi[i] = -1;
}
cor[v->value] = 1;
d[v->value] = 0;
pi[v->value] = -1;
Queue(f,v->value);
while(f->size > 0){
Item *aux = Dequeue(f);
for(int i = 0; i < G->V; i++){
if(G->adj[aux->data][i]->value == 1)
if(cor[i] == 0){
cor[i] = 1;
d[i] = d[aux->data]+1;
pi[i] = aux->data;
Queue(f,i);
}
}
cor[aux->data] = -1;
printf("\n\t\tVertice:%d", aux->data);
}
}A alteração realizada nesse método também se deu no laço while, para acessar os vértices adjacentes agora é preciso de dois laços for. Um para caminhar nas colunas da matriz INC e achar uma aresta que tenha origem no vértice analisado e outro para caminha nas linhas da matriz e encontrar o vértice de destino.
void BFS(graph G, vertex v){
int cor[G->V]; // -1 = Preto, 0 = Branco, 1 = Cinza
int d[G->V];
int pi[G->V];
Fila *f =FFVazia();
printf("\n\n\tMetodo de busca BFS: \n");
for(int i = 0; i < G->V; i++)
if(i != v->value){
cor[i] = 0;
d[i] = -1; //Infinito
pi[i] = -1;
}
cor[v->value] = 1;
d[v->value] = 0;
pi[v->value] = -1;
Queue(f,v->value);
while(f->size > 0){
Item *aux = Dequeue(f);
int aux2;
for(int i = 0; i < G->E; i++){
if(G->inc[aux->data][i]->value == -1)
for(int aux2 = 0; aux2 < G->V; aux2++)
if(G->inc[aux2][i]->value == 1)
if(cor[aux2] == 0){
cor[aux2] = 1;
d[aux2] = d[aux->data]+1;
pi[aux2] = aux->data;
Queue(f,aux2);
}
}
cor[aux->data] = -1;
printf("\n\t\tVertice:%d", aux->data);
}
}A implementação do algoritmo DFS coloca cada vértice do gráfo em uma de tres categorias:
- -1 -> Visitado (preto)
- 0 -> Não visitado (branco)
- 1 -> Em análise (Cinza)
O objetivo do algoritmo é marcar cada vértice como visitado, evitando ciclos. O algoritmo DFS funciona da seguinte maneira:
- Muda para branco a cor de todos os vértices
- A partir de um vértice, muda sua cor para cinza e parte para o primeiro vértice adjacente de cor branca.
- Repetir o passo o 2 até que não haja mais vértices ajcentes de cor branca
- Altera a cor do vértice encontrado no passo 3 para preto, retorna ao pai desse vértice e repete os passos 2 e 3.
- Repetir o passo 4 até que todos os vértices estejam pretos.
Comparado com a função DFS de lista de adjacência a alteração se deu na função: DFS_VISIT(). Para percorrer os vértices adjacentes precisa agora caminhar pelaS colunas da matriz adj.
void DFS(graph G){
printf("\n\n\tMetodo de busca DFS: \n");
int cor[G->V]; //-1 = Preto; 0 = Branco; 1 = Cinza
int d[G->V]; //Tempo de deslocação
int f[G->V]; //Tempo de Finalização
int tempo = 0;
for(int i = 0; i < G->V; i++) cor[i] = 0; //Branco para todos os vértices
for(int i = 0; i < G->V; i++)
if(cor[i] == 0)
DFS_VISIT(G,i,cor,d,f,&tempo);
}
void DFS_VISIT(graph G, int indice, int *cor, int *d, int *f, int *tempo){
cor[indice] = 1;
*tempo +=1;
d[indice] = *tempo;
for(int aux = 0; aux < G->V; aux++)
if(G->adj[indice][aux]->value == 1)
if(cor[aux] == 0)
DFS_VISIT(G, aux, cor, d, f, tempo);
cor[indice] = -1;
*tempo += 1;
f[indice] = *tempo;
printf("\n\t\tVertice:%d D:%d, F:%d ", indice, d[indice], f[indice]);
}As alterações aqui também se resumem a função: DFS_VISIT(), para percorrer os vértices adjacentes foram inclusos dois laços for. Um para caminhar nas colunas da matriz INC e achar uma aresta que tenha origem no vértice analisado e outro para caminha nas linhas da matriz e encontrar o vértice de destino.
void DFS(graph G){
printf("\n\n\tMetodo de busca DFS: \n");
int cor[G->V]; //-1 = Preto; 0 = Branco; 1 = Cinza
int d[G->V]; //Tempo de deslocação
int f[G->V]; //Tempo de Finalização
int tempo = 0;
for(int i = 0; i < G->V; i++) cor[i] = 0; //Branco para todos os vértices
for(int i = 0; i < G->V; i++)
if(cor[i] == 0)
DFS_VISIT(G,i,cor,d,f,&tempo);
}
void DFS_VISIT(graph G, int indice, int *cor, int *d, int *f, int *tempo){
cor[indice] = 1;
*tempo +=1;
d[indice] = *tempo;
for(int aux = 0; aux < G->E; aux++)
if(G->inc[indice][aux]->value == -1)
for(int aux2 = 0; aux2 < G->V; aux2++)
if(G->inc[aux2][aux]->value == 1)
if(cor[aux2] == 0)
DFS_VISIT(G, aux2, cor, d, f, tempo);
cor[indice] = -1;
*tempo += 1;
f[indice] = *tempo;
printf("\n\t\tVertice:%d D:%d, F:%d ", indice, d[indice], f[indice]);
}Como o grafo inserido nos dois casos é o mesmo os resultados obtidos também serão iguais:
A atividade contempla uma comparação entre os métodos de busca e as estruturas apresentadas. Para isso fora realizado testes com grafos esparsos com cerca de 100 vértices e grafos densos com cerca de 10000 vértices. As comparações serão baseadas em tempo para execução e consumo de memória RAM de cada estrutura. A codificação para gerar as entradas aleatórias de grafos para as funções se encontram no main de cada uma. Para realizar medições de tempo foi usada as funções da biblioteca: < time.h > e para medir o consumo de memória RAM utilizou-se o seguinte comando no terminal:
valgrind --leak-check=yes ./testeOs Resultados obtidos foram:
- O tempo de execução foi: 3.563000 milissegundos
- O espaço em memória gasto foi: 4.432 bytes
- O tempo de execução foi: 75.513000 milissegundos
- O espaço em memória gasto foi: 480,024 bytes
- O tempo de execução foi: 1.987000 milissegundos
- O espaço em memória gasto foi: 196,424 bytes
- O tempo de execução foi: 1918.756000 milissegundos
- O espaço em memória gasto foi: 784,069,000 bytes
- O tempo de execução foi: 5.368000 milissegundos
- O espaço em memória gasto foi: 530,536 bytes
- O tempo de execução foi: 7932.338000 milissegundos
- O espaço em memória gasto foi: 1,120,057,672 bytes
| Lista de Adjacência | Matriz de Adjacência | Matriz de Incidência | |
|---|---|---|---|
| Tempo gasto | 75.513000 milissegundos | 1918.756000 milissegundos | 7932.338000 milissegundos |
| Espaço utilizado | 480,024 bytes | 784,069,000 bytes | 1,120,057,672 bytes |
- Tempo
- Memória
| Lista de Adjacência | Matriz de Adjacência | Matriz de Incidência | |
|---|---|---|---|
| Tempo gasto | 3.563000 milissegundos | 1.987000 milissegundos | 5.368000 milissegundos |
| Espaço utilizado | 4.432 bytes | 196,424 bytes | 530,536 bytes |
- Tempo
- Memória
Analisando os resultados obtidos percebe-se que para grandes entradas de dados é muito viável utilizar Listas de adjacência e vasicamente inviável a utilização de matrizes de incidência. Já para pequenas entradas de dados é mais vantajoso matriz de adjacência, pelo se baixo consumo de memória, a diferênça de tempo é basicamente imperceptível.
A única estrutura que não se mostrou muito vantajosa em nunhum caso foi a matriz de incidência, em todos os casos ela apresenta piores resultados
[1] Wikipedia[2] Ime.Usp
[3] BFS