电子商务网站建设与管理期末考试试卷a,管理咨询和战略咨询,南京seo培训,视频编辑sdk1.图论基础概念
概念
#xff08;注意连通非连通情况#xff0c;1节点#xff09; 无向图#xff1a; 度是边的两倍#xff08;没有入度和出度的概念#xff09; 1.完全图#xff1a; 假设一个图有n个节点#xff0c;那么任意两个节点都有边则为完全图 2.连通图注意连通非连通情况1节点 无向图 度是边的两倍没有入度和出度的概念 1.完全图 假设一个图有n个节点那么任意两个节点都有边则为完全图 2.连通图是指任意两个结点之间都有一个路径相连。 3.区别 n个顶点的完全图有n(n-1)/2条边而连通图则不一定但至少有n-1条边。举个例子四个顶点的完全图有6条边也就是四条边加上2条对角线而连通图可以只包含周围四条边就可以了。 4.强连通图 你到我有路径我到你有路径——最少边数为n环至多边数为n(n-1) 有向图G中如果两个顶点vi,vj间vivj有一条从vi到vj的有向路径同时还有一条从vj到vi的有向路径则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通称G是一个强连通图。 5.连通分量
子图相通子图极大 与连通图对应一般书上说的都是特指无向图 首先要知道分量分量其实就是子图只不过说的高大尚罢了。但连通分量不是简单的子图连通他还除了要求子图连通还要求该连通子图极大。说白了无向图极大连通子图就是连通分量。到这里先往下看极大连通子图再回来看
6.极大连通分量 从5我们知道他首先是连通子图并且该连通子图是极大的主要是这里的极大很不好理解。这里我画图举例 7.极小连通分量 7.生成树 连通图的生成树是包含图中全部顶点的一个极小连通子图。 8.生成森林 9.有向树 一个顶点的入度为0其余顶点入度为1的有向图为有向树
例题
1. 2. 答案选B 无向图是没有方向的而强连通图 强调的是有方向的图 而有回路也不一定正确可能会出现以下情况访问不到其余节点 而一棵树只有从根节点出发才能访问所有节点 3. 1.子图的概念 **子图**假设有两个图GV,{E}和gv,{e},如果v⊆Ve⊆E则称g为G的子图 例假设有图GV,{E}顶点集A⊆VB⊆E则A和{B}构成G的子图。答错误因为A和B未必能构成图。定义中g是G的子图是因为给条件时已经明确g是图2.无向完全图和有向完全图的概念 无向完全图每个节点之间都有边为1/2n(n-1); 有向完全图任意两个顶点之间都存在方向相反的两条弧。n(n-1); 3. 强连通图的概念 有方向有边但是强连通图不能保证任何顶点到其他所有顶点都有弧可能只与其中之一之间有弧 图的入度和出度 图的入度和出度不一定相等入读可能为0 有向完全图 有边且方向为双向边数为n(n-1)故有向完全图一定为强连通图 有边有方向 有向图边集的子集和顶点的子集不一定能够构成子图除非明确给出这个子集构成了个图
5. 注意非连通的情况 6. 对于强连通有向图成一个环三个节点三条边 你到我有路径我到你有路径——最少边数为n环至多边数为n(n-1) 7. 8. n个顶点最多n-1条边算入度出度2*n-1 10. 在五个顶点的完全图基础之上再加一个顶点使其为连通图 11. 可以知道的是树一定是一个连通图——所以符合n个节点n-1条边
生成树指的是最小连通子树而连通分量指的是极大连通子树生成树确实是无环的生成树与最下连通子树相关 12. n个顶点成为一个环有n个边n个边有n颗生成树也可以从度方面思考 13. 设森林中有s棵树再用n-1条边就能把所有的树连接成一棵树此时边数1顶点数即e(x-1)1n xn-e 14. 在有向图中顶点的度为入度与出度之和。n个顶点的有向图中任一顶点最多还可以与其他n—1个顶点有一对边相连。 2n-1*
15. 若图为环则度最少为2 16. 与上述类似一个无向图若要有七个节点要保证它是连通的说明六个节点的时候是完全图所以边数为6*(5)/2但因为要将其变为连通图所以需要1条边
17.邻接矩阵 非对称的邻接矩阵说明为有向图因为无向图一定是对称的各顶点的度依次是入度出度为3423 如果是无向图就要/2 2.图的存储
邻接矩阵
无向图的邻接矩阵是唯一的邻接表是唯一的
邻接表
**前提**因为邻接矩阵较为稀疏所以我们用邻接表法减少空间的消耗 有向图无向图都能够存储 邻接表存储有向图时顶点的出度个数为单链表中的节点个数 无向图中邻接表不唯一若无向图中有n个顶点、e条边则其邻接表需要n个头结点和2e个表结点。适宜存储稀疏图。 无向图和有向图存储空间的比较 **无向图**顶点数2*边数**有向图**定点数边数
图的遍历
深度优先DFS 从上至下遍历如果到顶了已经走过的路就不走了就返回上一步节点
广度优先BFS 从左到右一层一层遍历放入找当前节点距离为1的节点们放入然后继续遍历 邻接矩阵的遍历 注意遍历的唯一性
例题
