简单图论问题探讨

找无环有向图的直径

重复插入：

　　任取一条路径（长度为ｎ），然后在ｎ+1个插入点上扩展新的点进入路径。

找无环有向图的最长直径：

无环图，

则一个点能够到达的点（子节点）不能够回到这个点（即没有环），

那么存在源点和终点，前者没有点能够到达它，后者不到达任何点。（不然这个图会无限的上下伸缩下去）。

可以有多个源头和终点，一个点可以对应多个父节点（乃至多个源），对应多个子节点（乃至多个终点）。

两种解法：

１　拓扑排序（特殊宽搜：把一个点的所有父节点都访问完以后，该点入度已经为０，再访问这个点） O(n)复杂度

　　其中，ＤＰ求最长路径：　ｍａｘＬｅｎ(v) =  max { maxLen( father_of(v) ) } = maxLen(last_visited_father_of(v) ) 。

２　循环松弛宽搜 （spfa）

 while(!que.empty()){
       v=que.front(); 
       que.pop(), vis[v] = false; //visit v
       for u=son_of(v): 
           if(len[u]<len[v]+1){  //找到一个可以被更新的子节点
                len[u]=len[v]+1;
                if(!vis[u]){ 
                    que.push(u), vis[u] = true;
                }
           }
    }

3   DP (借用floyd思路）？？？？

repUp(i, 1, N)
   repUp(j, 1, N)
         ？？？　max( dis[j], dis[i]+1 if map[i][j] )

４　重复dfs

　　每次重复访问到一个点v，发现它的当前的ｍａｘＬｅｎ比上次的大（ｍａｘｌｅｎ初始时设置为　最小　０），那么就ｄｆｓ(v). 否则直接返回。

　　这个时间代价太高。

dfs(pa, v){
           if(pa>=0){
               if(len[v]>len[pa]+1) return;
               len[v]=len[pa]+1;
          }
          for u=son_of (v): 
              dfs(v,u)
        }

 找无环图的s->t最长路长度

1 无向无环图： 树中两点路径，以s或t的一点为根，找到另一点的路径。

2 有向无环图： 记忆化搜索（白皮书163页）， spfa。