数据结构-图的基本概念与实现

桃扇骨 2024-03-22 17:16 15阅读 0赞

**目录**

一、引言

二、图的基本概念

1.图的定义

2.图的组成部分

3.图的分类

三、图的存储方式

1.邻接矩阵

2.邻接表

3.十字链表

4.邻接多重表

四、图的遍历算法

1.深度优先遍历

2.广度优先遍历

五、最短路径算法

1.迪杰斯特拉算法

2.弗洛伊德算法

六、最小生成树算法

1.普里姆算法

2.克鲁斯卡尔算法

七、总结

八、使用邻接矩阵实现简单图

--------------------

## 一、引言 ##

在计算机科学中，图是一种非常重要的数据结构，它可以用来描述各种实际问题，如社交网络、地图路线规划、电路设计等。本文将介绍图的基本概念、存储方式、遍历算法、最短路径算法和最小生成树算法等内容，希望能够帮助读者更好地理解和应用图这一数据结构。

## 二、图的基本概念 ##

### 1.图的定义 ###

图是由若干个节点和它们之间的边组成的一种数据结构。节点也称为顶点，边表示顶点之间的关系。图可以用来描述各种实际问题，如社交网络、地图路线规划、电路设计等。

### 2.图的组成部分 ###

图由两个基本部分组成：顶点和边。顶点是图中的基本元素，用来表示实体或概念，通常用圆圈表示。边是连接顶点的线，用来表示顶点之间的关系，通常用直线或曲线表示。

### 3.图的分类 ###

根据图的性质和应用场景，图可以分为以下几类：

（1）无向图：顶点之间的边没有方向，表示两个顶点之间的关系是相互的。

（2）有向图：顶点之间的边有方向，表示两个顶点之间的关系是单向的。

（3）带权图：顶点之间的边有权值，表示两个顶点之间的关系有一定的权重。

（4）稠密图：顶点之间的边比较多，通常使用邻接矩阵来存储。

（5）稀疏图：顶点之间的边比较少，通常使用邻接表来存储。

## 三、图的存储方式 ##

图的存储方式有多种，常用的有邻接矩阵、邻接表、十字链表和邻接多重表等。

### 1.邻接矩阵 ###

邻接矩阵是一种二维数组，用来表示顶点之间的关系。如果顶点i和顶点j之间有边，则邻接矩阵中第i行第j列的值为1，否则为0。如果是带权图，则邻接矩阵中存储的是边的权值。

邻接矩阵的优点是查询两个顶点之间是否有边的时间复杂度为O(1)，缺点是空间复杂度比较高，当图比较稀疏时，会浪费很多空间。

### 2.邻接表 ###

邻接表是一种链表，用来表示每个顶点的邻接点。对于每个顶点i，邻接表中存储的是与它相邻的顶点的编号。如果是带权图，则邻接表中还需要存储边的权值。

邻接表的优点是空间复杂度比较低，当图比较稀疏时，可以节省很多空间。缺点是查询两个顶点之间是否有边的时间复杂度为O(k)，其中k是顶点i的度数，即与它相邻的顶点的个数。

### 3.十字链表 ###

十字链表是一种链表，用来表示有向图中每个顶点的出边和入边。对于每个顶点i，十字链表中存储的是它的出边和入边的信息，包括边的起点、终点和权值等。

十字链表的优点是可以方便地遍历有向图中每个顶点的出边和入边，缺点是空间复杂度比较高，当图比较稀疏时，会浪费很多空间。

### 4.邻接多重表 ###

邻接多重表是一种存储无向图的方式，它可以有效地存储无向图中的重边和自环。在邻接多重表中，每个顶点都对应一个链表，链表中存储与该顶点相邻的顶点以及它们之间的边。

## 四、图的遍历算法 ##

### 1.深度优先遍历 ###

深度优先遍历是一种递归的方式，从图的某个顶点开始，沿着一条路径访问图中的所有顶点，直到到达最后一个顶点，然后回溯到前一个顶点，继续访问其他路径。深度优先遍历的时间复杂度为O(n+m)，其中n为顶点数，m为边数。

### 2.广度优先遍历 ###

广度优先遍历是一种非递归的方式，从图的某个顶点开始，先访问该顶点的所有邻居顶点，然后再访问邻居顶点的邻居顶点，以此类推，直到访问完所有顶点。广度优先遍历的时间复杂度为O(n+m)，其中n为顶点数，m为边数。

## 五、最短路径算法 ##

### 1.迪杰斯特拉算法 ###

迪杰斯特拉算法是一种贪心算法，用于求解带权有向图中的单源最短路径问题。该算法的基本思想是从起点开始，依次选择与起点距离最短的顶点，并更新与该顶点相邻的顶点的距离。迪杰斯特拉算法的时间复杂度为O(n^2)，其中n为顶点数。

### 2.弗洛伊德算法 ###

弗洛伊德算法是一种动态规划算法，用于求解带权有向图中的所有顶点之间的最短路径。该算法的基本思想是通过中间顶点的枚举，逐步更新每对顶点之间的最短路径。弗洛伊德算法的时间复杂度为O(n^3)，其中n为顶点数。

## 六、最小生成树算法 ##

### 1.普里姆算法 ###

普里姆算法是一种贪心算法，用于求解带权无向图的最小生成树。该算法的基本思想是从任意一个顶点开始，依次选择与当前生成树相邻的权值最小的边，并将其加入到生成树中。普里姆算法的时间复杂度为O(n^2)，其中n为顶点数。

### 2.克鲁斯卡尔算法 ###

克鲁斯卡尔算法是一种贪心算法，用于求解带权无向图的最小生成树。该算法的基本思想是将所有边按照权值从小到大排序，然后依次选择权值最小的边，并判断该边是否会形成环，如果不会，则将该边加入到生成树中。克鲁斯卡尔算法的时间复杂度为O(mlogm)，其中m为边数。

## 七、总结 ##

图是一种非常重要的数据结构，它广泛应用于计算机科学和工程领域。本文介绍了图的基本概念、存储方式、遍历算法、最短路径算法和最小生成树算法，希望能够对读者有所帮助。

## 八、使用邻接矩阵实现简单图 ##

以下是使用邻接矩阵实现的简单图的C++代码：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    class Graph {
    private:
        int numVertices;
        vector<vector<int>> adjMatrix;
    
    public:
        Graph(int numVertices) {
            this->numVertices = numVertices;
            adjMatrix.resize(numVertices, vector<int>(numVertices, 0));
        }
    
        void addEdge(int i, int j) {
            adjMatrix[i][j] = 1;
            adjMatrix[j][i] = 1;
        }
    
        void removeEdge(int i, int j) {
            adjMatrix[i][j] = 0;
            adjMatrix[j][i] = 0;
        }
    
        bool isEdge(int i, int j) {
            return adjMatrix[i][j] == 1;
        }
    
        void printGraph() {
            for (int i = 0; i < numVertices; i++) {
                cout << i << " : ";
                for (int j = 0; j < numVertices; j++) {
                    if (adjMatrix[i][j] == 1) {
                        cout << j << " ";
                    }
                }
                cout << endl;
            }
        }
    };
    
    int main() {
        Graph g(5);
    
        g.addEdge(0, 1);
        g.addEdge(0, 4);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 4);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
    
        g.printGraph();
    
        return 0;
    }

这个实现使用了邻接矩阵来表示图。在构造函数中，我们初始化了一个大小为numVertices x numVertices的矩阵，并将所有元素初始化为0。addEdge函数将两个顶点之间的边添加到矩阵中，removeEdge函数将它们从矩阵中删除。isEdge函数检查两个顶点之间是否有边。printGraph函数打印出图的邻接矩阵表示。在main函数中，我们创建了一个大小为5的图，并添加了一些边。最后，我们打印出图的邻接矩阵表示。