CODEWITHSUNDEEP
javadata-structuresgraph
knowledge of no knowledge
knowledge of no knowledge

Reputation: 75

Directed graph implementation in Java

I'm taking a class on data structures in java right now and we are to figure out how to implement a digraph class.
Just off the top, I thought that having a Linked List kind class with a value field and an array of link (self referential) fields like the code below:

    public class Digraph<T>
    {
        T vertex;
        Digraph<T>[] edge;

        public Digraph(T val, int maxDegree)
        {
            vertex = val;
            edge = new Digraph<T>[maxDegree];
        }
    }

After I wrote this out, I realized that this isn't a little to no mess method of approaching this prompt. How can I implement a digraph that isn't as messy as my code bit up there? Or is this an okay approach?

Upvotes: 0

Views: 2423

Answers (1)

ZhaoGang
ZhaoGang

Reputation: 4915

I think using your linked-list way to implement a graph is not a good ieda. Unlike linked list and tree, Graph is not a recursion structure in nature.

I will implement it based on the fact that a graph is consisted of a list of Vertexs, and each Vertex is connected to its neighbours by Edges:

class Graph<E> {
    public List<Vertex<E>> vertexs; 
}

class Vertex<E> {
    public E val;
    public List<Edge<E>> connections; 
}

class Edge<E> {
    public Vertex<E> source;
    public Vertex<E> destination;
}

But the simplest way to represent a graph is to use an Adjacency_matrix

Upvotes: 2

Related Questions