太仓市住房和城乡建设局规网站,网站建设 考核指标,做购物网站是怎么链接银行,教育 wordpress模板下载地址个人主页#xff1a;【#x1f60a;个人主页】 系列专栏#xff1a;【❤️数据结构与算法】 学习名言#xff1a;天子重英豪#xff0c;文章教儿曹。万般皆下品#xff0c;惟有读书高——《神童诗劝学》 系列文章目录
第一章 ❤️ 学前知识 第二章 ❤️ 单向链表 第三章… 个人主页【个人主页】 系列专栏【❤️数据结构与算法】 学习名言天子重英豪文章教儿曹。万般皆下品惟有读书高——《神童诗劝学》 系列文章目录
第一章 ❤️ 学前知识 第二章 ❤️ 单向链表 第三章 ❤️ 递归 … 文章目录 系列文章目录前言什么是图图的分类图按照无方向和有方向分为无向图和有向图。图按照边分为稀疏图和稠密图完全图网 顶点与边顶点与边的关系 图的存储结构邻接列表邻接矩阵 图的定义和术语总结 前言 与线性表中的元素是“一对一”的关系和树中的元素是“一对多”的关系不同的是数据结构中图的元素则是“多对多”的关系。图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(\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阶方阵: 对无向图而言邻接矩阵一定是对称的而且主对角线一定为零(在此仅讨论无向简单图)副对角线不一定为0有向图则不一定如此。在无向图中任一顶点i的度为第i列(或第i行)所有非零元素的个数在有向图中顶点i的出度为第i行所有非零元素的个数而入度为第i列所有非零元素的个数。用邻接矩阵法表示图共需要n^2个空间由于无向图的邻接矩阵一定具有对称关系所以扣除对角线为零外仅需要存储上三角形或下三角形的数据即可因此仅需要n(n-1)/2个空间 #include stdio.h#define MAX_NODES 100int 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的一条弧 弧尾Tailv为弧尾或初始点Initial node 弧头Headw为弧头或终端点Terminal node 有向图Digraph图中每条边都有方向 无向图Undigraph图中每条边都没有方向 连通图Connected Graph对于图中任意两个顶点vj∈Vv和j都是连通的则称G是连通图 连通分量Connected Compenent无向图中的极大连通子图 完全图Completed graph有1/2*nn-1条边的无向图称为完全图 有向完全图具有nn-1条弧的有向图称为有向完全图 稀疏图Sparse graph有很少条边或弧如e nlogn的图称为稀疏图 稠密图Dense graph有很多条边或弧 权Weight有时图的边或弧具有与它相关的数这种与图的边或弧相关的数叫做权 度Degree定点v的度是和v相关联的边的数目记为TDV 入度InDegree以顶点v为头的弧的数目称为v的入度记为IDv 出度Outdegree以v为尾的弧的数目成为v的出度记为ODv V 是顶点的有穷非空集合 VR是两个顶点之间的关系的集合 n表示图中顶点数目 e表示边或弧的数目
