图论 图：点用线连接起来 有向图：边有方向 无向图：边无方向 结点的度：无向图中与结点相连的边的数目，称为结点的度。 结点的入度：在有向图中，以这个结点为终点的有向边的数目。 结点的出度：在有向图中，以这个结点为起点的有向边的数目。 权值：边的“费用”，可以形象地理解为边的长度。 连通：如果图中结点U，V之间存在一条从U通过若干条边、点到达V的通路，则称U、V 是连通的。 回路：起点和终点相同的路径，称为回路，或“环”。 完全图：一个n 阶的完全无向图含有n*(n-1)/2 条边；一个n 阶的完全有向图含有n*(n-1)条边； 稠密图：一个边数接近完全图的图。 稀疏图：一个边数远远少于完全图的图。 强连通分量：有向图中任意两点都连通的最大子图。 储存方法：二维数组a[i][j].(储存节点与权值) 图的邻接表存储法： struct Edge { int next; //下一条边的编号 int to; //这条边到达的点 int dis; //这条边的长度 }edge[maxm]; 图的遍历：深度优先；广度优先；（标记已查） 最短路径：Floyed-Warshall算法 O(N3) For (k = 1; k <= n; k++)（遍历节/起点） For (i = 1; i <= n; i++)（遍历终点） For (j = 1; j <= n; j++)（松弛） If (dis[i][j] >dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j]; 算法结束：dis[i][j]得出的就是从i到j的最短路径。 Floyed算法的变形： For (k = 1; k <= n; k++) For (i = 1; i <= n; i++) For (j = 1; j <= n; j++) dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]); 用这个办法可以判断一张图中的两点是否相连。 Dijkstra算法O (N2) 设起点为s，dis[v]表示从s到v的最短路径，pre[v]为v的前驱节点，用来输出路径。 a)初始化：dis[v]=∞(v≠s); dis[s]=0; pre[s]=0; b)For (i = 1; i <= n ; i++) 1.在没有被访问过的点中找一个顶点u使得dis[u]是最小的。 2.u标记为已确定最短路径 3.For 与u相连的每个未确定最短路径的顶点v if (dis[u]+w[u][v] < dis[v]) （贪心） { dis[v] = dis[u] + w[u][v]; pre[v] = u; } c)算法结束：dis[v]为s到v的最短距离；pre[v]为v的前驱节点，用来输出路径。 当时学的时候感觉有点迷糊，回来以后发现并没有这么难，这两天代码打的有点郁闷，char与string类型的数据老是处理不好，想用set 又嫌遍历太麻烦，有时候条件判断用多了出现了bug,感觉出现在条件上，但又不知道什么错，最后只好换思路，不甘心啊，还是知识掌握不够深入，最近看了本书，感觉学到了很多常用处理的简单实现，感觉还是挺有用的。
