【数据结构与算法】图的概述（内含源码）

骑猪看日落 2024-04-13 14:15 132阅读 0赞

> 个人主页：[【?个人主页】][Link 1]  
> 系列专栏：[【❤️数据结构与算法】][Link 2]  
> 学习名言：天子重英豪，文章教儿曹。万般皆下品，惟有读书高——《神童诗劝学》

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

![在这里插入图片描述][5f53cc7046814a708b5db9a679ed5b5c.jpeg_pic_center]

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

## 系列文章目录 ##

第一章 ❤️ [学前知识][Link 3]  
第二章 ❤️ [单向链表][Link 4]  
第三章 ❤️ [递归][Link 5]  
…

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

#### 文章目录 ####

*  系列文章目录
 *  前言
 *  什么是图？
 *  图的分类
 *   *  图按照无方向和有方向分为：无向图和有向图。
     *  图按照边分为：稀疏图和稠密图
     *  完全图
     *  网
 *  顶点与边
 *   *  顶点与边的关系
 *  图的存储结构
 *   *  邻接列表
     *  邻接矩阵
 *  图的定义和术语总结

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

## 前言 ##

> 与线性表中的元素是“一对一”的关系和树中的元素是“一对多”的关系不同的是，数据结构中图的元素则是“多对多”的关系。图（Graph）是一种复杂的非线性结构，在图结构中，每个元素都可以有零个或多个前驱，也可以有零个或多个后继，也就是说，元素之间的关系是任意的，今天就让我来带大家了解数据结构中图结构吧。

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

## 什么是图？ ##

在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。  
*顶点有时也称为节点或者交点，边有时也称为链接*  
图有各种形状和大小。边可以有权重（weight），即每一条边会被分配一个正数或者负数值。

> 图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合

![在这里插入图片描述][b68db4d3519e4978b8b1030e3d45189f.png_pic_center]

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

## 图的分类 ##

### 图按照无方向和有方向分为：无向图和有向图。 ###

![在这里插入图片描述][a209a435d4904d88b1ce191695c8aee5.png_pic_center]

> 不带有箭头指向的图只由顶点和边构成称为无向图，有向图是由顶点和弧（有向边构成）。弧有弧头和弧尾区别。

### 图按照边分为：稀疏图和稠密图 ###

**这是个模糊的概念，同样是相对的概念。**

### 完全图 ###

> 如果任意两个顶点之间都存在边叫完全图，有向的边叫有向完全图。如果无重复的边或者顶点到自身的边叫简单图。在用数学方式表示时，无向边用()表示，有向边用<>表示。我们目前接触到的图全是简单图。

![在这里插入图片描述][8b2bfeaa844e412593101911ed4c5573.png_pic_center]*没有重复的边或者到自身的边（简单图），右图则有*

### 网 ###

![在这里插入图片描述][c61df4fde4024b90acb0fd710b78ae7a.png_pic_center]*这种边带权值的图叫网*

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

## 顶点与边 ##

### 顶点与边的关系 ###

*  顶点的度：顶点关联边的数目。有向图图中有，入度：方向指向顶点的边；出度：方向背向顶点的边。在有向图中顶点的度就是两者之和。
 *  路径长度：路径上边或者弧的数目。

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

## 图的存储结构 ##

理论上，图就是一堆顶点和边对象而已，那我们又如何用代码来实现它呢？

**通常我们有两种选择：邻接列表和邻接矩阵。**

### 邻接列表 ###

> 邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。  
> 对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。

![在这里插入图片描述][5db3c21a986b499280afe2ba38eb335e.png_pic_center]  
顶点表的各个结点由data（数据域）和Firstedge（指针域）两个域表示，data是数据域，指针域指向边表的第一个结点，即顶点的第一个邻接点。边表结点由adjvex（邻接点域）和next两个域组成。  
邻接点域存储某顶点的邻接点在顶点表中坐标，next存储边表中下一个结点指针。  
如图中v1顶点与v2、v0互为邻接点，则在v1边表中，adjvex分别为0和2。  
**有向图也可以用邻接表，出度表叫邻接表，入度表尾逆邻接表**。

#include <stdio.h>
    #include <stdlib.h>
    
    // 邻接表中每个节点的结构体
    struct AdjListNode {
        
        int dest;
        struct AdjListNode* next;
    };
    
    // 邻接表的结构体
    struct AdjList {
        
        struct AdjListNode *head;
    };
    
    // 图的结构体
    struct Graph {
        
        int V;
        struct AdjList* array;
    };
    
    // 创建一个新的邻接表节点
    struct AdjListNode* newAdjListNode(int dest) {
        
        struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
        newNode->dest = dest;
        newNode->next = NULL;
        return newNode;
    }
    
    // 创建一个具有V个顶点的新图
    struct Graph* createGraph(int V) {
        
        struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
        graph->V = V;
    
        // 创建邻接表数组
        graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
    
        // 初始化链表头为空
        for (int i = 0; i < V; ++i)
            graph->array[i].head = NULL;
    
        return graph;
    }
    
    // 添加一个边到无向图
    void addEdge(struct Graph* graph, int src, int dest) {
        
        // 添加一条从src到dest的边
        struct AdjListNode* newNode = newAdjListNode(dest);
        newNode->next = graph->array[src].head;
        graph->array[src].head = newNode;
    
        // 添加一条从dest到src的边，因为是无向图
        newNode = newAdjListNode(src);
        newNode->next = graph->array[dest].head;
        graph->array[dest].head = newNode;
    }
    
    // 打印邻接列表表示的图
    void printGraph(struct Graph* graph) {
        
        for (int v = 0; v < graph->V; ++v) {
        
            struct AdjListNode* pCrawl = graph->array[v].head;
            printf("\n 邻接列表%d: ", v);
            while (pCrawl) {
        
                printf("-> %d", pCrawl->dest);
                pCrawl = pCrawl->next;
            }
            printf("\n");
        }
    }
    
    int main() {
        
        // 创建一个具有5个顶点的新图
        struct Graph* graph = createGraph(5);
    
        // 添加边
        addEdge(graph, 0, 1);
        addEdge(graph, 0, 2);
        addEdge(graph, 1, 2);
        addEdge(graph, 1, 3);
        addEdge(graph, 2, 3);
        addEdge(graph, 2, 4);
        addEdge(graph, 3, 4);
    
        // 打印邻接列表表示的图
        printGraph(graph);
    
        return 0;
    }

### 邻接矩阵 ###

邻接矩阵(Adjacency Matrix):是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V=\{v1,v2,…,vn\}。G的邻接矩阵是一个具有下列性质的n阶方阵:  
![在这里插入图片描述][de011591c54c48e3b864251a9912275f.png_pic_center]

>  *  对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零(在此仅讨论无向简单图)，副对角线不一定为0，有向图则不一定如此。
>  *  在无向图中，任一顶点i的度为第i列(或第i行)所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。
>  *  用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n(n-1)/2个空间

#include <stdio.h>
    
    #define MAX_NODES 100
    
    int adj_matrix[MAX_NODES][MAX_NODES];
    
    void add_edge(int start, int end) {
        
        adj_matrix[start][end] = 1;
        adj_matrix[end][start] = 1; // 无向图需要将两个方向都标记为已连接
    }
    
    int main() {
        
    
        // 添加边
        add_edge(0, 1);
        add_edge(0, 2);
        add_edge(1, 2);
        add_edge(2, 3);
    
        // 输出邻接矩阵
        printf("邻接矩阵：\n");
        for (int i = 0; i < MAX_NODES; i++) {
        
            for (int j = 0; j < MAX_NODES; j++) {
        
                printf("%d ", adj_matrix[i][j]);
            }
            printf("\n");
        }
    
        return 0;
    }

## 图的定义和术语总结 ##

> 顶点（Vertex）：图中的数据元素通常称为顶点  
> 弧（Arc）：若< v,w >∈VR，则< v,w >表示从v到w的一条弧  
> 弧尾（Tail）：v为弧尾或初始点（Initial node）  
> 弧头（Head）：w为弧头或终端点（Terminal node）  
> 有向图（Digraph）：图中每条边都有方向  
> 无向图（Undigraph）：图中每条边都没有方向  
> 连通图（Connected Graph）：对于图中任意两个顶点v，j∈V，v和j都是连通的，则称G是连通图  
> 连通分量（Connected Compenent）：无向图中的极大连通子图  
> 完全图（Completed graph）：有1/2\*n（n-1）条边的无向图称为完全图  
> 有向完全图：具有n（n-1）条弧的有向图称为有向完全图  
> 稀疏图（Sparse graph）：有很少条边或弧（如e < nlogn）的图称为稀疏图  
> 稠密图（Dense graph）：有很多条边或弧  
> 权（Weight）：有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权  
> 度（Degree）：定点v的度是和v相关联的边的数目，记为TD（V）  
> 入度（InDegree）：以顶点v为头的弧的数目称为v的入度，记为ID（v）  
> 出度（Outdegree）：以v为尾的弧的数目成为v的出度，记为OD（v）  
> V： 是顶点的有穷非空集合  
> VR：是两个顶点之间的关系的集合  
> n：表示图中顶点数目  
> e：表示边或弧的数目

![在这里插入图片描述][1280e294ad1048e4905928c98adbd1d0.gif_pic_center]

[Link 1]: https://blog.csdn.net/weixin_73602725?type=blog
[Link 2]: https://blog.csdn.net/weixin_73602725/category_12226568.html?spm=1001.2014.3001.5482
[5f53cc7046814a708b5db9a679ed5b5c.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/62c7c7cbfb094d54a5fae6997707460a.jpeg
[Link 3]: https://blog.csdn.net/weixin_73602725/article/details/129406349
[Link 4]: https://blog.csdn.net/weixin_73602725/article/details/129270463
[Link 5]: https://blog.csdn.net/weixin_73602725/article/details/129450203
[b68db4d3519e4978b8b1030e3d45189f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/5890f0659e6345949f3b9c43f9ab0376.png
[a209a435d4904d88b1ce191695c8aee5.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/da645d3b2d8049e3aa2753580c5c3b20.png
[8b2bfeaa844e412593101911ed4c5573.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/7357a82f52af415aa79bf1d06daa7af3.png
[c61df4fde4024b90acb0fd710b78ae7a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/4f080dd1ca9a405fb1a8a2abbc3bdca3.png
[5db3c21a986b499280afe2ba38eb335e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/50ab7f3144ca493b93a966e32fd1f067.png
[de011591c54c48e3b864251a9912275f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/f547a8dc478e4bd3a1c60ece2c0171e9.png
[1280e294ad1048e4905928c98adbd1d0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/2924c768b55c4c019e7ed42bbbc6cb84.gif