7/10
今天凉爽，感觉秋天不远了，开学也不远了。今天的课程是图论V点E边，路指顶点序列，网络是图的所有边都具有权值。图的存储方法：邻接矩阵和关联矩阵。重点讲了邻接矩阵，这里我先说关联矩阵。Aij表示Vi与ej的关联次数Case vi是ej的始点 aij=1Case vi是ej的终点 aij=-1Case 不关联 aij=0下面介绍邻接矩阵一般图 case i=j aij=0 case i!=j (i,j)属于E aij=1 (i,j)不属于E aij=0网络图 case i=j aij=0 case i!=j (i,j)属于E aij=w(i,j) (i,j)不属于E aij=inf接下来讲了最短路问题若从图中的某一点到达另一点的路径不止一条，如何寻找一条路径，使得沿此路径各个边上的权值总和最小，这条路就是最短路。输入邻接矩阵输出d ，di表示由源点到第i个点的最短路径，index2为顶点索引，许峰说可以用2行代码改进index2。课间和同学一起讨论了C的一个实现方法，回来后自己实现了MATLAB的写法。（cleari=input('请输入到第i个点：');a=;%等待排序的路径b=a(i);while b~=1disp(b)c=a(b);disp(c)b=a(c);enddisp(1)%倒序得出路径）接下来讲了最小生成树，不包含圈的连通圈称为树，包含图所有点的极小连接子图称为G的生成树。可行遍历，中国邮递员遍历边，旅行商问题遍历点。网络流＾>都为前向，最大流等于最小割的容量。下午上机调试了最短路的Dijkstra和Floyd算法。最小生成树的Kruskal和Prim算法。图论最大流的Flod_Fulkerson和Dinic算法，最大流最小费用的Busacker_Gowan迭代法。Euler环游（遍历边）的Fleury算法，Tsp（遍历点）的改良圈算法。明天放假一天。
页:
[1]