olá,
desde já o meu muito obrigada por você estar a tentar ajudar…
eu vou postar aqui, se bem que é um bocado grande :???:
Eu tenho isto em 4 classes distintas, uma classe da aresta, a do arco, a do grafo e a última que é a que estou a implementar se chama caminhos.
import java.util.Vector;
public class Graph {
private Vector<Vertex> vertices; // contém os vértices do grafo
// construtor do grafo
public Graph() {
vertices = new Vector<Vertex>();
}
/*
* valida se existem os vértices que são passados quando se controiem os
* arcos
*/
public boolean validate(String id1) {
for (int i = 0; i < vertices.size(); ++i)
if ((vertices.elementAt(i).getId().equalsIgnoreCase(id1))) {
return true;
}
return false;
}
/*
* adiciona um arco ao vertice do grafo com id = id1, um arco que termina no
* vértice com id=id2 e peso w
*/
public boolean addEdge(String id1, String id2, int w) {
if (!validate(id1))
return false;
if (!validate(id2))
return false;
Vertex v1 = this.get(id1);
Vertex v2 = this.get(id2);
if (v1.addEdge(v2, w))
return true;
return false;
}
/*
* retorna o vértice do grafo com id igual ao recebido como parametro ou
* null caso não exista
*/
public Vertex get(String id) {
for (int i = 0; i < vertices.size(); ++i) {
if (vertices.elementAt(i).getId().equals(id)) {
return vertices.get(i);
}
}
return null;
}
/*
* retorna o vértice do gráfico com index igual ao passado por parametro ou
* null caso não exista
*/
public Vertex get(int v) {
for (int i = 0; i < vertices.size(); ++i) {
if (vertices.elementAt(i).getIndex() == v) {
return vertices.get(i);
}
}
return null;
}
// retorna os ids dos vértices
public String idsVertices() {
String id = "";
String aux = "";
for (int i = 0; i < vertices.size(); ++i) {
aux = vertices.elementAt(i).getId();
id += "[" + " " + aux + " ]";
}
return id;
}
// retorna o número de vertices
public int getSize() {
return vertices.size();
}
/*
* remove um arco se ele existir neste grafo. Retorna true ou false
* consoante a remoção se concretize ou não.
*/
public boolean removeEdge(WeightedEdge e) {
Vertex init = e.getInit();
Vertex rem = null;
for (int i = 0; i < vertices.size(); ++i) {
if (vertices.elementAt(i).equals(init)) {
rem = vertices.elementAt(i);
}
}
rem.removeEdge(e);
return false;
}
/*
* método que retorna um objecto String com o seguinte formato:
*
* [(vo1, vd1, w1), (vo2,vd2,w2), . . ., (von,vdn,wn)]
*
* Em que cada triplo (voi,vdi, wi), i Î{1, ...,n} representa um objecto do
* tipo WeightedEdge.
*/
public String toString() {
String aux = "";
String st = "";
for (int i = 0; i < vertices.size(); ++i) {
Vertex v = vertices.elementAt(i);
aux = v.vertexToEdgeToString();
st += aux;
}
return "[" + st + "]";
}
/*
* retorna o vértice do grafo com id igual ao recebido como parametro, caso
* não exista um vertice com este id adiciona ao grafo um novo vértice com
* este id e index igual à posição em que foi adicionado
*/
public Vertex vertex(String id) {
for (int i = 0; i < vertices.size(); ++i) {
if (vertices.elementAt(i).getId().equals(id)) {
return vertices.get(i);
}
}
Vertex ver = new Vertex(id, vertices.size());
vertices.add(ver);
return ver;
}
}
public class WeightedEdge {
private int weight; // peso do arco
private Vertex init, end; // vértice de inicio e fim do arco
// cria um arco com inicio em vo, fim em vd e peso p
public WeightedEdge(Vertex vo, Vertex vd, int p) {
this.init = vo;
this.end = vd;
this.weight = p;
}
// retorna true se o objecto ref arco igual,false caso contrário
// 2 arcos são iguais se ligarem os mesmos vértices
public boolean equals(Object o) {
if (o instanceof WeightedEdge) {
WeightedEdge we = (WeightedEdge) o;
if (((this.init == we.init) && (this.end == we.end))
|| ((this.end == we.init) && (this.init == we.end)))
return true;
}
return false;
}
// retorna o vértice de destino do arco
public Vertex getEnd() {
return (this.end);
}
// retorna o vértice de origem do arco
public Vertex getInit() {
return (this.init);
}
// retorna o peso do arco
public int getWeight() {
return weight;
}
// exibe o arco e os seus parâmetros
public String toString() {
return "(" + this.init + "," + this.end + "," + this.weight + ")";
}
}
import java.util.*;
public class Vertex {
private String id; // id do vértice
private int index;
private LinkedList<WeightedEdge> edges; // contêm a lista de arcos q têm origem neste vértice
public Vertex(String id, int index) {
edges = new LinkedList<WeightedEdge>();
this.id = id; // identificador do vértice
this.index = index; // indice onde o vértice se encontra no grafo
}
//Adiciona um novo arco a edges, com origem neste
// vértice, fim e peso passados como parâmetros
public boolean addEdge(Vertex d, int p) {
WeightedEdge we = new WeightedEdge(this, d, p);
return (edges.add(we)); // como o método add é boolean vai retornar true se for adicionado
}
//retorna true se o objecto referencia um vértice, caso contrário é falso
public boolean equals(Object o) {
if (o instanceof Vertex) {
Vertex v = (Vertex) o;
if (this.id == v.id)
return true;
}
return false;
}
//Percorre a lista de arcos e retorna um iterador para os vértices
public VertexIterator getEdgesIterator() {
VertexIterator vI = new VertexIterator();
return vI;
}
// retorna o id do vértice
public String getId() {
return id;
}
//retorna o index do vértice
public int getIndex() {
return index;
}
//remove um arco da lista de arcos deste mesmo vértice
public boolean removeEdge(WeightedEdge a) {
Iterator it = edges.listIterator();
while (it.hasNext()) {
if (a.equals(it.next())) {
it.remove();
return true;
}
}
return false;
}
//retorna o id do vértice
public String toString() {
return getId();
}
//Inner Class
//Classe VertexIterator, percorre os vértices dos arcos da lista
public class VertexIterator implements Iterator {
Iterator it = edges.listIterator();
//testa se há seguinte
public boolean hasNext() {
return (it.hasNext());
}
//retorna o próximo elemento
public Vertex next() {
WeightedEdge we = (WeightedEdge) it.next();
return we.getEnd();
}
//remove um arco
public void remove() {
it.remove();
}
}
public String vertexToEdgeToString() {
Iterator it = edges.listIterator();
String s = "";
String s1 = "";
while (it.hasNext()) {
WeightedEdge we = (WeightedEdge) it.next();
s1 += we.toString();
}
return s += s1;
}
}
import java.util.*;
public class caminhos {
Graph grafo = null;
Vertex init, end;
String i, e;
public caminhos(Graph grafo) {
this.grafo = grafo;
}
public static void main(String[] args) {
int nEdge;
Graph g = new Graph();
String init;
String end;
int peso;
Scanner sc = new Scanner(System.in);
System.out
.println("Introduza o número de ligações entre dois cruzamentos consecutivos das pistas :");
nEdge = sc.nextInt();
for (int i = 0; i < nEdge; i++) {
System.out.println("Introduza a ligação " + i
+ " entre 2 cruzamentos consecutivos das pistas :");
init = sc.next();
end = sc.next();
peso = sc.nextInt();
g.vertex(init);
g.vertex(end);
g.addEdge(init, end, peso);
}
System.out.println(g.toString());
}
}
É nesta última class que tenho que fazer os métodos para resolver aquele problema.
Desde já fico muito agradecida.