第七章 图

在图结构中,结点间前驱和后继均可不唯一,即结点之间是多对多的关系

点集合中不能为空,边集合可以为空

图的存储结构:邻接矩阵、邻接表、十字链表及邻接多重表

图的遍历方法:广度优先搜索,深度优先搜索

稠密图:图中具有很多的边(普利姆算法)

稀疏图:图中具有很少的边(克鲁斯卡尔算法)

关键路径:拓扑排序

最短路径:迪杰斯特拉

最小生成树:prime算法,克鲁斯卡尔算法

深度优先搜索:按照深度方向搜索,类似于树的先根遍历(找邻点的邻点直到没有,再回溯)

广度优先搜索:按照广度方向搜索,类似于树的层次遍历(先找一个点的所有邻接点,同时访问,再继续同时访问下一个)

有向图:节点之间的边存在方向

无向图:节点之间的边不存在方向

一、dfs 

二、bfs

三、拓扑序列

 

1. 关于图的邻接矩阵,下列哪个结论是正确的?(B)

A.有向图的邻接矩阵总是不对称的

B.有向图的邻接矩阵可以是对称的,也可以是不对称的

C.无向图的邻接矩阵总是不对称的

D.无向图的邻接矩阵可以是不对称的,也可以是对称的

无向图的邻接矩阵一定是对称的;

有向图的邻接矩阵可以是对称的,也可以是不对称的

2. 下面给出的有向图中,各个顶点的入度和出度分别是:(A)

A.入度: 0, 2, 3, 1, 2; 出度: 3, 2, 1, 1, 1

B.入度: 3, 2, 1, 1, 1; 出度: 0, 2, 3, 1, 2

C.入度: 3, 4, 4, 2, 3; 出度: 3, 4, 4, 2, 3

D.入度: 0, 1, 2, 1, 1; 出度: 3, 2, 1, 1, 1

0 入度:0   出度:3

1 入度:2   出度:2

2 入度:3   出度:1

3 入度:1   出度:1

4 入度:2   出度:1

3. 设无向图为 G=(V,E),其中 V={v1,v2,v3,v4},E={(v1,v2),(v3,v4),(v4,v1),(v2,v3),(v1,v3)}。则相应的邻接矩阵为:(B)

A.

A.JPG

B.

B.JPG

C.

C.JPG

D.

D.JPG

因为为无向图,所以 v1<->v2;v3<->v4;v4<->v1;v2<->v3;v1<->v3; 

 

4. 在图中自d点开始进行深度优先遍历算法可能得到的结果为:(C)

A.d,a,c,f,e,b

B.d,a,e,b,c,f

C.d,e,a,c,f,b

D.d,f,c,e,a,b

d->e,d->f.排除A,B选项

d->f->c(c之后只能选择a,不能没有走完就突然回溯到d)

5. 下列选项中,不是下图深度优先搜索序列的是:(D)

A.V1​, V5​, V4​, V3​, V2​

B.V1​, V3​, V2​, V5​, V4​

C.V1​, V2​, V5​, V4​, V3​

D.V1​, V2​, V3​, V4​, V5​

D选项中,V2走不到V3

6. 在图中自c点开始进行广度优先遍历算法可能得到的结果为:(C)

A.c,a,b,e,f,d

B.c,a,f,d,e,b

C.c,f,a,d,e,b

D.c,f,a,b,d,e

c a f b d e

c f a d b e

c f a d e b

7. 任何一个带权无向连通图的最小生成树(C)

A.是唯一的

B.是不唯一的

C.有可能不唯一

D.有可能不存在

8.已知有向图G=(V, E),其中V = {v1, v2, v3, v4, v5, v6}E = {<v1,v2>, <v1,v4>, <v2,v6>, <v3,v1>, <v3,v4>, <v4,v5>, <v5,v2>, <v5,v6>}。G的拓扑序列是:(A)

A.v3, v1, v4, v5, v2, v6

B.v3, v4, v1, v5, v2, v6

C.v1, v3, v4, v5, v2, v6

D.v1, v4, v3, v5, v2, v6

先找入度为0的点,边删边,边找入度为0的点

9. 我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题?(A)

A.Dijkstra算法(从顶点v0出发到其余顶点的最短路径算法)

B.Kruskal算法(最小生成素)

C.深度优先搜索(图的遍历)

D.拓扑排序算法(关键路径)

10.数据结构中Dijkstra算法用来解决哪个问题?(B)

A.关键路径

B.最短路径

C.拓扑排序

D.字符串匹配

相关推荐

  1. 模板

    2023-12-23 16:08:04       15 阅读
  2. 模板

    2023-12-23 16:08:04       29 阅读
  3. 函数矩阵

    2023-12-23 16:08:04       29 阅读

最近更新

  1. TCP协议是安全的吗?

    2023-12-23 16:08:04       16 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2023-12-23 16:08:04       16 阅读
  3. 【Python教程】压缩PDF文件大小

    2023-12-23 16:08:04       15 阅读
  4. 通过文章id递归查询所有评论(xml)

    2023-12-23 16:08:04       18 阅读

热门阅读

  1. Python的内存管理与垃圾回收机制

    2023-12-23 16:08:04       39 阅读
  2. web服务以Jetty作为伺服器并以docker打镜像部署

    2023-12-23 16:08:04       36 阅读
  3. Hive的四种排序方法

    2023-12-23 16:08:04       37 阅读
  4. 第二百二十二回

    2023-12-23 16:08:04       41 阅读
  5. Spring Boot 定时任务实现

    2023-12-23 16:08:04       38 阅读
  6. 使用 Qt API 获取串口信息

    2023-12-23 16:08:04       39 阅读
  7. LeetCode347. Top K Frequent Elements

    2023-12-23 16:08:04       30 阅读