一楼忘掉呼喊度姐姐的名字真是失败……（蹲墙角）

图的表示法一般有两种：一种是邻接矩阵，一种是邻接链表。
邻接矩阵，顶点和顶点之间相连不相连这个就很简单处理，一个布尔就行了
邻接链表，顶点和顶点的相关联用链表表示。即谁和谁连，谁在以谁为第一项的链表里面。
图的遍历其实跟普通的一样，有深度搜索，有宽度搜索。
生成树：一个v个点的图，取其中v-1条边，并连接所有的定点，则组成原图的一个生成树。 特征：连通，无环。
最小生成树：连接所有点的最低成本路线即最小生成树。
局域网：
某局域网内有n（n<=100）台计算机，由于建网时工作人员的疏忽，现在网内存在回路，造成网络卡的现象。
我们用f(i,j)表示i,j之间连接的畅通程度（f(i,j)<1000），f(i,j)值越小表示i,j之间连接越通畅
讲了没听……大家上网自己查吧……

最小生成树的算法原理：环属性：一棵生成树上，增加一条边，在删除e所在环上的最大边，会得到另一棵更好的生成树（如果e不是最大）。
剪切属性：在图中，剪切将顶点划分成两个不相交集合。交叉边为地些顶点在两个不同集合的边。对于任何一个剪切，各条最小的交叉边都属于某个MST，且每个MST中都包含一条最小交叉边。
最小边原理：途中权值最小的边（如果唯一的话）一定在最小生成树上。
唯一性：一棵生成树上，如果各边的权都不相同，则最小生成树是唯一的，反之不然。

Prim算法
(1)将G剪切成两个集合A、B，A中只有一个点r
(2)取最小权的交叉边(x,y)，x∈A, y∈B
(3)将y加入A
(4)如果已经加了n-1条边，结束。否则，转 (3)
Kruskal算法
(1)将G所有条边按权从小到大排序；图mst开始为空
(2)从小到大次序取边(x,y)
(3)若加入边(x,y)，mst就有环，则放弃此边，转(2)
(4)将边(x,y)加入mst，如果已经加了n-1条边，结束。否则，转 (2)
本算法的要点在如何判断加入边（x,y）构成了环。可以化为判断xy是否相连，可用并查集进行查找。
对稀疏图一般用Kruskal算法。
平面上有K个水源（井），N个居民供水点，怎样用最少的管道使这N个居民点都能用连接到水源。注：边只能水源、居民点之间直接相连。
这个道题可以加一个虚节点，到各个水源的距离都为0，没有到其它点距离的，则使得个点之间连通。从而MST。