目录Python全系列 教程
3567个小节阅读：5930k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本，未来主流的版本
人工智能 教程
顺势而为，AI创新未来
大厂算法 教程
算法，程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
图(graph)是一种非线性数据结构，由顶点(vertex)和 边(edge) 组成
我们可以将图$G$抽象地表示为一组顶点$V$和一组边$E$的集合。以下示例展示了一个包含 5 个顶点和 7 条边的图
| 应用 | 顶点 | 边 | 图计算问题 |
|---|---|---|---|
| 社交网络 | 用户 | 好友关系 | 潜在好友推荐 |
| 地铁线路 | 站点 | 站点间的连通性 | 最短路线推荐 |
| 物流 | 仓库、交叉口 | 道路、路径 | 最短路径、最优路径规划 |
| 生物网络 | 蛋白质、基因 | 生物相互作用 | 生物网络模式、相互作用预测 |
| 推荐系统 | 用户、商品 | 用户行为、购买关系 | 个性化推荐、相似商品推荐 |
| 金融风险 | 公司、投资者 | 资金流动关系 | 风险评估、投资组合优化 |
根据边是否具有方向，可分为无向图(undirected graph)和有向图(directed graph)
根据所有顶点是否连通，可分为连通图(connected graph)和非连通图(disconnected graph)
还可以为边添加"权重"变量,从而得到有权图(weighted graph)。例如在"永劫无间"等游戏中，系统会根据共同游戏时间来计算玩家之间的"亲密度"，这种亲密度网络就可以用有权图来表示
图数据结构包含以下常用术语
图的常用表示方式包括"邻接(关联)矩阵"和"邻接表"
设图的顶点数量为 $n$ ，邻接矩阵(adjacency matrix) 使用一个 $n \times n$ 大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用 1 或 0 表示两个顶点之间是否存在边
设邻接矩阵为$M$、顶点列表为$V$，那么矩阵元素 $M[i,j]=1$表示顶点 $V[i]$ 到顶点 $V[j]$ 之间存在边，反之 $M[i,j]=0$ 表示两顶点之间无边
邻接矩阵具有以下特性:
提示
时间复杂度均为 $O(1)$ 空间复杂度$O(n^2)$
邻接表(adjacency list)使用$n$个链表来表示图，链表节点表示顶点。第$i$个链表对应顶点$i$，其中存储了该顶点的所有邻接顶点(与该顶点相连的顶点)
提示
邻接表仅存储实际存在的边，而边的总数通常远小于 $n^2$ ，因此它更加节省空间
而查找找又因是链表，所以效率不如邻接矩阵
实时效果反馈
1. 根据图的表示方式，选择下面哪个描述是正确的？
A 关联矩阵表示法中，矩阵元素$a[i,j]$的值表示从顶点 $i$ 到顶点 $j$ 有一条边
B 邻接表表示法中，每一行表示图中的一个顶点，列表示与该顶点相邻的所有顶点
C 关联矩阵表示法中，矩阵的行表示图的边，列表示图的顶点
D 无向图中，每条边都有方向，即从一个顶点指向另一个顶点
答案
1=>B
