- 线性表是一对一，树是一对多，图是多对多的关系。
- 图中的数据元素我们称为顶点（相对于树中的结点），顶点集合不能为空，边集合可以为空。
- 无向图——只要图中有一条边是无向边（A,B）。
- 有向图——任意两顶点之间的边都是有向边（弧）<A,B>。
- 无向完全图——n个顶点中任意两顶点之间都存在边的无向图。边的总数是n*(n-1)/2。
- 有向完全图——n个顶点中任意两顶点之间都存在方向相反的有向边的有向图。边的总数是n*(n-1)。
- 权——与图的边相关的数字。这些权可以表示从一个顶点到另一个顶点的距离或耗费。
- 网——带权的图。如网络图中，各条边就是链路，链路都是有带权（距离或带宽）的。
- 子图——G=(V,{E})，G'=(V',{E'})，其中V'是V的子集，E'是E的子集，则称G'是G的子图(subgraph)。
- 顶点v的度degree——是和顶点v相连接的边的数目。对于有向图的顶点的度还分为出度和入度。
- 邻接点——同一条边的两个点互为邻接点。
- 路径——指从一个顶点到另一个顶点所经过的顶点的序列。树的路径唯一，但图的路径不唯一，所以有很多求最短路径的算法。在网络图中，路径又叫路由。
- 路径的长度——路径上的边或弧的数目。
- 回路或环——第一个顶点和最后一个顶点相同的路径。
- 简单路径——路径序列中没有重复出现的顶点。
- 简单回路——除了第一个和最后一个顶点相同外，其余的顶点都不相同。
- 连通图（connected graph）——无向图中任意两个顶点都有路径（即都是连通的）。
- 非连通图——存在两个顶点之间没有路径，即不连通。有n个顶点，但只有小于n-1条边，一定是非连通图。
- 连通分量——无向图中的极大连通子图。连通图本身即是，而非连通图中最大的连通子图即是。
- 强连通图——有向图中，任意两个顶点都存在双向连通的路径。有向图的非强连通图，对应有强连通分量。
- 生成树——一个连通图的极小连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边（即去掉了环路）。不过n个顶点有n-1条边并不一定是生成树，比如一个非连通图中有一部分是个环路。因此生成树的前提一定是连通图。
- 有向树——一个有向图恰有一个顶点的入度为0（根结点），其余顶点的入度均为1。
- 生成森林——一个有向图的所有顶点，被分成若干颗不相交的有向树，这些有向树就组成了有向森林。
图的存储结构
- 因为顶点间多对多的关系，所以不能用简单的顺序结构数组来表示。
- 因为各个顶点的度不一致，所以不能用数据域+若干指针域的多重链表形式来表示，否则将造成很大的浪费。
- 图的存储结构有5种特别的。
1、邻接矩阵——重点关注顶点
2、邻接表——对邻接矩阵空间浪费的改进，重点关注顶点
3、十字链表——对有向图的邻接表进行改进，重点关注顶点
- 将展示出度的邻接表和展示入度的逆邻接表整合在一起。
4、邻接多重表——对无向图的邻接表进行改进，重点关注边
- 更关注边的操作，仿照十字链表。
- 邻接多重表与邻接表的差别：同一条边，在邻接表中要用两个结点表示，因此不便于删除一条边。然而在邻接多重表中，每个节点表示一条边，要删除边很简单。
5、边集数组——重点关注边，特别是与边的权值有关的最小生成树问题
图的遍历方式
1、深度优先搜索遍历DFS——类似于树的先序遍历，使用递归
2、广度优先搜索遍历BFS——类似于树的层序遍历，使用队列
总结分析两种遍历方式
寻找最小生成树——最小代价生成树
以最小的成本完成任务？
在一个带权值的图中，即网中，n个顶点找到n-1条边将他们连起来成为连通图，并且各边的权值总和最小，即为成本（代价）最小。类似的问题就是最小生成树问题。
网友评论