Python Graph 图表 数据结构
基本概念
- 无向图、有向图、加权图、加权有向图
- 边（edge）、顶点（vertex），自环、平行边
- 顶点的度数。子图。连通图
- 树是一个无环连通图，连通图的生成树是它的一幅子图，它含有图中所有的顶点且是一棵树
- 稀疏图、稠密图
无向图
首先要解决的问题就是使用什么样的数据结构来表示无向图，一种方式是使用邻接矩阵，即一个大小为v*v的矩阵，当i和j之间有边连接时，则Vij为true，这种方式带来的问题就是总是需要用V^2的空间大小来表示一张有V个顶点的图，当图过大时，开销就会很大。
一种比较好的方式是使用邻接表，即使用数组来表示。将顶点的编号 0，1，2… 作为数组的索引，数组中每个位置的元素存放一个链表，链表中存储了所有与该索引的顶点相连的顶点的索引，如图所示：
可以看出，使用这种方式，对于一幅图，可能有多种不同的邻接表来表示。对于一幅V个顶点和E条边的图，空间复杂度与V+E成正比，添加一条边的时间复杂度为常数，遍历一个顶点的所有边的时间复杂度与V的度数成正比。
参考
- 数据结构_浙江大学_中国大学 MOOC
- jwasham/coding-interview-university: A complete computer science study plan to become a software engineer.
- CS-Interview-Knowledge-Map/dataStruct-zh
- Python 数据结构与算法分析（第2版），人民邮电出版社
- 二叉树的后序遍历-非递归版本-四种方法python – CSDN
- B-树、B+ 树以及 B* 树的原理详解
- Tutorials – Using Tries
以上是 Python Graph 图表 数据结构 的全部内容， 来源链接： utcz.com/z/264575.html
