一、基本结构

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]

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: []

三、示例代码

1. 对于无向图

   
   

#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;
}