学习笔记之图的表示

发表于 更新于 分类于

学习笔记之图的表示

图的表示

1. Adjacency Matrix

邻接矩阵

package adjacency_matrix;

public class Graph {

  private int numOfNodes;
  private boolean directed;
  private boolean weighted;
  private float[][] matrix;

  private boolean[][] isSetMatrix;

  public Graph(int numOdNodes, boolean directed, boolean weighed) {
    this.directed = directed;
    this.numOfNodes = numOdNodes;
    this.weighted = weighed;

    matrix = new float[numOfNodes][numOfNodes];
    isSetMatrix = new boolean[numOfNodes][numOfNodes];
  }

  public void addEdge(int source, int destination) {
    int valueToAdd = 1;
    if (weighted) {
      valueToAdd = 0;
    }

    matrix[source][destination] = valueToAdd;
    isSetMatrix[source][destination] = true;

    /*
        * Since matrices for directed graphs are symmetrical, we have to add
        * [destination][source] at the same time as [source][destination]
        */
    if (!directed) {
      matrix[destination][source] = valueToAdd;
      isSetMatrix[destination][source] = true;
    }

  }

  public void addEdge(int source, int destination, float weight) {
    float valueToAdd = weight;
    if (!weighted) {
      valueToAdd = 1;
    }

    matrix[source][destination] = valueToAdd;
    isSetMatrix[source][destination] = true;

    /*
         * Since matrices for directed graphs are symmetrical, we have to add
         * [destination][source] at the same time as [source][destination]
         */
    if (!directed) {
      matrix[destination][source] = valueToAdd;
      isSetMatrix[destination][source] = true;
    }

  }

  public void printMatrix() {
    for (int i = 0; i < numOfNodes; i++) {
      for (int j = 0; j < numOfNodes; j++) {
        if (isSetMatrix[i][j]) {
          System.out.format("%8s", String.valueOf(matrix[i][j]));
        } else {
          System.out.format("%8s", "/  ");
        }
      }
      System.out.println();
    }
  }

  public void printEdges() {
    for (int i = 0; i < numOfNodes; i++) {
      System.out.print("Node " + i + " is connected to: ");
      for (int j = 0; j < numOfNodes; j++) {
        if (isSetMatrix[i][j]) {
          System.out.print(j + " ");
        }
      }
      System.out.println();
    }
  }

  public boolean hasEdge(int source, int destination) {
    return isSetMatrix[source][destination];
  }

  public Float getEdgeValue(int source, int destination) {
    if (!weighted || !isSetMatrix[source][destination]) {
      return null;
    }
    return matrix[source][destination];
  }

  public static void main(String[] args) {
    Graph graph = new Graph(5, false, true);
    graph.addEdge(0, 2, 19);
    graph.addEdge(0, 3, -2);
    graph.addEdge(1, 2, 3);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);

    graph.printMatrix();

    System.out.println();
    System.out.println();

    graph.printEdges();

    System.out.println();
    System.out.println("Does an edge from 1 to 0 exist?");
    if (graph.hasEdge(0,1)) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}


Screen Shot 2020-08-24 at 5.42.42 PM Screen Shot 2020-08-24 at 5.43.23 PM

2. Adjacency List

使用HashMap and LinkedList.

package adjacency_list;

import java.util.Objects;

public class Node {

  int n;
  String name;

  public Node(int n, String name) {
    this.n = n;
    this.name = name;
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Node node = (Node) o;
    return n == node.n &&
      name.equals(node.name);
  }

  @Override
  public int hashCode() {
    return Objects.hash(n, name);
  }
}

package adjacency_list;

import java.util.HashMap;
import java.util.LinkedList;

public class Graph {

  private HashMap<Node, LinkedList<Node>> adjacencyMap;
  private boolean directed;

  public Graph(boolean directed) {
    this.directed = directed;
    this.adjacencyMap = new HashMap<>();
  }

  public void addEdgeHelper(Node a, Node b) {
    LinkedList<Node> tmp = adjacencyMap.get(a);
    if (tmp != null) {
      tmp.remove(b);
    } else {
      tmp = new LinkedList<>();
    }
    tmp.add(b);
    adjacencyMap.put(a, tmp);
  }

  public void addEdge(Node source, Node destination) {
    if (!adjacencyMap.keySet().contains(source)) {
      adjacencyMap.put(source, null);
    }
    if (!adjacencyMap.keySet().contains(destination)) {
      adjacencyMap.put(destination, null);
    }

    addEdgeHelper(source, destination);

    if (!directed) {
      addEdgeHelper(destination, source);
    }
  }

  public void printEdges() {
    for (Node node : adjacencyMap.keySet()) {
      System.out.print("The " + node.name + " has an edge towards: ");
      if (adjacencyMap.get(node) != null) {
        for (Node neighbor : adjacencyMap.get(node)) {
          System.out.print(neighbor.name + " ");
        }
        System.out.println();
      } else {
        System.out.println("none");
      }
    }
  }

  public boolean hasEdge(Node source, Node destination) {
    return adjacencyMap.containsKey(source) && adjacencyMap.get(source) != null && adjacencyMap.get(source).contains(destination);
  }

  public static void main(String[] args) {

    Graph graph = new Graph(true);
    Node a = new Node(0, "A");
    Node b = new Node(1, "B");
    Node c = new Node(2, "C");
    Node d = new Node(3, "D");
    Node e = new Node(4, "E");

    graph.addEdge(a,b);
    graph.addEdge(b,c);
    graph.addEdge(b,d);
    graph.addEdge(c,e);
    graph.addEdge(b,a);

    graph.printEdges();

    System.out.println(graph.hasEdge(a,b));
    System.out.println(graph.hasEdge(d,a));
  }
}

3. which should I choose?

Adjacency matrices have a much faster look-up time than adjacency lists. For example, if we wanted to check whether node 0 has an edge leading to node 4 we could just check the matrix at indices [0,4] which gives us constant execution time.

Adding edges is also much faster in adjacency matrices - simply change the value at position [i,j] to add an edge from node i to node j, while with lists (if we don't have access to the pointer to the last element) can also take O(n) time, especially if we need to check whether that edge already exists in the list or not.

As far as space is concerned - djacency lists are much more efficient

  • Checking whether an edge is part of a graph: adjacency matrix, since checking whether an edge is part of a graph takes O(1) time, while in adjacency lists it takes O(lengthOfList) time
  • Adding or removing edges from the graph: adjacency matrix, same difference as in the previous case
  • Traversing the graph: adjacency list, takes O(N + E) time instead of O(N^2)

参考

https://stackabuse.com/graphs-in-java-representing-graphs-in-code/

https://www.baeldung.com/java-graphs