Graphs

Consist of:

  • vertices aka nodes ($V$)
  • $n$ = number of vertices
  • edges ($E$) = pair of vertices
  • $m$ - number of edges
  • can be undirected
  • or directed


Directed Acyclic Graph

This is a special kind of graph where

  • there are no cycles
  • and it is directed

These graphs can be sorted topologically


Representation

adjacency matrix

  • [math]n \times n[/math] matrix where
  • [math]A_{i,j} = 1[/math] if $G$ has [math](i, j)[/math] edge
  • or $+1$/$-1$ if directed
  • or weight if weighted
  • space required [math]\Theta(n^2)[/math]

adjacency list

  • array of vertices
  • array of edges for each vertex
  • space required [math]\Theta(n + m)[/math]

Implementation

Adjacency list:

public class Graph {
    private int n;
    private final List<List<Integer>> adj;

    public Graph(int n) {
        this.n = n;
        this.adj = createAdjacentList(n);
    }

    private static List<List<Integer>> createAdjacentList(int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>(n);

        int i = 0;
        while (i < n) {
            res.add(new LinkedList<Integer>());
            i++;
        }

        return res;
    }

    public void addEdge(int v, int u) {
        adj.get(v).add(u);
    }

    public Iterable<Integer> adjacent(int v) {
        return adj.get(v);
    }

    public int getN() {
        return n;
    }
}


See also

Sources