在本文中，我们谈论的是邻接列表（Adjacency List）。
图是边和顶点的集合。
这是表示节点网络的便捷方式。

编程时有多种表示图的方法。
邻接表是最受欢迎的表示形式之一。

在邻接列表表示下，图形表示为列表数组。
数组长度等于顶点数。
数组的每个块代表图形的一个顶点。
每个块包含特定顶点连接到的其他顶点的列表。

邻接表背后的想法

让我们看一个例子，以更好地理解它。
让图形如下所示：

这是一个无向图，这意味着边表示双向连接。

我们可以为有向图和无向图使用邻接表。
查看代码中的注释以查看区别。

上图的邻接表如下所示：

左侧显示阵列，右侧显示存储在阵列中的顶点列表。

邻接表的实现

为了实现邻接表，我们使用动态数组。
动态数组易于扩展。
我们的邻接列表将是数组列表的数组列表。
让我们来看一下代码。

要将边添加到邻接列表中，我们具有以下代码：

static void addEdge(ArrayList<ArrayList<Integer> > adj, int u, int v)
  {
      adj.get(u).add(v);
      adj.get(v).add(u);
      //if the graph is directed then only one statement is needed here
  }
</code>

由于我们正在考虑无向图，因此函数中有两个语句。
如果图形已定向，则从u到v的边将添加为：

static void addEdge(ArrayList<ArrayList<Integer> > adj, int u, int v)
  {
      adj.get(u).add(v);
  }
</code>

以下代码显示邻接表：

static void printGraph(ArrayList<ArrayList<Integer>> adj)
  {
      for (int i = 0; i < adj.size(); i++) {
          System.out.println("Adjacency list for vertex " + i);
          for (int j = 0; j < adj.get(i).size(); j++) {
              if (j!=0)
              System.out.print(" -> "+adj.get(i).get(j));
              else
                  System.out.print(adj.get(i).get(j));
          }
          System.out.println();
      }
  }
</code>

Java邻接表实现

package com.theitroad;

import java.util.ArrayList;

class GraphRep {
  //function to add the edge in Adj list
  static void addEdge(ArrayList<ArrayList<Integer> > adj,
                      int u, int v)
  {
      adj.get(u).add(v);
      adj.get(v).add(u);
      //if the graph is directed then only one statement is needed here
  }

  static void printGraph(ArrayList<ArrayList<Integer>> adj)
  {
      for (int i = 0; i < adj.size(); i++) {
          System.out.println("Adjacency list for vertex " + i);
          for (int j = 0; j < adj.get(i).size(); j++) {
              if (j!=0)
              System.out.print(" -> "+adj.get(i).get(j));
              else
                  System.out.print(adj.get(i).get(j));
          }
          System.out.println();
      }
  }
  public static void main(String[] args)
  {
      int V = 5;
      ArrayList<ArrayList<Integer> > graph
              = new ArrayList<>(V);

//creating array lists for storing lists        
for (int i = 0; i < V; i++)
          graph.add(new ArrayList<>());

      addEdge(graph, 0, 1);
      addEdge(graph, 0, 2);
      addEdge(graph, 1, 3);
      addEdge(graph, 1, 2);
      addEdge(graph, 3, 4);

      printGraph(graph);
  }
}
      
</code>

C ++中的邻接表实现

#include<bits/stdc++.h> 
using namespace std; 

//function to add the edge in Adj list
void addEdge(vector<int> adj[], int u, int v) 
{ 
  adj[u].push_back(v); 
  adj[v].push_back(u); 
 //if the graph is directed then only one statement is needed here
} 

void printGraph(vector<int> adj[], int V) 
{ 
  for (int v = 0; v < V; ++v) 
  { 
      cout << "\n Adjacency list for vertex "; 
      for (auto x : adj[v]) 
         cout << "-> " << x; 
      printf("\n"); 
  } 
} 
int main() 
{ 
  int V = 5; 
  vector<int> graph[V]; 
      addEdge(graph, 0, 1);
      addEdge(graph, 0, 2);
      addEdge(graph, 1, 3);
      addEdge(graph, 1, 2);
      addEdge(graph, 3, 4);
  printGraph(graph, V); 
  return 0; 
} 
</code>

输出

上面的代码输出为：

Adjacency list for vertex 0
1 -> 2
Adjacency list for vertex 1
0 -> 3 -> 2
Adjacency list for vertex 2
0 -> 1
Adjacency list for vertex 3
1 -> 4
Adjacency list for vertex 4
3
</code>