Entrada de arquivo - Grafos

[Edgar Cabral]

Olá pessoal, alguém pode me ajudar na elaboração de um código que manipula grafos? 
Seria mais ou menos assim: 

O problema consiste em receber uma entrada .txt no formato: 
p edge [total de vértices] [total de aresta]
e v1 v2 
e v1 v2 
. 
. 
. 
e gerar uma saída parecida, porém removendo os vizinhos dos vértices com grau 1.  "p edge" para dizer que ali começa a primeira linha, "e" significa o início do grafo.
Por exemplo: 

Entrada: 
p edge 5 6 
e 1 2 
e 1 3 
e 2 3 
e 2 4 
e 2 5 
e 3 5 

Visualmente: Entrada.png 


Saída (executando o código 1 vez): 
p Vértices na cobertura: 1 
p Arestas removidas: 4 
p grafo restante: 
p edge 3 2 
e 1 3 
e 3 5 
e 4 // representa neste exemplo um vértice isolado 

Visualmente: Saida.png 

Não estou conseguindo usar uma lista de adjacência que lê a entrada e já armazena o valor do grau de cada vértices para assim ajudar na atualização das remoções dos vértices de grau 1. 

Alguém que entendeu, poderia me ajudar? 

Obrigado.

[psykotico]

você percebe que todo Grafo é formado por Vértice e Aresta ... Sendo que a relação deles é 1->N entre Vértice e Aresta ... e SEMPRE 2 de Aresta pra Vértice, que podemos chamar de Origem e Destino. Além disso, no Grafo apresentado, você não tem indicadores de sentido, o que significa que cada aresta tem os dois sentidos, tanto de A para B quanto de B para A...

 

Com isso o que você precisaria fazer:

 

1) Pegar o Vértice A, verificar se já existe ... se não existir, cria ... se já existe, adiciona Aresta com destino ao Vértice B

2) Pegar o Vértice B, verificar se já existe ... se não existir, cria ... se já existe, adiciona Aresta com destino ao Vértice A

3) Adicionar a Aresta na lista de Aresta que compõe o grafo

4) A partir daqui, com o Grafo montado, poderemos trabalhar a questão de remover os vértices de grau 1 ... nesse caso fica fácil ... percorrendo a lista, basta procurar os Vértices que só aparecem uma única vez como Origem.

5) Com a relação desses Vértices, basta eliminar todas as Arestas que contiverem os vértices, sejam como Origem ou Destino.

6) Pra montar a Saída, você deve pegar o restante da lista e "ignorar o caminho de retorno" que foi o nosso passo 2...