文章
28
粉丝
19
获赞
0
访问
1.4k
(1)用一个数组indegree[numVertices]记录每个顶点的入度,zero用于记录当前入度为0的节点号,初值为-1.,按以下思路进行算法:
1.遍历邻接矩阵的列填入indegree数组;
2.遍历indegree数组,找出indegree为0的索引号存入zero中,如果找到2个(即zero!=-1的情况下有indegree为0),则返回false;
3.否则遍历邻接矩阵中的第zero行找到与选中节点的邻接节点,将zero指向节点以及其邻接节点入度-1
4.若zero!=-1,重复过程2;否则返回true
(2)
int uniquely(MGraph G)
{
int indegree[MAXV] = {0};
//初始化indegree
for(int i = 0; i< G.numVertices; i++)
{
int deg = 0;
for(int j = 0; j< G.numVertices; j++)
{
if(G.Edges[j][i] > 0)
{
deg++;
}
}
indegree[i] = deg;
}
//开始拓扑
int zero = -1;
do
{
for(int i = 0;i < G.numVertices; i++)
{
if(indegree[i] == 0){
if(zero == -1)
zero = i;
else
//存在两种拓扑
return false
}
}
if(zero != -1)
{
for(int j = 0; j< G.numVertices; j++)
{
if(G.Edges[zero][j] > 0) indegree[j]--;
}
indegree[zero]--;
}
}while (zero != -1)
//遍历完毕,存在唯一拓扑
return true;
}
登录后发布评论
暂无评论,来抢沙发