什么是邻接表

邻接表将图表示为链表数组。数组的索引代表一个顶点，其链表中的每个元素代表与该顶点形成边的其他顶点。例如，我们有下面的图表。

无向图

我们可以在计算机上以链表的形式表示这个图，如下所示。
这里，0、1、2、3是顶点，它们中的每一个都与它的所有相邻顶点形成一个链表。例如，顶点 1 有两个相邻的顶点 0 和 2。因此，在上图中，1 与 0 和 2 相连。

图的链表表示图

邻接表的优点

• 邻接表在存储方面是高效的，因为我们只需要存储边的值。对于具有数百万个顶点和边的稀疏图，这意味着可以节省大量空间。
• 它还有助于轻松找到与顶点相邻的所有顶点。

邻接表的缺点

• 查找相邻列表并不比邻接矩阵快，因为必须首先探索所有连接的节点才能找到它们。

  邻接表的结构

最简单的邻接表需要一个节点数据结构来存储一个顶点和一个图数据结构来组织节点。我们接近图的基本定义——顶点和边的集合{V, E}。为简单起见，我们使用未标记的图形而不是标记的图形，即顶点由它们的索引 0、1、2、3 标识。让我们深入研究这里起作用的数据结构。

class Graph{
    private int numVertices;
    private LinkedList<integer> adjLists[];
}

邻接表的实现

// Adjascency List representation in Java
import java.util.*;
class Graph {
  // Add edge
  static void addEdge(ArrayList<ArrayList<Integer>> am, int s, int d) {
    am.get(s).add(d);
    am.get(d).add(s);
  }
  public static void main(String[] args) {
    // Create the graph
    int V = 5;
    ArrayList<ArrayList<Integer>> am = new ArrayList<ArrayList<Integer>>(V);
    for (int i = 0; i < V; i++)
      am.add(new ArrayList<Integer>());
    // Add edges
    addEdge(am, 0, 1);
    addEdge(am, 0, 2);
    addEdge(am, 0, 3);
    addEdge(am, 1, 2);
    printGraph(am);
  }
  // Print the graph
  static void printGraph(ArrayList<ArrayList<Integer>> am) {
    for (int i = 0; i < am.size(); i++) {
      System.out.println("\nVertex " + i + ":");
      for (int j = 0; j < am.get(i).size(); j++) {
        System.out.print(" -> " + am.get(i).get(j));
      }
      System.out.println();
    }
  }
}