Python Graph 图表 数据结构

Question

基本概念

• 无向图、有向图、加权图、加权有向图
• 边（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