您现在的位置是：网站首页>技术百科技术百科

数据结构之图（Graph）

小大寒2024-01-01[技术百科]博学多闻

数据结构之图（Graph）图（Graph）是一种由顶点（Vertex）和边（Edge）构成的数据结构，边连接顶点，表示顶点之间的关系。图可分为有向图和无向图，边有方向或无方向。图在很多实际问题中都有广泛应用，如社交网络、计算机网络、地图导航等。

数据结构之图（Graph）

1. 基础概念

1.1 数据结构之图（Graph）的定义

图是由一组顶点和一组边构成的集合。每条边连接两个顶点，图的核心思想是通过边来表示顶点之间的关系。图可以分为：

有向图：边有方向，表示从一个顶点指向另一个顶点。
无向图：边没有方向，表示两个顶点之间的双向关系。
加权图：边带有权重，表示连接的强度或距离。
无权图：边没有权重。

1.2 数据结构之图（Graph）的特点

图的特点包括：

图是非线性的，可以表示更复杂的关系。
边可以是有向或无向，提供了丰富的表示能力。
图可以包含环路、孤立点等结构。
图可以表示任意两个顶点间的关系，而不需要是顺序结构。

1.3 使用场景

图在许多领域有广泛的应用：

社交网络：表示用户和用户之间的关系。
计算机网络：表示计算机之间的连接。
路径规划：如地图导航、机器人路径寻找等。
推荐系统：例如，基于物品的协同过滤。

2. 实现与操作

2.1 核心操作实现

在C语言中实现一个简单的无向图：

        #include <stdio.h>
        #include <stdlib.h>
        
        #define MAX_VERTICES 5
        
        // 图的邻接矩阵表示
        int graph[MAX_VERTICES][MAX_VERTICES];
        
        // 初始化图
        void initGraph() {
            for (int i = 0; i < MAX_VERTICES; i++) {
                for (int j = 0; j < MAX_VERTICES; j++) {
                    graph[i][j] = 0; // 初始时没有边
                }
            }
        }
        
        // 插入边
        void addEdge(int v1, int v2) {
            if (v1 < MAX_VERTICES && v2 < MAX_VERTICES) {
                graph[v1][v2] = 1;
                graph[v2][v1] = 1;  // 无向图
            }
        }
        
        // 打印图的邻接矩阵
        void printGraph() {
            for (int i = 0; i < MAX_VERTICES; i++) {
                for (int j = 0; j < MAX_VERTICES; j++) {
                    printf("%d ", graph[i][j]);
                }
                printf("\n");
            }
        }
        
        int main() {
            initGraph();
            addEdge(0, 1);
            addEdge(1, 2);
            addEdge(3, 4);
            
            printf("图的邻接矩阵表示：\n");
            printGraph();
            return 0;
        }
        </stdlib.h></stdio.h>

2.2 代码详解

此代码实现了一个简单的无向图的邻接矩阵表示：

首先，定义了一个全局变量 `graph`，表示图的邻接矩阵。
通过 `initGraph()` 函数初始化图，将所有的边设为0。
通过 `addEdge()` 函数添加一条边，设置相应位置为1。由于是无向图，两个方向的元素都设置为1。
`printGraph()` 函数打印图的邻接矩阵。

3. 时间与空间复杂度分析

3.1 时间复杂度

初始化图的时间复杂度为 O(V^2)，其中 V 为顶点数，因为需要创建一个 V x V 的邻接矩阵。
插入边的时间复杂度为 O(1)，因为我们直接在邻接矩阵中设置相应位置的值。
打印图的时间复杂度为 O(V^2)，因为需要遍历整个邻接矩阵。

3.2 空间复杂度

空间复杂度为 O(V^2)，因为我们使用了邻接矩阵来表示图，占用了 V x V 的空间。

4. 优缺点与局限性

4.1 优点

能够高效地表示密集图（即边较多的图）。
边的查询操作非常快速，时间复杂度为 O(1)。

4.2 缺点与局限性

对于稀疏图，邻接矩阵会浪费大量空间。
无法高效地处理图中的动态边的添加和删除。

5. 常见应用场景

5.1 实际应用

以下是一个实现Top-K问题的图应用场景：

        #include <stdio.h>
        #include <stdlib.h>
        
        #define MAX_VERTICES 5
        
        int graph[MAX_VERTICES][MAX_VERTICES];
        
        void initGraph() {
            for (int i = 0; i < MAX_VERTICES; i++) {
                for (int j = 0; j < MAX_VERTICES; j++) {
                    graph[i][j] = 0;
                }
            }
        }
        
        void addEdge(int v1, int v2) {
            if (v1 < MAX_VERTICES && v2 < MAX_VERTICES) {
                graph[v1][v2] = 1;
                graph[v2][v1] = 1;
            }
        }
        
        void printGraph() {
            for (int i = 0; i < MAX_VERTICES; i++) {
                for (int j = 0; j < MAX_VERTICES; j++) {
                    printf("%d ", graph[i][j]);
                }
                printf("\n");
            }
        }
        
        int main() {
            initGraph();
            addEdge(0, 1);
            addEdge(1, 2);
            addEdge(3, 4);
            
            printf("图的邻接矩阵表示：\n");
            printGraph();
            return 0;
        }
        </stdlib.h></stdio.h>