Question

逆邻接表c++实现

高手能指点一下逆邻接表求顶点入度的算法吗？有源码附注释也可以。
看了一些源码 脑子混乱了

Answer 1

楼上的你搞神马啊，那是我给别人回答问题的答案好吗？我勒个去你盗用我版权最少也加个出处吧？我囧。
我是真的OIer，不过我由于要出国，大半年没研究算法了，很多东西都忘干净了。
1楼正解，严格讲无向图没有逆邻接表，因为它存的是入度。倒是只有有向图才能拓扑排序这是真的，只有能拓扑排序才能建AOE网才能求关键路径这更是真的。。LZ想必研究算法也不肤浅了，膜拜一下OTZ。
我模糊的记得一点逆邻接表的操作，但是逆邻接表的拓扑排序是真的忘得一干二净了，好像之前也没写过的样子。首先既然是同一幅图，如果时空复杂度都允许，而且LZ会写邻接表的topo，为啥不把逆邻接表转化成邻接表。当然这是我个人YY，实际操作没操作过，LZ可以试试……成功了一定告诉我。。
下面我硬着头皮一边想一边答了。。对这部分记忆程度怎么样我自己都说不好。。要是问我个最短路径最小生成树什么的我还记得起来。。就像可恶的楼上盗我版权的最短路径答案。。噗噜噜。。气使我了。。
topo基本实现方法是先找一个入度 = 0，output，再删除这个点的所有出度。。这个LZ必然清楚我废话了。。
如果不考虑时间复杂度大可以全图遍历。。此方法暴力至极必然pass。。其实蛋疼的写到这我一直在想楼主你干嘛不建个邻接表啊？！楼上要是不盗我版权我也不至于硬着头皮来答问题。。
这已经过了40分钟了，我翻了自己的代码没找到，但是好像是发现了点有用的东西，总之多半自己也不认识了。。楼主听过什么逆拓扑排序mia？这刚好反过来，每次输出没有后继的那个结点。这样刚好是拓扑排序的逆序，来个栈或者直接不怕麻烦开个数组存一下就ok，写个栈也不过就10行以内。。简易只吃不吐的栈就三行搞定。。翻过来cout不就完了。然后之后楼主有想到神马木有。。遍历，找出度是0的结点，然后循环找，找到了就入栈并且删除他的入度，以此类推正好是反过来的。这样干脆直接在建图的时候多加一个域，存储的是各节点当前出度，到时候outdeg -- 完事~遍历一遍O(v)的复杂度，存出来，一目了然~~这个就跟正常的topsort木有大区别了啊，只是加了个栈，加了个域，顶多像我说的遍历一遍把域里的出度个数存出来，先把出度是0的找出来（我当回唐僧重复一遍。。。），然后找到他的所有入度，断绝关系并且把入度的出度数都减1，再遍历找0出度，再找他的入度，减出度数，这样一直循环下去。。。
我写到这一小时了。。我是回忆起来了。。不知道LZ有没有点概念？自己动手试试。。反正我当年是看人家代码必蒙。。看个变量名称就得累死。。好好个变量你就说出度吧。。outdegree缩写outdeg多简洁是吧，他非给你写个A数组，蛋疼，蛋疼。。
建议LZ照我的YY果断试一把，至于AOE网关键路径。。就不要问我了。。。。。我再把这个想起来今天不用睡了。。。6月4号还得考SAT。。LZ保重。。成功了告诉我。。
你不采纳你对不起我你。。。
PS 鄙视楼上。。。
再稍微补充一句，刚刚我一个关系很好的夜猫子学长上线了，他说这玩意数据结构的书里都有讲，LZ找一本看看吧。。并且此人朦胧状态下肯定了我的答案。。你一定要试试。。一定要试试。。
while(true)
printf("你不采纳你对不起我你。。。\n PS 鄙视楼上。。。");
时间久了连cout里能不能用\n当换行符都忘掉的少年飘过。。。LZ加油。。

追问

我的问题已经解决了 大部分书中有的只是算法和图解 小学生都能看懂好吧 我对在百度提问彻底失望了。。。。我囧 拜托不要说这么多废话好吧

Answer 2

>>全国交通咨询？
作为一个OIer、我表示对最短路径算法稍有研究。
Dijkstra和Floyd是按需要来看的
首先
dijkstra求的是从一个节点到其他节点的最短路 时间复杂度不优化的情况下是n方
Floyd求的是任意两点间的最短路径、时间复杂度永远是n的立方、而且我表示除了邻接矩阵我再没用其他数据结构写过。
所以在处理很多的结点很多边的时候、Floyd又耗费时间又浪费空间、没有特殊需要不要用。
至于dijkstra、在稀疏图里它一定比SPFA快
>>SPFA是另一种最短路算法、是Bellman-Ford的队列优化
但是对于稠密图、SPFA要比dijkstra快很多。
但是、dijkstra可以用堆优化
用小根堆来维护dijkstra中的dist数组、在每次取最小值的时候取堆顶元素
这样时间复杂度是nlogn级、很快
至于SPFA跟Heapdijkstra哪个快这个不大好比较= =、

OTZ回答的有点跑偏了。
注意最开始的那几行
我强烈推荐dijkstra、Floyd如果不求任意两点的最短路径的话根本没必要。

追问

我想用逆邻接表求顶点入度，实现拓扑排序，然后求关键路径，你的回答的确有点跑偏，让我不知所措。。。。