systemguuh/graph-implementation-java

Exercício de programação de Algoritmo e Estrutura de Dados II

EP1_AEDII

Exercício de programação de Algoritmo e Estrutura de Dados II

O trabalho consiste em desenvolver um programa em Java que recebe um grafo orientado e encontra as componentes fortemente conectadas . Na entrada o usuário deverá selecionar o tipo de representação a ser usada para representar os grafos durante a execução dos algoritmos, a qual pode ser uma coleção de listas de adjacências ou uma matriz de adjacências.

Além disso, o programa deverá imprimir:

1. Se o grafo é fortemente conexo
2. O número de componentes fortemente conectados
3. Uma ordenação topológica do grafo de componentes fortemente conectados
4. A representação em texto do grafo de componentes fortemente conectados

Entrada
A entrada conterá a especificação do grafo orientado. A primeira linha do texto conterá a quantidade de vértices do grafo, |V|. Para cada vértice listamos os nós adjacentes de cada vértice em cada linha, separando cada vérticeAdjacente por “;”. E a última linha especifica o tipo de representação dos grafos desejado pelo usuário, que pode ser:
1: coleção de listas de adjacências ou
2: matriz de adjacências.

Saída
A saída conterá as seguintes linhas. A primeira linha conterá “Sim” se o grafo é fortemente conexo e “Não” caso contrário. A segunda linha conterá o número de componentes fortemente conectados. A terceira linha conterá uma ordenação topológica do grafo de componentes fortemente conectados As demais linhas conterão a representação em texto do grafo de componentes fortemente conectados seguindo o mesmo formato da entrada, caso a representação escolhida seja do tipo 1 ou a matriz, caso seja tipo 2.

Exemplo
  Entrada:
   8
   a: b;
   b: c; e; f;
   c: d; g;
   d: c; h;
   e: a; f;
   f: g;
   g: f; h;
   h: h;
   2

  Saída:
   Não
   abe cd fg h
   abe cd fg h
   abe 0 1 1 0
   cd 0 0 1 1
   fg 0 0 0 1
   h 0 0 0 0