文章
15
粉丝
0
获赞
6
访问
860
(1) 首先由题意可得,G一定是一个AOV网,因此一定有拓扑序列;若G中某个顶点的入度或出度>1,那么G中就不存在唯一的拓扑序列,又因为G是用邻接矩阵存储的,故可以检查每个顶点的入度与出度,若某个值大于1,则返回0;全部检查完也没有找到入度与出度大于1的,则返回1。时间复杂度为O(|V|^2)与空间复杂度为O(1)。
(2)
// 算法主体
int solution(MGraph G) {
// 遍历每个顶点,以获取其入度与出度
for (int i = 0; i < G.numVertices; i++) {
int inDegree = 0, outDegree = 0; // 顶点i的入度与出度
for (int j = 0; j < G.numVertices; j++) {
if (G.Edge[j][i] == 1) { // j到i有一条有向边,入度+1
inDegree++;
if (inDegree > 1) // 如果入度 > 1,则返回0
return 0;
}
if (G.Edge[i][j] == 1) { // i到j有...
登录后发布评论
暂无评论,来抢沙发