Arestas de corte

Um grafo simétrico é conexo se existe um passeio de cada vértice aos demias vértices do grafo. Um grafo simétrico que não é conexo consiste de um conjunto de componentes conexas que são subgrafos conexos maximais.

Uma ponte ou aresta de corte de um garfo simétrico é uma aresta que se removida aumenta o número de componentes conexos.

PROBLEMA. Determinar as arestas de corte de um grafo simétrico dado.

Considere uma floresta de busca em profundidade do grafo dado. Para cada vértice u do grafo tem-se que u->min é o vértice v de menor númeração pré-ordem tal que

existe um arco de retorno de um descendente de u a v, com exceção feita ao arco de u ao seu predecessor na árvore de busca me profundidade.

• u == v->pred; e
• v->min == v.

#define estado     z.I
#define pre_ordem  y.I
#define min        x.V
#define pred       w.V

enum {NAOVISTO, VISITADO, EXAMINADO};

Boolean dfs_pontes (Vertex *r);
  /*
   * determina as arestas de corte do componente do grafo que
   * contém o vértice r
   */


void
pontes (Graph *g)
{
  Vertex *v0 = g->vertices;
  Vertex *vn = g->vertices + g->n;
  Vertex *v;

  for (v = v0; v < vn; v++)
    {
       v->estado = NAOVISTO;
       v->min = v;
    }

  for (v = v0; v < vn; v++)
    {
      if (v->estado == NAOVISTO)
        {
          v->pred = v;
          dfs_pontes(v);
        }
    }
}


void
dfs_pontes (Vertex *r)
{
  static long pre = 0;
  Arc *a;

  r->estado = VISITADO;
  r->estado = ++pre;

  for (a = r->arcs; a; a = a->next)
    {
      Vertex *v = a->tip;

      if (v == r->pred) continue;

      /* rv é um arco para frente (foward-arc) */
      if (v->estado == EXAMINADO) continue;

      /* rv é um arco de retorno */
      if (v->estado == VISITADO && v->pre_ordem > r->min->pre_ordem) continue;

      /* rv é um arco de retorno */
      if (v->estado == VISITADO && v->pre_ordem < r->min->pre_ordem)  r->min = v;
  
      /* rv é um arco da árvore */
      if (v->estado == NAOVISTO)
        {
           v->pred = r;
           dfs_pontes(v);
           if (v->min->pre_ordem < r->min->pre_ordem)  r->min = v->min;
        }
    } 

  r->estado = EXAMINADO;
}