V1 V2 V3 V4 V5 V6 V7 V8 V9 V10
V1 0 1 1 1 0 0 0 0 0 0
V2 0 0 0 1 1 0 0 0 0 0
V3 0 0 0 1 0 1 0 0 0 0
V4 0 0 0 0 0 1 1 0 1 0
V5 0 0 0 0 0 0 1 0 0 0
V6 0 0 0 0 0 0 0 1 1 0
V7 0 0 0 0 0 0 0 0 1 0
V8 0 0 0 0 0 0 0 0 0 1
V9 0 0 0 0 0 0 0 0 0 1
V10 0 0 0 0 0 0 0 0 0 0
当用邻接表作为图的存储结构,且邻接表都按序号从大到小排序时,试写出:
(1).以顶点V1为出发点的唯一的深度优先遍历;
(2).以顶点V1为出发点的唯一的广度优先遍历;
(3).该图唯一的拓扑有序序列。
先上图:
深度优先遍历顺序:v1 v2 v4 v6 v8 v10 v9 v7 v5 v3
广度优先遍历顺序:v1 v2 v3 v4 v5 v6 v7 v9 v8 v10
拓扑序列:v1 v2 v3 v4 v5 v6 v7 v8 v9 v10
不太明白您为什么要强调“唯一”,一个图的遍历顺序和拓扑序都有很多(真的很多)
我给的是字典序最小的
追问题目要求是用由大到小的邻接表作为存储结构时,所写出来的遍历和拓扑排序,这时,唯一的邻接表就对应着唯一的序列了。
你能画出由大到小的邻接表,再排序吗?
图没变,给你张舒服点的:
从大到小应该是这样:
深度优先遍历顺序:v1 v4 v9 v10 v7 v6 v8 v3 v2 v5
广度优先遍历顺序:v1 v4 v3 v2 v9 v7 v6 v5 v10 v8
拓扑序列:v1 v3 v2 v5 v4 v7 v6 v9 v8 v10