[Udacity CS 215] Algorithms (Week #3)

  
previously:
第二个unit  http://www.1point3acres.com/bbs/thread-37403-1-1.html
第一个unit  http://www.1point3acres.com/bbs/thread-37390-1-1.html


这章的标题是 Basic Graph Algorithms：

1. clustering coefficient
cluster coefficient是用来描述一个点的邻接点之间相互连接的程度。例如生活社交网络中，你的朋友之间相互认识的程度。
关于计算方法，可参考维基百科。讲义中老师用的是（针对无向图的） C(vi) = ( 2 * vi邻接点之间边的个数) / ( vi邻接点个数 * (vi邻接点个数-1) ) 这个公式。

2. Connected Components
如何计算图中连通分量：个人感觉有点像flood fill的思想，就是每次在未标记的点集中找一个点，把能连通的都标记了，直到未标记的点集为空。

3. single shortest path
此处针对的是边没有权重的图。在这种情况下，对于求单源最短路径只需BFS一下就可以了。 如果是边有权重的话，还是得用dijkstra吧。

4. Bridge Edges
如果一个图里去掉一条边，分成了两个不相连的子图，这条边叫做bridge edge。
老师重点讲了求解图中bridge的算法。 网上也有java源代码可以参考:
http://algs4.cs.princeton.edu/41undirected/Bridge.java.html

该算法是R.Tarjan发明的。对图深度优先搜索，定义DFS(u)为u在搜索树（以下简称为树）中被遍历到的次序号。定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点，即DFS序号最小的节点。根据定义，则有：

Low(u)=Min
{
DFS(u)
DFS(v) (u,v)为后向边(返祖边) 等价于 DFS(v)<DFS(u)且v不为u的父亲节点
Low(v) (u,v)为树枝边(父子边)
}

一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)<Low(v)。

编程作业题：

---

Centrality

Write centrality_max (function) to return the maximum distance from a node to all the other nodes it can reach

要求用非递归的方式。


Bridge Edges

Find the bridge edges in a graph given the algorithm in lecture.

这道题的难度为挑战级。



  

Lesson 3: