• Usado o "C/C++ Makefile Project" extensão do VsCode

• Programa criado no Windowns 10, VisualCode

  Mudar no arquivo Makefile SRCDIR = "endereço da pasta"

Modo de execução:

• Abrir pasta do arquivo ./graph
• make
• graph.exe

Partindo do código estudado em sala e disponibilizado no qual utilizamos uma fila de adjacência foram reaizadas modificações tanto nas estruturas do grafo quanto nas estruturas BFS e DFS para comportar as matrizes de adjacência e de incidência

#1 -> A primeira mudança se refere a struct do grafo, no qual irá comportar uma matriz estática e um vetor estático que servirá de auxliar nas estruturas BSF e DFS.

#2 -> Nossa iniciação irá atribuir para todos os indices do vetor visitados o valor de 0 e para todas posições da matriz.

#3 -> Nossa inserção foi modificada para atribuir o valor de 1 para a posição da matriz em que os vértices fazem arestas.

• BFS com lista de adjacência:

Para o nosso BFS comportar a matriz de adjacência tivemos uma mudança no dentro do while #4 (linha 10 do exemplo acima).

 while(isEmpty(&f) == 0){ // Enquanto tiver elemento na lista
  
    FImprime(&f);
    vis = Desenfileira(&f); //Desinfilera a cabeça
    printf("Visitado vetor [%d] | Desenfilera da Fila\n",vis); 
    printf("\n V   E");
    
    // Percorro toda minha linha do vetor q estou visitando procurando aresta (1)
    for(int i=0;i<MAX; i++){ 

      printf("\n %d   %d",i,G->Matriz[vis][i]);
      
      /* Se eu encontrar uma aresta [Valor 1 na matriz], sendo q no vértice encontrado essa aresta 
       nao foi visitado, entro no if */
       
      if(G->visitados[i] ==  0 && (G->Matriz[vis][i] == 1)){ 
        G->visitados[i] = 1;   // Atribuo cor cinza 
        Enfileira(&f,i);// Adiciono o vertice encontrado na fila
        printf(" Entrou, Enfilera [%d] na fila | recebe [Cor Cinza = 1]",i);
      }

    }
     G->visitados[vis] = 2; // terminei de analisar o vértice por completo, recebe cor preta
     printf("\n\nVertice [%d] | recebe [Cor Preta = 2]  \n", vis);
  }

• Exemplo apresentado no código:

A matriz já setada na opção de [Matriz de Adjacência BFS] do código tem a seguinte representação:

Ao iniciar nosso código nessa opção teremos de inicio a representação da matriz adjacente e em seguida todo o acompanhamento realizado pelo BFS, incluindo os vertices que estão sendo analisados, quais dos vértices foram adicionados na fila e toda a mudança de cores desses vértices.

Comentando a analise primária, sendo que começamos a partir do vértice 0:

• No começo, iremos ter na fila apenas o vértice 0, que sera desenfileirado e analisado toda sua linha procurando uma aresta [valor 1]
• Na coluna 1 e 2 iremos encontrar arestas, portanto 1 e 2 é adicionado na fila e recebem cor cinza
• Após a análise por completo 0 recebe a cor preta

• DFS com lista de adjacência:

Para adptar a DFS para comportar a matriz adjacente mudamos o for dentro da função DFS-Visit#5 (Linha 4 do exemplo) para identificar o vértice no qual teremos aresta.

void DFS_VISIT(Graph G,int v, int *cor, int *d, int *f, int *tempo){
  cor[v]  = 1; //Recebe cor Cinza
  *tempo  += 1;
  d[v]    = *tempo;

/* vou percorrer na linha da minha matriz do vértice analisado*/
 for(int u = 0; u < MAX; u++) 
 
   /*Caso encontre uma aresta com algum outro vértice [Valor 1 na matriz] e 
   esse vértice não foi visitado  */
   if(G->Matriz[v][u] == 1 &&  cor[u] == 0) 
      DFS_VISIT(G, u, cor, d, f, tempo);

  cor[v] = 2; //Após analisar todo meu vértice, recebe cor Preta
  *tempo += 1;
  f[v] = *tempo;
  printf("Vertex:%d D:%d, F:%d \n", v, d[v], f[v]);
}

Exemplo da saída da opção [Matriz de Adjacência DFS], sendo que o grafo utilizado é o mesmo utilizado quando chamamos a estrutura BFS

#6 -> Mudanças no struct para poder criar uma matriz não quadrática

#7 -> Criado uma variável para controlar o número de arestas criadas

#8 -> Na função de criar as arestas, a coluna da matriz (aresta) será fixa na variável de controle da aresta, e sempre que criamos uma adicionamos +1 nessa variável.

Igualmente quando mudamos o conteudo do while dentro do BSF para a matriz de adjancencia mudaremos ela para a matriz de incidencia. Ao contrário da Matriz de Adjacencia em que mudamos o for para que a partir do vértice visitado ele caminhasse na linha para encontrar uma aresta [Valor 1], na matriz de incidencia a partir do vértice pesquisado iremos caminhar sua linha ate encontrar uma aresta [Valor 1] e assim que encontrarmos iremos caminhar a coluna para encontrar a outra ponta desse vértice [ver em #9].

while(isEmpty(&f) == 0){ // Enquanto tiver elemento na lista
 
   FImprime(&f);
   vis = Desenfileira(&f); //Desinfilera a cabeça
   printf("Visitado vetor [%d] | Desenfilera da Fila\n",vis); 
   
   for(int i=0; i<Edge;i++){  // Vou percorrer as linhas procurando um valor 1
       
       if(G->Matriz[vis][i] == 1){ // caso encontrado, entro no if
           
           
           /*Percorro a coluna para procurar a outra ponta da aresta*/
          
          for(int j=0; j<MAXInc;j++){
               /*Caso encontrar o valor 1 durande a busca pela coluna e 
                o vértice encontrado nao foi visitado entro no if
               */
               if(G->Matriz[j][i]==1 && G->visitados[j]==0 ){
                    G->visitados[j] = 1; // Atribuo cor Cinza
                   Enfileira(&f,j);// Adiciono o vertice na fila
                   printf(" Entrou, Enfilera [%d] na fila | Aresta: %d| recebe [Cor Cinza = 1]\n",j,i);
                   break;
               }
           }
       }
    G->visitados[vis] = 2; // Atribuo cor Preta apos analisar completamente o vértice
    printf("\n\nVertice [%d] | recebe [Cor Preta = 2]  \n", vis);
 }

• Exemplo apresentado no código:

A matriz já setada na opção de [Matriz de Incidência BFS] do código tem a seguinte representação:

No grafo, as arestas também estão sendo identificadas (e0,e1,e2,...,e8)

Após escolhermos essa opção, assim como o BFS da Adjacente, iremos acompanhar todo o processo realizada como saída do programa, desde o gráfico da matriz de incidência exibido como os vértices visitados, quais vértices foram adicionados a fila e todo o processo de mudança de cores.

Comentando a analise primária, sendo que começamos a partir do vértice 0:

• No começo, iremos ter na fila apenas o vértice 0, que sera desenfileirado e analisado toda sua linha procurando uma aresta [valor 1]
• Assim que achar uma aresta na sua linha ele irá procurar pela coluna a procura do outro par dessa aresta encontrada
• O vértice 0 acha pares na aresta 0 e 1, em que será com os vértices 4 e 3, que será adicionado na fila e atribuído cor cinza
• Após verificar totalmente o vértice 0, o mesmo recebe cor preta
• A cabeça da fila é desenfileirada e inicia uma analise a partir desse vértice, no caso, o 4 é desenfileirado e analisado
• 4 tem arestas (0,3,8) com os vértices 0,1,5. Como o vértice 0 é preto, apenas os vértices 1,5 são adicionados
• o vértice 3 é desenfileirado da fila e analisado. Ele tem arestas (1,5,7) com os vértices (1,2,5). O vértice 0 é preto e 5 é cinza, portanto apenas o vértice 2 é adicionado a fila
• Vértice 3 após ser todo investigado é atribuido a ele a cor preta

Para adptar a DFS para comportar a matriz de incidencia mudamos o for dentro da função DFS-Visit(Linha 4 do exemplo) para identificar o vértice no qual teremos aresta.

void DFS_VISITInc(GraphInc G,int v, int *cor, int *d, int *f, int *tempo){
  cor[v]  = 1;
  *tempo  += 1;
  d[v]    = *tempo;

    for(int u = 0; u < Edge; u++){ // vou percorrer na linha da minha matriz
        if(G->Matriz[v][u] == 1 &&  cor[u] == 0){
            for(int j=0;j<MAXInc;j++){ // vou percorrer na linha da minha matriz     
                if(G->Matriz[j][u] == 1 && cor[j] == 0){ //localizo vertices q contem arestas ligadas e não foi visitado
                    DFS_VISITInc(G, j, cor, d, f, tempo);
                }
            }
        }
    }

  cor[v] = 2;
  *tempo += 1;
  f[v] = *tempo;
  printf("Vertex:%d D:%d, F:%d \n", v, d[v], f[v]);
}

Exemplo da saída da opção [Matriz de Incidência DFS], sendo que o grafo utilizado é o mesmo utilizado quando chamamos a estrutura BFS