Kahn链路预测算法.pdfVIP

Kahn链路预测算法

算法步骤

遍历所有图顶点,把入度为0的顶点入队

当队列不为空时,取出一个顶点v输出

将与v相邻的顶点入度减1,然后把减1后入度为0的顶点入

队

重复2,3步,直到队列为空,算法结束

代码实现

#includeiostream

#includealgorithm

#includecstdlib

usingnamespacestd;

constintMaxV=100;

/*定义队列*/

typedefstructQNode{

int*Data;

intFront,Rear;

intMaxSize;

}*Queue;

/*定义边*/

typedefstructENode{

intv1,v2;

intWeight;

}*Edge;

/*定义邻接结点*/

structAdjVNode{

intAdjV;

intWeight;

AdjVNode*Next;

};

/*定义邻接表头*/

typedefstructVNode{

AdjVNode*EdgeFirst;

//booltag;//标记是否被访问,该题不需要此标记,入度

为0后,邻接表就不会在访问它了

intIndegree;//该结点的入度数

}AdjList[MaxV];

/*定义图*/

typedefstructGNode{

intNv,Ne;

AdjListL;

}*LGraph;

/*创建队列并初始化*/

QueueCreateQueue(intMaxSize)//给定队列最大长度

{

QueueQ=(Queue)calloc(1,sizeof(QNode));

Q-Data=(int*)calloc(MaxSize,sizeof(int));

Q-MaxSize=MaxSize;

returnQ;

}

/*入队操作*/

voidAddQ(QueueQ,intx)

{

Q-Rear=(Q-Rear+1)%Q-MaxSize;

Q-Data[Q-Rear]=x;

}

/*出队操作*/

intDeleteQ(QueueQ)

{

Q-Front=(Q-Front+1)%Q-MaxSize;

returnQ-Data[Q-Front];

}

/*

队列空:Q-Front==Q-Rear;

队列满:(Q-Rear+1)%Q-MaxSize==Q-Front;

*/

/*创造有Nv各结点的无边图*/

LGraphCreateGraph(intNv)

{

LGraphG=(LGraph)calloc(1,sizeof(GNode));

G-Nv=Nv;

returnG;

}

/*给图插入边*/

voidInsertEdge(LGraphG,EdgeE)

{

AdjVNode*A=(AdjVNode*)malloc(sizeof(AdjVNode));

A-AdjV=E-v2;

A-Next=G-L[E-v1].EdgeFirst;

G-L[E-v1].EdgeFirst=A;

}

/*创建图表*/

LGraphBuildGraph()

{

intNv;cinNv;

LGraphG=CreateGraph(Nv);

cinG-Ne;

EdgeE=(Edge)malloc(sizeof(ENode));

for(inti=0;iG-Ne;i++)

{

cinE-v1E-v2;

InsertEdge(G,E);

G-L[E-v2].Indegree++;//计算入度

}

free(E);

returnG;