题目内容
（请给出正确答案）
设有向图G有n个点(用1，2，…，n表示)，e条边，写一算法根据G的邻接表生成G的反向邻接表，要求算法时间复杂性为O(n+e)。【东南大学1996三(13分)1992六(18分)】【北京邮电大学2006五、3(10分)】
如果结果不匹配，请 联系老师 获取答案
更多“设有向图G有n个点（用1，2，…，n表示)，e条边，写一算法…”相关的问题
问题描述:给定有向图G=(V,E).设P是G的一个简单路(顶点不相交)的集合.如果V中每个顶点恰好在P的条路上,则称P是G的一个路径覆盖.P中路径可以从V的任何一个项点开始,长度也是任意的,特别地,可以为0.G的最小路径覆盖是G的所含路径条数最少的路径覆盖.
设计一个有效算法求一个有向无环图G的最小路径覆盖.
[设V={1,2,...,n},如下构造网络G1=(V1,E1):
每条边的容量均为1.求网络G1的(x0,y0)最大流.]
算法设计:对于给定的有向无环图G,找出G的一个最小路径覆盖.
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和m.n是给定有向无环图G的顶点数,m是G的边数.接下来的m行,每行有2个正整数i和j,表示一条有向边(i,j).
结果输出:将最小路径覆盖输出到文件output.txt.从第1行开始,每行输出一条路径.文件的最后一行是最少路径数.
设图G是n阶无向简单图，其中n是偶数，若图G中有k个奇数度点，问：在其补图
假定图G=(V，E)是有向图，V={1，2，…，N}，N≥1，G以邻接矩阵方式存储，G的邻接矩阵为A，即A是一个二维数组，如果i到j有边，则A[i，j]=1，否则A[i，j]=0，请给出一个算法思想，该算法能判断G是否是非循环图(即G中是否存在回路)，要求算法的时间复杂性为O(n×n)。
对n个顶点的无向图G，采用邻接矩阵表示，判别下列有关问题： (1)图中有多少条边？ (2)任意两个顶点Vi和Vj是否有边相连？ (3)任意一个顶点的度是多少？
对n个顶点的无向图G，采用邻接矩阵表示，判别下列有关问题：
(1)图中有多少条边？
(2)任意两个顶点Vi和Vj是否有边相连？
(3)任意一个顶点的度是多少？
A、O(n)
B、O(n+e)
C、O(n2)
D、O(n×e)
在简单无向图中，如果每个顶点的度数都为是，则称此图为k—正则图。现设图G是有向图，其n个顶点分别为v1，v2，…，vn，如果图G的底图是3—正则图，且图G是强连通图。证明图G中各顶点出度的立方之和等于各顶点入度的立方之和。
