推荐书籍《数据结构与算法分析--C++语言描述》p.304-p.316 源代码
图：图有顶点和边构成。图用符号G表示，顶点用符号V表示，边（或称弧）用符号E表示。G(V,E)表示由顶点集合V和边集合E构成的图。其中边由两个顶点构成，若两个顶点构成的边无序，如v-w和w-v相同，则称无向图，否则称有向图。若（v,w）构成一条边，则称w邻接到v；若是无向图，则w邻接到v且v邻接到w。图有时还有第三种属性，称权（或值）。
路径：图中的路径是顶点序列，路径程度为序列包含的边的数目。如N个顶点组成的路径，长为N-1。从v到v的路径长为0
简单路径：由互异的顶点组成的路径，但第一个和最后一个顶点可能相同。 顶点v到v的路径，称为环。
有向图中的圈：满足长度至少为1，起点与终点为同一个顶点的简单路径。u-v-u是圈。
无向图中的圈：满足有向图圈的要求，且边是互异的。因此u-v-u不是圈。
无向图的连通性：对于无向图，若每个顶点到其他顶点都存在路径，则称无向图连通。
有向图的连通性：对于有向图，若每个顶点到其他顶点都存在路径，则称有向图强连通。若有向图不是强连通，但是其对应的无向图（有向图的边去掉方向）是连通的，则称该有向图弱连通。
完全图：每一对顶点都存在一条边的图
图的表示 邻接矩阵：使用一个二维数组，每条边(u,v)对应g[u][v]，若边存在，则g[u][v]置为true，否则置为false。如果边有权，则置为权的值。可以用很大或很小的数字表示不存在的边。邻接矩阵法适合稠密的图。邻接表：对于每个顶点，使用一个表存放其邻接的顶点，如果边有权，也可以在表中附加权的信息，是图的标准表示方法。可以使用vector实现邻接表，或是映射，因为顶点是互异的。
入度：顶点v的入度为边（u，v）的数目，即所有v邻接的顶点u的数目。入边，如边（u，v）为v的入边。
拓扑排序：有向无圈图中顶点的一种排序，若存在边(vi,vj)，即j邻接i，那么排序中j在i之后。拓扑排序不唯一。实现：首先找出图中没有入边（即入度为0）的顶点，在排序表中放置该顶点，之后将该顶点和所有的边从图中删除，继续算法。如果没有入度为0的顶点，说明该图有圈。
赋权路径长：假设图有权，每条边(vi,vj)的权重(或开销)为ci,j，则路径长为边对应的权求和。
无权路径长：路径上所有边的数目，若顶点数目N，则path_min=N-1。
单源 从一个固定起点出发 如s出发到所有的v 或s出发到某一固定的v
广度优先搜索BFS(BreadthFirstSearch)
按层处理顶点，距开始最近的顶点首先被求值，而最远的点最后被求值，很像树的层序遍历。因为广度优先搜索最先处理相邻的层，因此可用于求最短路径或最小深度。广度优先搜索是盲目搜索，因为算法本身就是从起点开始，先遍历下一层，直到遍历到所有的终点，因此遍历到终点的时间长。
有向图的拓扑排序
若有向图中有边w(a,b)，则在拓扑排序中，b在a之后。因为需要先访问a才能通过a访问b，有向图不一定存在拓扑排序，因为有的边会破坏拓扑有序性，如存在边w(a,b)和w(b,a)。那么就不存在拓扑排序，因为访问b之前需要先访问a，而访问a之前又要先访问b。如果有向图存在拓扑排序，那么拓扑排序不唯一，可能有多个。因为确定拓扑排序当前节点时，任何没有前置节点的节点都可以作为当前节点。
单源无权最短路径问题-BFS算法
从某个起点出发，到达所有可达节点的算法，每次都更新当前节点到其邻接节点的最短路径（因为无权，所以直连是最短路径），因为无权，为了避免节点重复访问，需要设置已读。如果要求某起点到具体节点的路径，在循环中增加判断当前节点是否为结束节点即可。无权最短路径问题对于有向图和无向图都适用，因为对于有向图，除非有圈，否则节点不能重复访问；对于无向图，节点重复访问的路径肯定大于不重复访问的路径。单源有权最短路径问题（非负值权重）-Dijkstra算法
有权有向图或有权无向图中，从某个顶点出发，到达其他顶点的最短路径问题。其中权重为非负值。使用Dijkstra算法，即贪心算法，从起点开始，只要v未被标记（无向图中需要标记，有向图因为边有向，所以不需要记录是否已读）根据w(u,v)+d[u]和d[v]的较小值更新d[v]，若vi在u的所有邻接顶点中的d[vi]最小，则d[vi]作为下个要访问的顶点。
有向图单源有权最短路径问题（有负值权重）-BellmanFord算法
有权路径权重有正有负，从s出发到v的最短路径。因为有负值权重所以dijkstra算法的核心思路 w(a,b)<w(a,c)+w(c,b)失效，因此w(c,b)可以为负可以使w(a,c)减小从而使得w(a,c)+w(c,b)<w(a,b)。
有权有向图最小生成树问题-Prim算法
最小生成树是对于连通的赋权无向图，如何确定一条连接每个顶点的路径，使得路径最小。它可以解决例如给所有的房间通电线，使得电线最短这类问题。注意，对于非连通的无向图，不存在连通每个顶点的路径。
算法逻辑：找入度为0的顶点v作为拓扑排序的当前顶点，将v邻接的顶点t其入度-1，重复该循环。可以使用队列来模拟，1.构建邻接表和计算入度 2.入度为0的节点入队列 3.只要队列非空 取队列首cur放入拓扑排序 队列首出队列 其邻接的每个顶点 入度-1 若入度为0 放入队列。最后判断拓扑排序中的节点个数是否等于图中节点个数即可。因为是有向图，所以不需要记录访问的节点。
vector<int> sortTopo(vector<vector<int>> ad, vector<int> cnt) { int n = cnt.size();//节点个数 queue<int> q;//辅助队列 顺序访问 for (int i = 0; i < n; i++) if (cnt[i] == 0) q.push(i);//入度为0的节点入队列 vector<int> res;//拓扑排序 while (!q.empty()) { int cur = q.front();//当前节点 res.push_back(cur);//放入拓扑排序 q.pop();//出队列 auto adCur = ad[cur];//当前节点的邻接节点 for (auto p : adCur)//遍历每一个节点p { cnt[p]--;//邻接节点p的入度减1 if (cnt[p] == 0)//入度为0 q.push(p);//放入队列 } } if (res.size() == n)//所有节点均拓扑有序 return res; else return {};//无拓扑排序 }打印出的拓扑排序为2 1 3 4 5只是一个可能的拓扑排序，实际上在节点21之后 3和4的入度均为0，所以3和4之间拓扑顺序可以反转，即2 1 4 3 5也可以。
利用BFS搜索，因为无权，假设所有权重均为1。有w(a,b)<w(a,c)+w(c,b)，以起点为树的根节点，层序遍历其子节点，到任意节点的距离为该节点的层序。
vector<int> minPathGraphWithoutWeight(vector<vector<int>>ad, int n,int start, int end)//无权无向图的最小路径算法 { start--;//节点序号与索引对齐 end--;//节点序号与索引对齐 queue<int> q; vector<bool> known(n, false); vector<int> res(n,-1); q.push(start); known[start] = true; int layer = 0; while (!q.empty()) { int size = q.size();//当前层的节点个数 for (int i = 0; i < size; i++)//遍历当前层 { auto cur = q.front();//当前节点 q.pop();//出队列 res[cur] = layer;//记录最小路径 if (cur == end) return res;//指定终点 提前退出 for(auto p:ad[cur]) if (!known[p])//未访问 { q.push(p);//放入队列 known[p] = true;//记录已在队列中 } } layer++;//层序增加 } return res; }可以看出，节点3到其他每个顶点的最小距离即是其层序，在指定终点后，终点之后的每个节点其距离都未计算。
从某个起点出发，到达所有可达节点的最小距离，或者某个具体节点的最小距离。Dijkstra算法基于贪心算法，因为没有负值边，所以只要每次都选取当前距离最小的那个距离作为到当前节点的距离，即能保证最小距离。如果起点相同，从a出发，到b，c均有边，w(a,b)=3，w(a,c)=5，那么选取当前距离最小的w(a,b)作为a到b的距离，因为没有负值边，所以从c出发再到b的距离一定不可能小于w(a,c)，又w(a,c)>w(a,b)，所以能保证a到b的是最小距离。再考虑起点不同，如a到b和c到b均有边，其中起点为s，w(s,a)=10,w(a,b)=3，w(s,c)=5,w(c,b)=5，那么s到b的最小距离应该为10，即s->c->b。综上，只要当前节点未标记，即以d(s,v)+w(v,b)和d(s,b)取最小值更新d(s,b)，直至b访问。
vector<int> minPathGraphWithWeight(vector<vector<pair<int, int>>> ad, int n, int start, int end) { start--;//序号对齐 end--;//序号对齐 vector<int> res(n,INT_MAX); vector<bool> known(n, false); res[start] = 0; //queue<int> q; int cur = start;//当前节点 while (cur != -1)//当没有下个需要更新或者能更新的节点 置cur为-1 使循环退出 { known[cur] = true; if (cur == end) return res; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> s;//使用小顶堆求当前下个待处理节点 for(auto p:ad[cur]) if (!known[p.first])//未读节点 { res[p.first] = min(res[p.first], res[cur] + p.second);//更新最小距离 s.push({ res[p.first],p.first});//放入小顶堆 求下一个节点 } if (s.empty())//没有需要更新的节点或没有能更新的节点了 cur = -1;//结束 else cur = s.top().second; } return res; }如果图中有负值圈，那么不存在最小路径，因为每次走负值圈，路径值都会减小。若无负值圈，那么最小路径上边的数目最大为n-1，因为有n个顶点，除非有负值圈，此时无最小距离，否则每个顶点最多经过一次。即有n-1条边。记出发点为v0，则初始距离d[v0]=0,其余d[vi]=INT_MAX。外层循环为i，最多n-1次，若i==n，则说明有负值圈，本轮中有最小路径更新的所有顶点都在负值圈中。否则内层循环处理每条边，记当前边为w(u,v)，若d[u]+w(u,v)<d[v]，则更新d[v]。若指定终点end，则在内层循环中记录d[end]是否更新，若内层循环的所有边都未更新d[end]，说明start->end的最小路径已经找到。若不指定end，则在内层循环中记录每个路径d[i]是否更新，若无路径更新，说明start->i的所有路径都已达到最小值。
vector<int> minPathWithMinusWeight(vector<vector<pair<int, int>>> ad, int n,int start,int end) { start--;//顶点序号与索引对齐 end--;//顶点序号与索引对齐 vector<int> path(n, INT_MAX);//从start出发到其他顶点的最小距离 path[start] = 0;//起点到起点的最小距离 初始值为0 for (int i = 0; i <= n; i++)//若能进入第n次循环说明存在负值圈 { if (i == n) return {};//有负值圈时返回空 当i==n时能更新（更小路径）的顶点都是在负值圈上的点 bool update = true;//记录本轮是否有更新 若无更新 说明已达到所有顶点的最小路径 若指定end顶点 则update只检测end顶点是否更新 //遍历每条边 若d[u]不为INT_MAX 则以min(path[u]+w(u,v),path[u])更新v j记录边的起点 p.first为边的终点 p.second为边的权重 for (int j = 0; j < n; j++) { if (path[j] == INT_MAX) continue;//起点为j的路径 s->j还未更新 for (auto p : ad[j])//遍历起点为顶点j的每条边 { if (path[p.first] > path[j] + p.second)//path[v]>path[u]+w(u,v) { path[p.first] = path[j] + p.second;//更新start->v的最小路径 update = false;//记录本轮有最小路径更新 } } } if (update) break;//该轮没有更小的路径更新 说明已经迭代已经停止 } return path; }
最小生成树为图中连接所有顶点的边具有最小的权重和。最小生成树包含图中所有顶点，无圈，不唯一。其基本算法是，从某一个顶点出发（任意），选取当前顶点cur的边中权重最小的那条边w(cur,nxt)，则cur顶点在最小生成树中的边为w(cur,nxt)，同时置cur为已读。即每次都以边w(cur,nxt)的最小值更新所有未读的顶点nxt的值，若nxt的值为当前未读顶点中的最小值，则将其作为下一个处理的顶点。
vector<int> minSpanningTree(vector<vector<pair<int, int>>> ad, int n) { vector<bool> known(n, false);//记录每个顶点是否已读 vector<int> res(n,-1);//记录每个顶点连接的顶点 vector<int> cost(n, INT_MAX);//cost[i]=min(w(j,i)) 所有邻接到i的边的最小权重 初值为INT_MAX便于取min queue<int> q; q.push(0);//从顶点1开始构建最小生成树 起点任意 known[0] = true; while (!q.empty()) { int cur = q.front(); q.pop(); auto adj = ad[cur];//cur的所有边 for (auto p : adj) if (!known[p.first] && cost[p.first] > p.second) { res[p.first] = cur;//记录边 要在更新当前边的cost时 更新连接的顶点 cost[p.first] = p.second; } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> s;//小顶堆 求当前顶点的最小边 for (int i = 0; i < n; i++) if (!known[i]) s.push({ cost[i],i }); if (!s.empty()) { int nxt = s.top().second;//当前顶点在最小生成树中的边 做为下个顶点 q.push(nxt); known[nxt] = true;//记为已读 } cout << "cur=" << cur+1 << ":";//当前顶点和 当前轮每个顶点的连接情况 for (auto p : res) cout << p + 1 << " "; cout << endl; } return res; }
顶点序号从1开始，连接顶点为0意为还未更新。最后顶点1无连接顶点（起点），顶点2连顶点1，顶点3连顶点4，顶点4连顶点1，顶点5连顶点7，顶点6连顶点7，顶点7连顶点4。
