| |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
-> 数据结构与算法 -> 《黑马程序员》— 图的入门 -> 正文阅读 |
|
[数据结构与算法]《黑马程序员》— 图的入门 |
目录 图的定义
图是由一组顶点和一组能够将两个顶点相连的边组成的。
?特殊图: 图可以分为无向图和有向图。有向图就是连接是有方向的。 图的相关术语
度: 某个顶点的度就是依附于该顶点的边的个数
环: 是一条至少含有一条边且终点和起点相同的路径
连通图: 如果图中任意一个顶点都存在一条路径到达另外一个顶点
? 图的存储结构
要表示一幅图,只需要表示清楚以下两部分内容即可:
1.
图中所有的顶点;
2.
所有连接顶点的边;
常见的图的存储结构有两种:邻接矩阵和邻接表
?邻接矩阵
1.
使用一个
V*V
的二维数组
int[V][V] adj,
把索引的值看做是顶点;
2.
如果顶点
v
和顶点
w
相连,我们只需要将
adj[v][w]
和
adj[w][v]
的值设置为
1,
否则设置为
0
即可。
矩阵的横纵坐标代表了顶点,中间的元素值代表是否连接。 缺点:内存占用空间较大 邻接表
1.
使用一个大小为
V
的数组
Queue[V] adj
,把索引看做是顶点;
2.
每个索引处
adj[v]
存储了一个队列,该队列中存储的是所有与该顶点相邻的其他顶点。
无向图的实现?无向图的构建:
?图的搜索深度优先搜索(DFS)先找子结点,再找兄弟结点。 ?(搜索过的点不用再搜索)
广度优先搜索(BFS)先找兄弟结点,再找子结点。 (搜索过的点不用再搜索) 层序遍历其实就是广度优先搜索。
? |
|
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 | -2024/11/25 17:28:40- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |