数据结构中 关于图拓扑排序算法 有个地方不太明白 希望能得到解答
数据结构中 关于图拓扑排序算法 有个地方不太明白 希望能得到解答
我先把整个算法写下了吧
Status ToplogicalSort(ALGraph G){
//有向图G采用邻接表存储结构
//若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则ERROR.
FindInDegree(G,indegree); //对各顶点求入度indegree[0...vernum-1]
InitStack(S）；
for(i =0;inextarc){
k=p-->adjevex
if(!(--indegree[k])) Push(S,k）;//若入度减为0,则入栈
（终于码字码到这句了 我理解的是k是p指向的i的一个临界点,如果这个邻接点经过
--indegree入度减为0 则入栈 但是如果没减为0呢 --indegree[k]还要执行吗 我理解他是个条件啊 可是依照拓扑排序的思路 是要把i的邻接点入度都减1的）
}
}后面代码就不打了 主要是这一点 希望能解答下
我知道你哪里不明白了,你没看见上面的for循环,1,如果不为0,则不执行if了,但执行for循环.2,执行for循环的目的就是把所有的入度减1,减为0的入栈.为什么执行for循环就是把所有邻接点的入度减1 啊？能解释下for这句的意思吗for(p=G.vertices[i].firstarc;p;p=p-->nextarc){k=p-->adjevex（）里面表示什么意思？k不就是表示i的一个邻接点吗？怎么有入度减1的意思呢？？谢谢啦~for循环的意思就是说把所有的以G.vertices[i]为孤尾结点的，所有狐头指向的结点的入度减1，把度数减为0的入栈。G.vertices[i].firstarc的意思是：图G中以第i个顶点结点的狐尾结点的第一个孤所指向的结点。p=p-->nextarc是以第i个顶点结点的狐尾结点的下一个顶点结点。这是邻接表的定义嘛。k就是表示i的一个邻接点，但只是一个，要把所有的以第i个顶点结点的狐尾结点所指向的结点的入度都减1才行啊。