views:

251

answers:

1

Hi, I am trying to implement an adjacency matrix in java that will produce an output for a Hamiltonian cycle, which can then be solved with different algorithms such as kruskurals, djikstras and the 2opt approach. i know that i need a 2d array but i dont know where to start. i need to be able to store the matrix and apply it to the graph that i have, which is currently a circle with "n" nodes (dependant on the matrix). all help is welcomed, thanks

A: 

Here's a skeleton you can work from:

public class Graph {
    public final int V;
    private boolean[][] hasEdge;

    public Graph(int V) {
        this.V = V;
        hasEdge = new boolean[V][V];
    }

    public void addEdge(int v1, int v2) {
        hasEdge[v1][v2] = hasEdge[v2][v1] = true;
    }
    public boolean hasEdge(int v1, int v2) {
        return hasEdge[v1][v2];
    }
}

Things you can improve on:

  • Maybe allow multiple edges between nodes?
  • Maybe allow weighted edges?
  • Maybe use Node type instead of int indices for vertices?
  • etc...
polygenelubricants
thank you that is very helpful
alchemey89