您现在的位置是:首页 >技术交流 >【数据结构与算法】图的概述(内含源码)网站首页技术交流
【数据结构与算法】图的概述(内含源码)
个人主页:【?个人主页】
系列专栏:【❤️数据结构与算法】
学习名言:天子重英豪,文章教儿曹。万般皆下品,惟有读书高——《神童诗劝学》
系列文章目录
第一章 ❤️ 学前知识
第二章 ❤️ 单向链表
第三章 ❤️ 递归
…
前言
与线性表中的元素是“一对一”的关系和树中的元素是“一对多”的关系不同的是,数据结构中图的元素则是“多对多”的关系。图(Graph)是一种复杂的非线性结构,在图结构中,每个元素都可以有零个或多个前驱,也可以有零个或多个后继,也就是说,元素之间的关系是任意的,今天就让我来带大家了解数据结构中图结构吧。
什么是图?
在计算机科学中,一个图就是一些顶点的集合,这些顶点通过一系列边结对(连接)。顶点用圆圈表示,边就是这些圆圈之间的连线。顶点之间通过边连接。
顶点有时也称为节点或者交点,边有时也称为链接
图有各种形状和大小。边可以有权重(weight),即每一条边会被分配一个正数或者负数值。
图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合
图的分类
图按照无方向和有方向分为:无向图和有向图。
不带有箭头指向的图只由顶点和边构成称为无向图,有向图是由顶点和弧(有向边构成)。弧有弧头和弧尾区别。
图按照边分为:稀疏图和稠密图
这是个模糊的概念,同样是相对的概念。
完全图
如果任意两个顶点之间都存在边叫完全图,有向的边叫有向完全图。如果无重复的边或者顶点到自身的边叫简单图。在用数学方式表示时,无向边用()表示,有向边用<>表示。我们目前接触到的图全是简单图。
没有重复的边或者到自身的边(简单图),右图则有
网
这种边带权值的图叫网
顶点与边
顶点与边的关系
- 顶点的度:顶点关联边的数目。有向图图中有,入度:方向指向顶点的边;出度:方向背向顶点的边。在有向图中顶点的度就是两者之和。
- 路径长度:路径上边或者弧的数目。
图的存储结构
理论上,图就是一堆顶点和边对象而已,那我们又如何用代码来实现它呢?
通常我们有两种选择:邻接列表和邻接矩阵。
邻接列表
邻接表,存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中。
对于无向图来说,使用邻接表进行存储也会出现数据冗余,表头结点A所指链表中存在一个指向C的表结点的同时,表头结点C所指链表也会存在一个指向A的表结点。
顶点表的各个结点由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("
邻接列表%d: ", v);
while (pCrawl) {
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("
");
}
}
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阶方阵:
- 对无向图而言,邻接矩阵一定是对称的,而且主对角线一定为零(在此仅讨论无向简单图),副对角线不一定为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("邻接矩阵:
");
for (int i = 0; i < MAX_NODES; i++) {
for (int j = 0; j < MAX_NODES; j++) {
printf("%d ", adj_matrix[i][j]);
}
printf("
");
}
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:表示边或弧的数目