数据结构与算法9

9.图

1.图

• 图 （graph）是一种非线性 数据结构，由顶点 （vertex）和边 （edge）组成。

• 如果将顶点看作节点，将边看作连接各个节点的引用（指针），相较于线性关系（链表）和分治关系（树），网络关系（图）的自由度更高，因而更为复杂。

1.图常见类型与术语

• 根据边是否具有方向 ，可分为无向图 （undirected graph）和有向图 （directed graph）

  • 在无向图 中，边表示两顶点之间的双向 连接关系

  

  • 在有向图 中，边具有方向性 ，即 𝐴 → 𝐵 和 𝐴 ← 𝐵 两个方向的边是相互独立的

• 根据所有顶点是否连通 ，可分为连通图 （connected graph）和非连通图 （disconnected graph）

  • 对于连通图 ，从某个顶点出发，可以到达其余任意顶点。

  

  • 对于非连通图 ，从某个顶点出发，至少有一个顶点无法到达。

  

• 还可以为边添加权重 变量，从而得到有权图 （weighted graph）

• 反之则为无权图

• 图数据结构包含以下常用术语。
  • 邻接 （adjacency）：当两顶点之间存在边相连 时，称这两顶点邻接 。
  • 路径 （path）：从顶点 A 到顶点 B 经过的边构成的序列被称为从 A 到 B 的路径 。
  • 度 （degree）：一个顶点拥有的边数 。对于有向图 ，入度 （in‑degree）表示有多少条边指向该顶点 ，出度 （out‑degree）表示有多少条边从该顶点指出 。

2.图的表示

1.邻接矩阵

• 设图的顶点数量为 𝑛 ，邻接矩阵 （adjacency matrix）使用一个 𝑛 × 𝑛 大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用 1 或 0 表示两个顶点之间是否存在边
• 设邻接矩阵为 𝑀、顶点列表为 𝑉 ，那么矩阵元素 𝑀[𝑖, 𝑗] = 1 表示顶点 𝑉 [𝑖] 到顶点 𝑉 [𝑗]之间存在边，反之 𝑀[𝑖, 𝑗] = 0 表示两顶点之间无边

• 邻接矩阵具有以下特性。

  • 在简单图中，顶点不能与自身相连，此时邻接矩阵主对角线元素没有意义。
  • 对于无向图 ，两个方向的边等价，此时邻接矩阵关于主对角线对称 。
  • 将邻接矩阵的元素从 1 和 0 替换为权重，则可表示有权图。

• 使用邻接矩阵表示图时，可以直接访问矩阵元素以获取边，因此增删查改操作的效率很高 ，时间复杂度均为 𝑂(1) 。然而，矩阵的空间复杂度为 $𝑂(𝑛^2 )$ ，内存占用较多

2.邻接表

• 邻接表 （adjacency list）使用 𝑛 个链表来表示图，链表节点 表示顶点 。第 𝑖 个链表对应顶点 𝑖 ，其中存储了该顶点的所有邻接顶点（与该顶点相连的顶点）

# 邻接表仅存储实际存在的边，而边的总数通常远小于 $𝑛^2$ ，因此它更加节省空间。

# 然而，在邻接表中需要通过遍历链表来查找边，因此其时间效率不如邻接矩阵

• 邻接表结构与哈希表中的链式地址 非常相似，因此也可以采用类似的方法来优化效率。
• 比如当链表较长时，可以将链表转化为 AVL 树或红黑树，从而将时间效率从 𝑂(𝑛) 优化至 𝑂(log 𝑛) ；
• 还可以把链表转换为哈希表，从而将时间复杂度降至 𝑂(1) 。

3.图的常见应用

	顶点	边	图计算问题
社交网络	用户	好友关系	潜在好友推荐
地铁线路	站点	站点间的连通性	最短路线推荐
太阳系	星体	星体间的万有引力作用	行星轨道计算

2.图的基础操作

• 图的基础操作分为对边 的操作和对顶点 的操作
• 在邻接矩阵 和邻接表 两种表示方法下，有不同的实现方式

1.基于邻接矩阵的实现

• 添加或删除边 ：直接在邻接矩阵中修改指定的边即可，使用 𝑂(1) 时间。而由于是无向图，因此需要同时更新两个方向的边。

• 添加顶点 ：在邻接矩阵的尾部添加一行一列，并全部填 0 即可，使用 𝑂(𝑛) 时间。

• 删除顶点 ：在邻接矩阵中删除一行一列。当删除首行首列时达到最差情况，需要将 $(𝑛−1)^2$ 个元素“向左上移动”，从而使用 𝑂($𝑛^2$ )时间。

• 初始化 ：传入 𝑛 个顶点，初始化长度为 𝑛 的顶点列表 vertices ，使用 𝑂(𝑛) 时间；初始化 𝑛 × 𝑛 大小的邻接矩阵 adjMat ，使用 𝑂($𝑛^2$ ) 时间。

• 代码实现

/* 基于邻接矩阵实现的无向图结构体 */
typedef struct {
    int vertices[MAX_SIZE];
    int adjMat[MAX_SIZE][MAX_SIZE];
    int size;
} GraphAdjMat;

/* 构造函数 */
GraphAdjMat *newGraphAdjMat() {
    GraphAdjMat *graph = (GraphAdjMat *)malloc(sizeof(GraphAdjMat));
    graph->size = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        for (int j = 0; j < MAX_SIZE; j++) {
            graph->adjMat[i][j] = 0;
        }
    }
    return graph;
}

/* 析构函数 */
void delGraphAdjMat(GraphAdjMat *graph) {
    free(graph);
}

/* 添加顶点 */
void addVertex(GraphAdjMat *graph, int val) {
    if (graph->size == MAX_SIZE) {
        fprintf(stderr, " 图的顶点数量已达最大值\n");
        return;
    }
    // 添加第 n 个顶点，并将第 n 行和列置零
    int n = graph->size;
    graph->vertices[n] = val;
    for (int i = 0; i <= n; i++) {
        graph->adjMat[n][i] = graph->adjMat[i][n] = 0;
    }
    graph->size++;
}

/* 删除顶点 */
void removeVertex(GraphAdjMat *graph, int index) {
    if (index < 0 || index >= graph->size) {
        fprintf(stderr, " 顶点索引越界\n");
        return;
    }
    // 在顶点列表中移除索引 index 的顶点
    for (int i = index; i < graph->size - 1; i++) {
        graph->vertices[i] = graph->vertices[i + 1];
    }
    // 在邻接矩阵中删除索引 index 的行
    for (int i = index; i < graph->size - 1; i++) {
        for (int j = 0; j < graph->size; j++) {
            graph->adjMat[i][j] = graph->adjMat[i + 1][j];
        }
    }
    // 在邻接矩阵中删除索引 index 的列
    for (int i = 0; i < graph->size; i++) {
        for (int j = index; j < graph->size - 1; j++) {
            graph->adjMat[i][j] = graph->adjMat[i][j + 1];
        }
    }
    graph->size--;
}

/* 添加边 */
// 参数 i, j 对应 vertices 元素索引
void addEdge(GraphAdjMat *graph, int i, int j) {
    if (i < 0 || j < 0 || i >= graph->size || j >= graph->size || i == j) {
        fprintf(stderr, " 边索引越界或相等\n");
        return;
    }
    graph->adjMat[i][j] = 1;
    graph->adjMat[j][i] = 1;
}

/* 删除边 */
// 参数 i, j 对应 vertices 元素索引
void removeEdge(GraphAdjMat *graph, int i, int j) {
    if (i < 0 || j < 0 || i >= graph->size || j >= graph->size || i == j) {
        fprintf(stderr, " 边索引越界或相等\n");
        return;
    }
    graph->adjMat[i][j] = 0;
    graph->adjMat[j][i] = 0;
}

/* 打印邻接矩阵 */
void printGraphAdjMat(GraphAdjMat *graph) {
    printf(" 顶点列表 = ");
    printArray(graph->vertices, graph->size);
    printf(" 邻接矩阵 =\n");
    for (int i = 0; i < graph->size; i++) {
        printArray(graph->adjMat[i], graph->size);
    }
}

2.基于邻接表的实现

• 设无向图的顶点总数为 𝑛、边总数为 𝑚

• 添加边 ：在顶点对应链表的末尾 添加边即可，使用 𝑂(1) 时间。因为是无向图，所以需要同时添加两个方向的边。

• 删除边 ：在顶点对应链表中查找并删除指定边，使用 𝑂(𝑚) 时间。在无向图中，需要同时删除两个方向的边

• 添加顶点 ：在邻接表中添加一个链表，并将新增顶点作为链表头节点，使用 𝑂(1) 时间。

• 删除顶点 ：需遍历整个邻接表，删除包含指定顶点的所有边，使用 𝑂(𝑛 + 𝑚) 时间。

• 初始化 ：在邻接表中创建 𝑛 个顶点和 2𝑚 条边，使用 𝑂(𝑛 + 𝑚) 时间。

• 代码实现

/* 节点结构体 */
typedef struct AdjListNode {
    Vertex *vertex; // 顶点
    struct AdjListNode *next; // 后继节点
} AdjListNode;
/* 查找顶点对应的节点 */
AdjListNode *findNode(GraphAdjList *graph, Vertex *vet) {
    for (int i = 0; i < graph->size; i++) {
        if (graph->heads[i]->vertex == vet) {
            return graph->heads[i];
        }
    }
    return NULL;
}


/* 添加边辅助函数 */
void addEdgeHelper(AdjListNode *head, Vertex *vet) {
    AdjListNode *node = (AdjListNode *)malloc(sizeof(AdjListNode));
    node->vertex = vet;
    // 头插法
    node->next = head->next;
    head->next = node;
}

/* 删除边辅助函数 */
void removeEdgeHelper(AdjListNode *head, Vertex *vet) {
    AdjListNode *pre = head;
    AdjListNode *cur = head->next;
    // 在链表中搜索 vet 对应节点
    while (cur != NULL && cur->vertex != vet) {
        pre = cur;
        cur = cur->next;
    }
    if (cur == NULL)
        return;
    // 将 vet 对应节点从链表中删除
    pre->next = cur->next;
    // 释放内存
    free(cur);
}

/* 基于邻接表实现的无向图类 */
typedef struct {
    AdjListNode *heads[MAX_SIZE]; // 节点数组
    int size; // 节点数量
} GraphAdjList;

/* 构造函数 */
GraphAdjList *newGraphAdjList() {
    GraphAdjList *graph = (GraphAdjList *)malloc(sizeof(GraphAdjList));
    if (!graph) {
        return NULL;
    }
    graph->size = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        graph->heads[i] = NULL;
    }
    return graph;
}

/* 析构函数 */
void delGraphAdjList(GraphAdjList *graph) {
    for (int i = 0; i < graph->size; i++) {
        AdjListNode *cur = graph->heads[i];
        while (cur != NULL) {
            AdjListNode *next = cur->next;
            if (cur != graph->heads[i]) {
                free(cur);
            }
            cur = next;
        }
        free(graph->heads[i]->vertex);
        free(graph->heads[i]);
    }
    free(graph);
}

/* 查找顶点对应的节点 */
AdjListNode *findNode(GraphAdjList *graph, Vertex *vet) {
    for (int i = 0; i < graph->size; i++) {
        if (graph->heads[i]->vertex == vet) {
            return graph->heads[i];
        }
    }
    return NULL;
}

/* 添加边 */
void addEdge(GraphAdjList *graph, Vertex *vet1, Vertex *vet2) {
    AdjListNode *head1 = findNode(graph, vet1);
    AdjListNode *head2 = findNode(graph, vet2);
    assert(head1 != NULL && head2 != NULL && head1 != head2);
    // 添加边 vet1 - vet2
    addEdgeHelper(head1, vet2);
    addEdgeHelper(head2, vet1);
}

/* 删除边 */
void removeEdge(GraphAdjList *graph, Vertex *vet1, Vertex *vet2) {
    AdjListNode *head1 = findNode(graph, vet1);
    AdjListNode *head2 = findNode(graph, vet2);
    assert(head1 != NULL && head2 != NULL);
    // 删除边 vet1 - vet2
    removeEdgeHelper(head1, head2->vertex);
    removeEdgeHelper(head2, head1->vertex);
}

/* 添加顶点 */
void addVertex(GraphAdjList *graph, Vertex *vet) {
    assert(graph != NULL && graph->size < MAX_SIZE);
    AdjListNode *head = (AdjListNode *)malloc(sizeof(AdjListNode));
    head->vertex = vet;
    head->next = NULL;
    // 在邻接表中添加一个新链表
    graph->heads[graph->size++] = head;
}

/* 删除顶点 */
void removeVertex(GraphAdjList *graph, Vertex *vet) {
    AdjListNode *node = findNode(graph, vet);
    assert(node != NULL);
    // 在邻接表中删除顶点 vet 对应的链表
    AdjListNode *cur = node, *pre = NULL;
    while (cur) {
        pre = cur;
        cur = cur->next;
        free(pre);
    }
    // 遍历其他顶点的链表，删除所有包含 vet 的边
    for (int i = 0; i < graph->size; i++) {
        cur = graph->heads[i];
        pre = NULL;
        while (cur) {
            pre = cur;
            cur = cur->next;
            if (cur && cur->vertex == vet) {
                pre->next = cur->next;
                free(cur);
                break;
            }
        }
    }
    // 将该顶点之后的顶点向前移动，以填补空缺
    int i;
    for (i = 0; i < graph->size; i++) {
        if (graph->heads[i] == node)
            break;
    }
    for (int j = i; j < graph->size - 1; j++) {
        graph->heads[j] = graph->heads[j + 1];
    }
    graph->size--;
    free(vet);
}

# 可以使用列表（动态数组）来代替链表

# 使用哈希表来存储邻接表

3.效率对比

• 设图中共有 𝑛 个顶点和 𝑚 条边

	邻接矩阵	邻接表（链表）	邻接表（哈希表）
判断是否邻接	𝑂(1)	𝑂(𝑚)	𝑂(1)
添加边	𝑂(1)	𝑂(1)	𝑂(1)
删除边	𝑂(1)	𝑂(𝑚)	𝑂(1)
添加顶点	𝑂(𝑛)	𝑂(1)	𝑂(1)
删除顶点	𝑂($𝑛^2$ )	𝑂(𝑛 + 𝑚)	𝑂(𝑛)
内存空间占用	𝑂($𝑛^2$ )	𝑂(𝑛 + 𝑚)	𝑂(𝑛 + 𝑚)

• 实际上，在邻接矩阵中操作边的效率更高，只需一次数组访问或赋值操作即可。
• 综合来看，邻接矩阵 体现了以空间换时间 的原则，而邻接表 体现了以时间换空间 的原则。

3.图的遍历

• 图的遍历方式也可分为两种：广度优先遍历 和深度优先遍历

1.广度优先遍历

• 广度优先遍历 （BFS）是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点 ，并一层层向外扩张

• 从左上角顶点出发，首先遍历该顶点的所有邻接顶点，然后遍历下一个顶点的所有邻接顶点，以此类推，直至所有顶点访问完毕。

1.算法实现

• BFS 通常借助队列来实现，队列具有先入先出 的性质，这与 BFS 的由近及远 的思想异曲同工。
  • 1.将遍历起始顶点 startVet 加入队列，并开启循环。
  • 2.在循环的每轮迭代中，弹出队首顶点并记录访问，然后将该顶点的所有邻接顶点加入到队列尾部。
  • 3.循环步骤 2. ，直到所有顶点被访问完毕后结束。

# 为了防止重复遍历顶点，需要借助一个哈希集合 visited 来记录哪些节点已被访问

# 哈希集合可以看作一个只存储 key 而不存储 value 的哈希表，它可以在 𝑂(1) 时间复杂度下进行 key的增删查改操作。根据 key 的唯一性，哈希集合通常用于数据去重等场景。

• 代码实现

/* 节点队列结构体 */
typedef struct {
    Vertex *vertices[MAX_SIZE];
    int front, rear, size;
} Queue;

/* 构造函数 */
Queue *newQueue() {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->front = q->rear = q->size = 0;
    return q;
}

/* 判断队列是否为空 */
int isEmpty(Queue *q) {
    return q->size == 0;
}

/* 入队操作 */
void enqueue(Queue *q, Vertex *vet) {
    q->vertices[q->rear] = vet;
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->size++;
}

/* 出队操作 */
Vertex *dequeue(Queue *q) {
    Vertex *vet = q->vertices[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    q->size--;
    return vet;
}

/* 检查顶点是否已被访问 */
int isVisited(Vertex **visited, int size, Vertex *vet) {
    // 遍历查找节点，使用 O(n) 时间
    for (int i = 0; i < size; i++) {
        if (visited[i] == vet)
            return 1;
    }
    return 0;
}

/* 广度优先遍历 */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
void graphBFS(GraphAdjList *graph, Vertex *startVet, Vertex **res, int *resSize, Vertex **visited, int
	*visitedSize) { 
    // 队列用于实现 BFS
    Queue *queue = newQueue();
    enqueue(queue, startVet);
    visited[(*visitedSize)++] = startVet;
    // 以顶点 vet 为起点，循环直至访问完所有顶点
    while (!isEmpty(queue)) {
        Vertex *vet = dequeue(queue); // 队首顶点出队
        res[(*resSize)++] = vet; // 记录访问顶点
        // 遍历该顶点的所有邻接顶点
        AdjListNode *node = findNode(graph, vet);
        while (node != NULL) {
            // 跳过已被访问的顶点
            if (!isVisited(visited, *visitedSize, node->vertex)) {
                enqueue(queue, node->vertex); // 只入队未访问的顶点
                visited[(*visitedSize)++] = node->vertex; // 标记该顶点已被访问
            }
            node = node->next;
        }
    }
    // 释放内存
    free(queue);
}

• 演示

# 广度优先遍历 的序列不唯一。广度优先遍历只要求按由近及远 的顺序遍历，而多个相同距离的顶点的遍历顺序允许被任意打乱。

2.复杂度分析

• 时间复杂度 ：所有顶点都会入队并出队一次，使用 𝑂(|𝑉 |) 时间；在遍历邻接顶点的过程中，由于是无向图，因此所有边都会被访问 2 次，使用 𝑂(2|𝐸|) 时间；总体使用 𝑂(|𝑉 | + |𝐸|) 时间。
• 空间复杂度 ：列表 res ，哈希集合 visited ，队列 que 中的顶点数量最多为 |𝑉 | ，使用 𝑂(|𝑉 |) 空间。

2.深度优先遍历

• 深度优先遍历（DFS）是一种优先走到底、无路可走再回头的遍历方式

1.算法实现

• 基于递归来实现
• 也需要借助一个哈希集合 visited 来记录已被访问的顶点，以避免重复访问顶点。

/* 检查顶点是否已被访问 */
int isVisited(Vertex **res, int size, Vertex *vet) {
    // 遍历查找节点，使用 O(n) 时间
    for (int i = 0; i < size; i++) {
        if (res[i] == vet) {
            return 1;
        }
    }
    return 0;
}

/* 深度优先遍历辅助函数 */
void dfs(GraphAdjList *graph, Vertex **res, int *resSize, Vertex *vet) {
    // 记录访问顶点
    res[(*resSize)++] = vet;
    // 遍历该顶点的所有邻接顶点
    AdjListNode *node = findNode(graph, vet);
    while (node != NULL) {
        // 跳过已被访问的顶点
        if (!isVisited(res, *resSize, node->vertex)) {
            // 递归访问邻接顶点
            dfs(graph, res, resSize, node->vertex);
        }
        node = node->next;
    }
}

/* 深度优先遍历 */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
void graphDFS(GraphAdjList *graph, Vertex *startVet, Vertex **res, int *resSize) {
    dfs(graph, res, resSize, startVet);
}

# 与广度优先遍历类似，深度优先遍历序列的顺序也不是唯一的。给定某顶点，先往哪个方向探索都可以，即邻接顶点的顺序可以任意打乱，都是深度优先遍历。

以树的遍历为例，“根 → 左 → 右”“左 → 根 → 右” “左 → 右 → 根”分别对应前序、中序、后序遍历，它们展示了三种遍历优先级，然而这三者都属于深度优先遍历。

2.复杂度分析

• 时间复杂度：所有顶点都会被访问 1 次，使用 𝑂(|𝑉 |) 时间；所有边都会被访问 2 次，使用 𝑂(2|𝐸|) 时间；总体使用 𝑂(|𝑉 | + |𝐸|) 时间。
• 空间复杂度：列表 res ，哈希集合 visited 顶点数量最多为 |𝑉 | ，递归深度最大为 |𝑉 | ，因此使用 𝑂(|𝑉 |)空间。