CODEWITHSUNDEEP
javagraph
Hoser
Hoser

Reputation: 5044

What are some ways I can represent a weighted, directed graph in Java?

I can't use any external libraries, so I'm trying to think of some ways to build the data structure myself. I was thinking maybe something like this:

public class Node{
    Set<Edge> adjacent;
    int value;
}

public class Edge{
    Node target;
    int weight;
}

But I'm guessing there's probably a better way to do it.

My eventual use for this graph is to run the Bellman Ford algorithm on it, but I obviously need a functioning graph first!

Upvotes: 10

Views: 15337

Answers (3)

Sumit
Sumit

Reputation: 31

You can use a node as in an unweighted graph, holding a list of nodes to which it is connected,and additionally add the weights associated with the connections as:

public class Node{
    int value;
    HashMap<Node,Integer> adjacency;
}

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726479

The answer depends a lot on the algorithms that you are planning to apply to your graphs.

There are two common ways to represent a graph - an adjacency list and an adjacency matrix. In your case, and adjacency matrix is a square array of integers representing weights. Your representation uses an adjacency list.

There are algorithms that work better on adjacency matrixes (e.g. Floyd-Warshall algorithm). Other algorithms work better on adjacency lists (e.g. Dijkstra's algorithm). If your graph is sparse, using adjacency matrix may be prohibitive.

Upvotes: 15

leo
leo

Reputation: 1117

As usual, you can represent graphs as Adjacency Lists or Adjacency Matrices. The choice really depends on the details of your problem.

Using an Adjacency Matrix, you could simply have a matrix of integers, representing the weight.

If you decide to have an Adjacency List, you could simply store a list of list of integers (assuming the nodes of your graph are identified by an integer value), similar to what you've done.

Upvotes: 4

Related Questions