图中的加权边表示 class

Question

我目前正在实施一个图表 class。我应该使用什么数据结构来存储一组边以及检查边是否存在或 return 他的权重？这是我目前的工作。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.NoSuchElementException;

public class Graph 
{   
    private HashMap<Integer,Position> vertices;
    private ArrayList<Edge> edges;

    private class Edge
    {
        private int weight;
        private int vertex1;
        private int vertex2;

        public Edge(int vertex1, int vertex2, int weight)
        {
            this.weight = weight;
            this.vertex1 = vertex1;
            this.vertex2 = vertex2;
        }   
    }

    //adds a vertex to the graph
    public void addVetex(int vertex, int x, int y)
    {
        vertices.put(vertex, new Position(x,y));
    }

    //connects two vertices in the graph
    public void addEdge(int vertex1, int vertex2, int weight)
    {
        if(!vertices.containsKey(vertex1) || !vertices.containsKey(vertex2))
        {   
            throw new NoSuchElementException();
        }

        edges.add(new Edge(vertex1, vertex2, weight));
    }


    //returns a list of the neighbours of a vertex
    public List<Integer> neighbours(int vertex)
    {
        if(!edges.contains(vertex))
        {
            throw new NoSuchElementException();
        }

        List<Integer> neighbours = new ArrayList<Integer>();

        for(Integer curVertex : vertices.keySet())
        {   
            if(edgeExists(vertex, curVertex))
            {
                neighbours.add(curVertex);
            }
        }

        return neighbours;
    }

    public boolean edgeExists(int vertex1, int vertex2)
    {


    }

    public int weight(int vertex1, int vertex2)
    {
        if(!edgeExists(vertex1, vertex2))
        {
            throw new NoSuchElementException();
        }

        return 
    }

    // returns the position of a vertex that exists
    public Position position(int vertex)
    {
        if(!vertices.containsKey(vertex))
        {
            throw new NoSuchElementException();
        }

        return vertices.get(vertex);
    }

    //creates a graph with n vertices where the probability of an edge is p
    public void randomGraph(int n, double p)
    {


    }

    private class Position
    {
        private int x;
        private int y;

        public Position(int x, int y)
        {
            this.x=x;
            this.y=y;
        }
    }
}

Answer 1

我会把它作为一个答案，因为作为评论写起来太长了，但是天啊，停止嵌套类！

注意，你不需要那么多名字，比如Position。 Vertex 由位置定义。这是一个模型，在多个文件中使用多个类...

Vertex.java

public class Vertex
{
    private int x;
    private int y;

   @Override
   public boolean equals(Object o) {
   // self check
   if (this == o)
       return true;
   // null check
   if (o == null)
      return false;
   // type check and cast
   if (getClass() != o.getClass())
      return false;
   Vertex v = (Vertex) o;
   // field comparison
   return x == v.x && y == v.y;

}

Edge.java

public class Edge
{
    private int weight;
    private Vertex v1;
    private Vertex v2;

   @Override
   public boolean equals(Object o) {
   // self check
   if (this == o)
       return true;
   // null check
   if (o == null)
      return false;
   // type check and cast
   if (getClass() != o.getClass())
      return false;
   Edge e = (Edge) o;
   // field comparison
   return v1.equals(e.v1) && v2.equals(e.v2);
}

Graph.java

public class Graph
{
    private HashMap<Integer,Position> vertices;
    private ArrayList<Edge> edges;
}

然后在你的比较检查中做：

Edge test = new Edge(vertex1, vertex2);
foreach edge in edges:
   # compare edge.equals(test)

抱歉我正在学习Python

图中的加权边表示 class

Weighted edges representation in a graph class

java

graph-theory