请编写程序,实现并测试邻接表表示的图的以下基本操作:
- 返回图中顶点的第一个邻接顶点
- 判断边是否存在
- 向图中插入边
- 从图中删除顶点及所有邻接于该顶点的边
输入格式:
输入首先在第一行给出图中最大顶点数量,即正整数 kMaxVertex
(≤10)。
第二行给出两个正整数,依次为当前要创建的图的顶点数 n 和边数 m(保证顶点数至少为 1 且不超过最大顶点数量)。
第三行给出 n 个英文字母,顺序对应每个顶点的信息。
随后 m 行,每行给出一条有向边的起点编号、终点编号、权重。顶点编号从 0 开始,权重(≤230)为整数。
结束了图的信息之后,接下来 2 行,每行给出一条待检查的有向边的起点编号、终点编号,用于检查边的存在性。
接下来给出一个顶点编号,用于检查该顶点的第一个邻接点。
最后给出待删除顶点的编号。
同行数字、字符均以一个空格分隔。
输出格式:
参考样例。
首先第一行输出 邻接表为:
。随后 n 行,顺序输出邻接表每个链表的状态,格式为:
list[i]->v:w->...->end
其中 i
是顶点编号,从 0 开始;v
是 i
的邻接点编号;w
是有向边 <i, v>
的权重;链表末尾用 end
表示。
完成了邻接表输出后,下一行输出 顶点数 = x
,其中 x
是图中顶点数。
对于待检查的两条有向边,按格式 <u, v> 的存在性 = x
输出其存在性检查结果,其中 u
为边的起点编号,v
为边的终点编号,x
为 0 表示不存在,为 1 表示存在。
对于下一个给出的顶点,按格式 顶点x的第一个邻接点 = y
输出第一个邻接点的检查结果,其中 x
为给定顶点编号,y
为其第一个邻接点的编号。注意:邻接表中的邻接点按输入逆序存储,即第一个邻接点是最后一个读入的邻接点。
对于最后要删除的顶点,首先按格式 待删除的顶点信息为 x
输出该顶点的信息字符 x
,随后将其从图中删除。
最后输出结果邻接表的信息,格式为:
在一行中输出 当前顶点数 = x
,其中 x
为图中顶点数;
在一行中输出 当前边数 = y
,其中 y
为图中边数;
在一行中顺序输出每个顶点的信息,中间没有空格;
在一行中输出 邻接表为:
;
按照输出初始邻接表的相同格式输出结果图的邻接表。
输入样例:
10
5 7
a b c d e
0 2 1
2 0 2
2 3 1
3 0 3
3 4 4
2 4 2
4 0 5
1 3
3 4
2
2
输出样例:
邻接表为:
list[0]->2:1->end
list[1]->end
list[2]->4:2->3:1->0:2->end
list[3]->4:4->0:3->end
list[4]->0:5->end
顶点数 = 5
<1, 3> 的存在性 = 0
<3, 4> 的存在性 = 1
顶点2的第一个邻接点 = 4
待删除的顶点信息为 c
当前顶点数 = 4
当前边数 = 3
abed
邻接表为:
list[0]->end
list[1]->end
list[2]->0:5->end
list[3]->2:4->0:3->end