图的基本内容
图的基本术语
-
端点和邻接点
无向图:若存在一条边(i, j)中顶点i和顶点j为端点,它们互为邻接
点。有向图:若存在一条边<i, j>与顶点i为起始端点(简称为起点) ,
顶点j为终止端点(简称终点),它们互为邻接点。 -
顶点的度、入度和出度
无向图:以顶点i为端点的边数称为该顶点的度。
有向图:以顶点i为终点的入边的数目,称为该顶点的入度。以顶点i为始点的出边的数目,称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。
若一个图中有n个顶点和e条边,每个顶点的度为d, (0≤i≤n-1)
则有:
这里我们可以看出顶点度与边的关系 -
完全图
无向图:每两个顶点之间都存在着一条边,称为完全无向图,包含有n(n-1)/2条边。
有向图:每两个顶点之间都存在着方向相反的两条边,称为完全有向图,包含有n(n-1)条 边。 -
路径和路径长度
在一个图G=(V, E)中,从顶点i到顶点j的一条路径(i, i1, i2, ., im,j)。其中所有的(ix, iy,)∈E(G), 或者<ix,iy>∈E(G)
路径长度是指一条路径.上经过的边的数目。
若一条路径上除开始点和结束点可以相同外,其余顶点均不相同,则称此路径为简单路径。 -
连通、连通图和连通分量
无向图:若从顶点i到顶点j有路径,则称顶点i和j是连通的。
若图中任意两个顶点都连通,则称为连通图,否则称为非连通图。
无向图G中的极大连通子图称为G的连通分量。显然,任何连通图的连通分量只有一个,即本身,而非连通图有多个连通分量。 -
强连通图和强连通分量
有向图:若从顶点i到顶点j有路径,则称从顶点i到j是连通的。.
若图G中的任意两个顶点i和j都连通,即从顶点i到j和从顶点j到i都存在路径,则称图G是强连通图。可以看到强连通图是针对有向图而言的。
在一个非强连通中找强连通分量的方法。
①在图中找有向环。
②扩展该有向环:如果某个顶点到该环中任一-顶点有路径,并且该环中任一顶点到这个顶点也有路径,则加入这个顶点。 -
权和网
图中每一条边都可以附带有一一个对应的数值,这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。
边上带有权的图称为带权图,也称作网。
图的存储结构
图的两种主要存储结构:
- 邻接矩阵
- 邻接表
邻接矩阵
邻接矩阵的主要特点:
-
一个图的邻接矩阵表示是唯一的。
-
特别适合于稠密图的存储。
邻接矩阵演示:
那么我们如何从这些数据中判断该顶点的度呢?
很明显,无向图,邻接矩阵的第i行或第i列、非零元素的个数正好是顶点i的度;
有向图,邻接矩阵的第i行(第i列)非零元素的个数正好是顶点i的出度;对有向图来说,它也可能是对称矩阵,可以看到邻接矩阵的存储空间为O(n²),也就是说它适合对稠密图存储。
邻接表
-
对图中每个顶点i建立一一个单链表,将顶点i的所有邻接点链起来。
-
每个单链表.上添加一个表头节点(表示顶点信息)。并将所有表头节点构成一个数组,下标为i的元素表示顶点i的表头节点。
对有向图来说,它的邻接表创建是这样的:
可以看到
对无向图来说:即将顶点i的所以邻接点衔接在一起。邻接表中顶点i对应的第i个单链表的边结点数正好是顶点i的度
对有向图来说:即将出边的邻接点衔接在一起。邻接表中顶点i对应的第i个单链表的边结点数正好是顶点i的出度。顶点i的入度为邻接表中所有adjvex域值为i的边结点数。拿上图的结点2来说,它的入度为2。我们可以看到,邻接表存储空间为O(n+e),也就是说适合于稀疏图存储。
图的遍历
深度优先遍历(DFS)
深度优先遍历过程::
(1)从图中某个初始顶点v出发,首先访问初始顶点v。
(2)选择一个与顶点v相邻且没被访问过的顶点w,再从w出发进
行深度优先搜索,直到图中与当前顶点v邻接的所有顶点都被访问过为止。
算法设计思路:
- 深度优先遍历的过程体现出后进先出的特点:用栈或递归方式实现。
- 如何确定一个顶点是否访问过?设置一个visited[]全局数组,visited[]=0表示顶点i没有访问; visited[i]=1 表示顶点已经访问过。
算法:
该算法时间复杂度为O(n+e)
遍历过程:
可以看先访问2,然后找2的邻接点1,然后再找1的邻接点0,依次下去,直到所有结点都被访问完毕,最后按原路径回退到出发点。
广度优先遍历(BFS)
广度优先遍历过程::
(1)访问初始点v,接着访问v的所有未被访问过的邻接点v1,v2, .,. vt。
(2) 按照v1,v2, … vt的次序,访问每一个顶点的所有未被访问过的邻接点。
(3)依次类推,直到图中所有和初始点v有路径相通的顶点都被访问过为止。
算法设计思路:
- 广度优先搜索遍历体现先进先出的特点,用队列实现。
- 如何确定一个顶点是否访问过?设置一个visited[]全局数组,visited[]=0表示顶点i没有访问; visited[i]=1 表示顶点已经访问过。
算法:
该算法时间复杂度为O(n+e)
遍历过程:
可以看出,开始访问2,然后直接访问所有2的邻接点1,3,4。然后再依次由1找它的邻接点,2找它的邻接点,4找它的邻接点。
非连通图的遍历
-
无向连通图:调用一次DFS或BFS,能够访问到图中的所有顶点。
-
无向非连通图:调用一次DFS或BFS,只能访问到初始点所在连通分量中的所有顶点,不可能访问到其他连通分量中的顶点。
可以分别遍历每个连通分量,才能够访问到图中的所有顶点。非连通图:调用DFS()和BFS()的次数恰好等于连通分量的个数。