问答题
请回答下列关于图(Graph)的一些问题：(每题4分)
问答题
有n个顶点的有向强连通图最多有多少条边?最少有多少条边?
【正确答案】正确答案：n(n一1)，n
【答案解析】
问答题
表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?
【正确答案】正确答案：100，不一定是稀疏矩阵。
【答案解析】
问答题
对于一个有向图，不用拓扑排序，如何判断图中是否存在环?【清华大学2000一(12分)】
【正确答案】正确答案：使用深度优先遍历，按退出dfs过程的先后顺序记录下的顶点是逆向拓扑有序序列。若在执行dfs(v)未退出前，出现顶点u到v的回边，则说明存在包含顶点v和顶点u的环。
【答案解析】