概念
略。
是比树更一般的结构。可以考虑转化为树（半线性），再转化为线性结构。
存储
- 邻接矩阵：浪费空间，增删顶点慢，遍历邻居慢，但循秩访问使得其它静态操作快。
- 邻接表：省空间，对顶点操作快，遍历邻居快。
- 关联矩阵：略了。
图遍历
不仅仅能把图染一遍色，还顺带把边分成树边和跨边，画出一棵搜索树来。这里我在遍历过程中都略过了对边的分类。
为了便于后面玩，先画一棵丑丑的树，顶点给了个结构，边就直接表示在二维数组graph里了。以及一个把status重置的函数。
const int N = 8;
struct vertice{
int data;
int status;
int dTime;
int fTime;
}vertices[N];
int graph[N][N] = {{0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 1, 0}, {0, 0, 0, 0, 0, 1, 0, 0},
{0, 1, 0, 0, 0, 1, 0, 0}, {1, 0, 1, 1, 0, 0, 0, 0}};
void clearStatus(){
for(int i = 0; i < N; i ++){
vertices[i].status = 0;
}
}
BFS
首先访问到的就是进来的顶点。在搜索过程中会依次访问顶点的邻居、邻居的邻居，效果正是这棵搜索树的层次遍历。在实现上，也同样是拉出一个栈来。（我说学树的时候怎么觉得层次遍历越看越顺眼呢。）
这都是写过的东西了，再顺手写一遍啦：
void BFS(int v){
int queue[N], start = 0, end = 1;
queue[0] = v;
vertices[queue[0]].status = 1;
while(end > start){
v = queue[start ++];
for(int i = 0; i < N; i ++){
if(graph[v][i] && vertices[i].status == 0){
queue[end ++] = i;
vertices[i].status = 1; //discovered和visited一并标为1
}
}
printf("%d\t", v);
}
}
void bfs(){
clearStatus();
for(int i = 0; i < N; i ++){
if(vertices[i].status == 0){
BFS(i);
}
}
}
DFS
DFS就是一个很简洁的递归思路：对该顶点顺着边到达的每一个邻居都做DFS。这次相比之前写过的DFS，增加了一个clock标记dTime和fTime，即发现时间和访问完毕时间。
void DFS(int v, int & clock){
vertices[v].dTime = (++clock);
vertices[v].status = 1;
for(int i = 0; i < N; i ++){
if(graph[v][i]){
if(vertices[i].status == 0){
DFS(i, clock);
}
}
}
vertices[v].fTime = (++clock);
}
void dfs(){
clearStatus();
int clock = 0;
for(int i = 0; i < N; i ++){
if(vertices[i].status == 0){
DFS(i, clock);
}
}
}
对于dTime还有其他在递归之前做的操作，都类似于对树的先序遍历；而对于fTime及其他附近的操作，都类似于后序遍历。
还有一个很神奇的引理：若在dfs遍历树中顶点u是v的直系祖先，则[u.dTime, u.fTime]包含[v.dTime, v.fTime]；如果没有直系关系，则这两个区间不相交。我还没有看到除了判断辈份关系外的其它用途，但据说很有用……
回顾
前面做过的题中，milk3, castle都是用图遍历算法实现的。不过当时只知道自己在搜索，好像和图论这一套联系不起来。
castle
给个地图，想知道城堡有多少个房间，每个房间有多大。另外，农夫约翰想要把一面单独的墙（指两个单位间的墙）拆掉以形成一个更大的房间。 你的工作就是帮农夫约翰做以上的准备，算出房间数与房间的大小。
当时我记得看了很久的floodfill，现在看来基于dfs或者bfs都是可以的，不过就是换个连通域的时候标记一下就好了。其实每个格子都是个顶点，与临近格子之间没有墙的话就相当于有边，就这样搜索邻居就是了。
重写得跟之前几乎长得一样，还调了一堆bug才完事，不好意思挂上来了。
milk3
农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数， 最初，A和B桶都是空的，而C桶是装满牛奶的。有时，农民把牛奶从一个桶倒到 另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约， 牛奶不会有丢失。
写一个程序去帮助农民找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。
每个状态是一个顶点，能通过一步倒牛奶能达到的状态就是跟它邻接的。虽然我当时根本不觉得这是个图论（手动跟智商再见）。
dijkstra算法
我先写了一个野版本，现在看来是我不能证明正确的，而且很可能确实是错误的，就不放了(≧▽≦)
我又乖乖地看了一下比较标准的写法，也就是在选择下一个处理的顶点上，这里将所有顶点分为两个集合：最短路径已知的集合S，和最短路径未知（可能有个值，但肯定还不能确定它是最优值）的集合V - S。这里要从V - S中取出到原点最近的顶点u，就可以将它加入S（确认这个点目前已经得到了最短路径），然后对它的邻居们做一遍更新。
这是代码，在循环之前，要将原点的邻居们的最短路径填入，并且将原点加入集合S（在这里我把status置1，表示在集合S中）。
int dijkstra(int from, int to){
int dist[N];
int u, minDist;
//status初始化
clearStatus();
vertices[from].status = 1;
//dist初始化
for(int i = 0; i < N; i ++) dist[i] = 1<<30;
dist[from] = 0;
for(int i = 0; i < N; i ++){
if(graph[from][i]) dist[i] = graph[from][i];
}
while(1){
//找到最短路未知的里面距离最小的
minDist = 1<<30;
for(int i = 0; i < N; i ++){
if(vertices[i].status == 0 && dist[i] < minDist){
minDist = dist[i];
u = i;
}
}
if(minDist == 1<<30) break;
vertices[u].status = 1;
for(int i = 0; i < N; i ++){
if(graph[u][i]){
int newDist = dist[u] + graph[u][i];
if(newDist < dist[i]) dist[i] = newDist;
}
}
}
return dist[to];
}
我之前的写法很可能是错在“选择下一个顶点”不正确。毕竟，很难一眼就看懂为什么这么写是对的，尤其是为什么要选V - S中距原点最近的顶点u，而且还拍着胸脯说：来吧，你现在手里这个就已经是最短路径了。CSDN上的这个帖子的证明让我看懂了。下面我再重现一下小剧场：
- 顶点u：你怎么敢说我现在手里就是最短路径？
- 回复：你现在手里这条，一定是 S 中某倒霉顶点 v 的最短路径，再加上 v 到你那里的距离。
- 顶点u：那如果 S 中另一个更倒霉的 v' 的最短路径，再加上 v' -> u，要比我手里的这条要短呢？
- 回复：怎么可能，人家 v' 在早先加入 S 的时候，就已经把它的邻居们更新过一遍了，人家不会藏着掖着更短的路径不告诉你的。
- 顶点u：那如果我的上一个节点不必在 S 里面呢？比如 S 中某顶点 v 的最短路径，再到 （V - S） 中的 v'' ，到 v'''，再到我，才是最短的呢?
- 那（V - S） 中的 v'' 、v''' 岂不是最短路径都比你短？你怎么当这里面最短的？
- 顶点无言以对，乖乖地走到了 S 集合中——来到了我人生导师的家里，而人生导师笑眯眯地反锁上了门：“又骗来一个”。
吐槽
昨天更新了vs code的c/c++插件，也可能是我之前没注意，也可能是这个插件读了更多头文件里的东西，这两天我写什么它都在给我提示：这个在Graph::里面已经有了。
根据教程，C++里面还可以用优先级搜索算法框架，实现bfs,dfs,dijkstra等等算法。确实，这些算法的差异“就在于每一步迭代中对新顶点的选取策略不同”。bfs是优先取更早被发现的顶点，dfs则是取更晚被发现的顶点，dijk则是选距离最近的顶点。虽然不会写，但是看它们priorityUpdater的代码：
只差一个边权被换成了1而已。“BFS实际上完全等效于，在所有边的权重统一为1个单位的图中，采用Dijkstra算法构造最短路径树。 从这个意义上讲， BFS也可以视作Dijkstra算法的一个特例。”好神奇……
