一、基本结构

1. 顶点数组：数组的下标对应图的顶点编号（或用哈希表映射顶点标识），数组的每个元素指向该顶点的 “邻居列表”；

2. 邻居列表：每个顶点对应的列表，存储与该顶点直接相连的顶点（带权图还需存储边的权重）。

二、临接表示例

1.无向图的邻接表

如果上面的图用临接矩阵表示，那么便是一个4*4的矩阵

如果是临接表，那么可以看出一共有4个顶点0、1、2、3

每个顶点都有“邻居”（邻居数组）。

比如顶点0，它的邻居数组是[1,2]

顶点1,它的邻居数组是[0,2]

顶点2,它的邻居数组是[0,1,3]

顶点3,它的邻居数组是[2]

表示成下面这样：

0 → [1, 2]  1 → [0, 2]   2 → [0, 1, 3]  3 → [2]

参考代码：

#include <iostream>  #include <vector>  using namespace std;  // 创建无向图的邻接表  vector<vector<int> > createUndirectedGraph(int numVertices) {      return vector<vector<int> >(numVertices);  }  // 添加无向边  void addUndirectedEdge(vector<vector<int> >& graph, int u, int v) {      graph[u].push_back(v);      graph[v].push_back(u);  }  // 打印邻接表   void printGraph(const vector<vector<int> >& graph) {      cout << "无向图邻接表:" << endl;      for (int i = 0; i < graph.size(); i++) {          cout << "顶点 " << i << " -> ";          // 循环遍历邻居          for (int j = 0; j < graph[i].size(); j++) {              cout << graph[i][j] << " ";          }          cout << endl;      }  }    // 计算每个顶点的度  vector<int> calculateDegrees(const vector<vector<int> >& graph) {      vector<int> degrees(graph.size(), 0);      for (int i = 0; i < graph.size(); i++) {          degrees[i] = graph[i].size();      }      return degrees;  }    // 检查两个顶点之间是否有边 - 使用传统for循环  bool hasEdge(const vector<vector<int> >& graph, int u, int v) {      for (int j = 0; j < graph[u].size(); j++) {          if (graph[u][j] == v) {              return true;          }      }      return false;  }  // 删除无向边   void removeUndirectedEdge(vector<vector<int> >& graph, int u, int v) {      // 删除 u->v 的边      for (int j = 0; j < graph[u].size(); j++) {          if (graph[u][j] == v) {              graph[u].erase(graph[u].begin() + j);              break;          }      }            // 删除 v->u 的边      for (int j = 0; j < graph[v].size(); j++) {          if (graph[v][j] == u) {              graph[v].erase(graph[v].begin() + j);              break;          }      }  }  int main() {      // 创建无向图      vector<vector<int> > graph = createUndirectedGraph(6);      // 添加边      addUndirectedEdge(graph, 0, 1);      addUndirectedEdge(graph, 0, 2);      addUndirectedEdge(graph, 1, 3);      addUndirectedEdge(graph, 1, 4);      addUndirectedEdge(graph, 2, 4);      addUndirectedEdge(graph, 3, 5);      // 打印图      printGraph(graph);      cout << endl;      // 计算顶点度      vector<int> degrees = calculateDegrees(graph);      for (int i = 0; i < degrees.size(); i++) {          cout << "顶点 " << i << " 的度: " << degrees[i] << endl;      }      cout << endl;      // 检查边      cout << "检查边 0-1: " << (hasEdge(graph, 0, 1) ? "存在" : "不存在") << endl;      cout << "检查边 0-3: " << (hasEdge(graph, 0, 3) ? "存在" : "不存在") << endl;      cout << endl;      // 删除边      cout << "删除边 0-1 后:" << endl;      removeUndirectedEdge(graph, 0, 1);      printGraph(graph);      return 0;  }

2.有向图的临接表

对于上面这个有向图，如果用临接矩阵表示，是一个4*4的临接矩阵，如下所示

如果是临接表，那么有4个顶点0，1，2，3

对于顶点0来说，它的邻居数组是[1,2]

对于顶点1来说，它的邻居数组是[2]

对于顶点2来说，它的邻居数组是[3]

对于顶点3来说，它的邻居数组是[]

表示成下面

顶点0: [1, 2]  // 0指向1、2  顶点1: [2]     // 1指向2  顶点2: [3]     // 2指向3  顶点3: []      // 3无出边

3.带权图的邻接表

邻接表需存储 “邻居顶点 + 权重”（通常用二元组 / 结构体）：

对于这个带权图，如果是临接矩阵，那么是4*4的临接矩阵，表示成下面这样

如果是临接表进行表示，

顶点0: [(1,5), (2,3)]  顶点1: []  顶点2: [(3,7)]  顶点3: []