下列关于图的叙述中，正确的是（）。

[单选题]

下列关于图的叙述中，正确的是（）。
Ⅰ．回路是简单路径
Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间
Ⅲ．若有向图中存在拓扑序列，则该图不存在回路

```
仅Ⅱ
```
```
仅Ⅰ、 Ⅱ
```
```
仅Ⅲ
```
```
仅Ⅰ、 Ⅲ
```

查看答案及解析

推荐

爱豆儿

I：几个概念描述如下：

回路：第一个顶点和最后一个顶点相同的路径称为回路（环）。

简单路径：在一条路径中，若没有重复相同的顶点，该路径称为简单路径。

简单回路：在一个回路中，除了第一个与最后一个顶点外，其余顶点不重复出现的回路称为简单回路（简单环）。

回路对应于路径，简单回路对应于简单路径。

II：存储稀疏图时，使用邻接表比邻接矩阵更剩空间。

III:若有向图中存在拓扑序列，则说明该图不存在回路。

通过以上分析可知，只有III的描述是正确的。

编辑于 2017-07-12 15:23:56 回复(0)

福娃

1. 简单回路:在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的回路称为简单回路(简单环)。按理说第一个应该对。可能是这个回路没有考虑正确吧，除了第一个和最后一个顶点外，中间如果出现重复的话，就不是简单回路。例如这个由a-b-d-e-g-f-d-c-a组成的回路，就不是简单回路了。

2. 邻接表只存储了有数据的节点，因此相比邻接矩阵更节省空间。

3.有向图的拓扑序列：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序（360百科），从定义可以看出不能存在回路。

发表于 2016-12-19 22:41:31 回复(0)