定义和操作

图的定义

图是由顶点和边组成的非线性数据结构。顶点有时也被称为节点，而边是连接图中任意两个节点的线或弧。更正式地说，图是由一组顶点(V)和一组边(E)组成的。图用G(E, V)表示。

• 有向图（directed graph）：边是有方向的，从一个定点指向另一个定点
• 无向图（undirected graph）：边是没有方向的

• 连通图（Connected Graph）：图中的每一对不同顶点都可以通过一条或多条边相互连接，也就是说，从图中的任意一个顶点出发，都可以到达图中的任意其他顶点。
• 非连通图（Disconnected Graph）：图中存在两个或多个互不相连的子图，也就是说，其中至少存在一个顶点集合，无法通过边连接到图中的其他顶点集合。
• 完全图（Complete Graph）：完全图是一种特殊的图，其中每一对不同的顶点都直接相连，也就是说，完全图中的任意两个顶点之间都存在一条边。如果一个完全图有n个顶点，那么它将有 $C(n, 2) = n(n-1)/2$ 条边，其中 $C(n, 2)$ 表示从n个顶点中选择2个顶点的组合数。

• 连通分量（Connected Components）：连通分量（Connected Components），也称为连通子图，是一个无向图中的一个重要概念。一个连通分量是指在无向图中，如果从其中一个顶点出发，可以通过边的路径到达该连通分量内的任何其他顶点，而无法通过图中的边到达其他连通分量内的顶点。
• 顶点的度（Degree）：顶点的度是指与该顶点相邻的边的数量，也就是与该顶点直接相连的其他顶点的个数。对于有向图和无向图都适用。
  • 在无向图中，顶点的度就是与该顶点相邻的边的数量。
  • 在有向图中，顶点的度分为入度和出度，分别表示指向该顶点的边的数量和从该顶点出发的边的数量的总和。
• 入度（In-Degree）：入度是指在有向图中指向某个顶点的边的数量，也就是与该顶点关联的边中以该顶点为终点的边的数量。
• 出度（Out-Degree）：出度是指在有向图中从某个顶点出发的边的数量，也就是与该顶点关联的边中以该顶点为起点的边的数量。

邻接矩阵

定义

图的邻接矩阵（Adjacency Matrix）是一种常用的图表示方法，特别适用于稠密图，它以矩阵的形式表示图的连接关系。

在邻接矩阵中，行和列分别代表图的顶点，矩阵的元素表示顶点之间是否相邻或者边的权重。

1. 对于无向图：
   • 如果顶点 $i$ 和顶点 $j$ 之间存在边，则邻接矩阵中 $(i, j)$ 和 $(j, i)$ 位置的元素都被标记为 $1$ （或者表示边的权重）。
   • 如果顶点 $i$ 和顶点 $j$ 之间不存在边，则邻接矩阵中 $(i, j)$ 和 $(j, i)$ 位置的元素都被标记为 $0$ 。
2. 对于有向图：
   • 如果有一条从顶点 $i$ 到顶点 $j$ 的有向边，则邻接矩阵中 $(i, j)$ 位置的元素被标记为 $1$ （或者表示边的权重）。
   • 如果没有从顶点 $i$ 到顶点 $j$ 的有向边，则邻接矩阵中 $(i, j)$ 位置的元素被标记为 $0$ 。

实现

我们可以用一个二维数组来表示邻接矩阵，邻接矩阵的行数和列数与图中的顶点数量相同。

• 邻接矩阵定义
• 添加边

#define MAX_VERTICES 100

int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵

// 初始化邻接矩阵
void initializeMatrix(int vertices) {
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            adjMatrix[i][j] = 0; // 初始化所有元素为0
        }
    }
}

// 在邻接矩阵中添加一条边
void addEdge(int start, int end) {
    adjMatrix[start][end] = 1; // 添加边，将对应位置的元素设为1
    adjMatrix[end][start] = 1; // 无向图需要将对称位置的元素也设为1
}

入度出度

如果需要计算邻接矩阵中某个顶点的 出度 的话，假设顶点编号为 i，我们统计邻接矩阵中的 第 i 行 有多少元素不为 0 即可（该顶点指向哪些顶点）。

如果需要计算邻接矩阵中某个顶点的 出度 的话，假设顶点编号为 i，我们统计邻接矩阵中的 第 i 列 有多少元素不为 0 即可（哪些顶点指向该顶点）。

邻接表

定义

图的邻接表（Adjacency List）是一种常见的图表示方法，特别适用于稀疏图，它使用链表或数组的形式来表示图的连接关系。每个顶点都对应一个链表，链表中存储与该顶点相邻的其他顶点。

邻接表的主要思想是为每个顶点创建一个链表，链表中的每个节点表示与该顶点相邻的另一个顶点。对于无向图，通常需要为每一条边创建两个链表节点，分别表示两个相邻的顶点。

实现

// 邻接表节点结构
struct Node {
    int data;
    struct Node* next;
};

// 图的结构
struct Graph {
    int vertices;
    struct Node** adjacencyList;
};

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 创建图
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->vertices = vertices;
    graph->adjacencyList = (struct Node**)malloc(vertices * sizeof(struct Node*));
    for (int i = 0; i < vertices; i++) {
        graph->adjacencyList[i] = NULL;
    }
    return graph;
}

// 添加边
void addEdge(struct Graph* graph, int start, int end) {
    // 添加边到起始顶点的链表
    struct Node* newNode = createNode(end);
    newNode->next = graph->adjacencyList[start];
    graph->adjacencyList[start] = newNode;

    // 对于无向图，需要添加一条反向边
    newNode = createNode(start);
    newNode->next = graph->adjacencyList[end];
    graph->adjacencyList[end] = newNode;
}

邻接多重表

邻接多重表（Adjacency Multi-list）是一种用于表示无向图的数据结构，主要用于避免在邻接表存储方式中重复存储无向边，提高存储效率，同时便于图的操作（如边的删除）。

邻接多重表中顶点种类分为两种：

• 顶点结点（Vertex Node）：
  • 每个顶点有一个头结点，存储该顶点的信息，以及指向其所有关联边的指针。
• 边结点（Edge Node）：
  • 每条边有一个结点，存储该边的两个顶点及其相关信息。
  • 该结点包含两个指针，分别指向该边所连接的两个顶点的邻接边链表的下一条边，使得图的存储更加紧凑。

还是举个实际例子说明，在上述的邻接多重表中，总共需要存储 5 条边，每条边只需要存储一次，所以总共有 5 个边结点，每个边结点中存储的数据如下表所示：

总结一下，相比于邻接表，邻接多重表最大的不同在于如下两点：

• 节省存储空间：对于无向图，每条边只存储一次。
• 方便进行边的操作：例如，删除一条边时，只需要修改相关顶点的链表中的指针，而不需要像邻接表那样在两个顶点的邻接表中都进行操作。