图定义和相关术语
抽象看，图由顶点（Vertex）和边（Edge）组成，可记作G(V,E)。连接边的两个顶点一定要是V中的，可以存在独立的顶点。
图分为有向图和无向图
顶点的度是指和该顶点相连的边的条数，对于有向图，顶点的出边条数称为出度，入边条数成为入度。
顶点和边都可以有一定属性，而量化的属性称为权值，顶点的权值称为点权，边的权值成为边权。
图的存储
一般图的存储方式有两种，邻接矩阵和邻接表。
邻接矩阵
设图G(V,E)的顶点标号为0,1,...N-1，那么可以令二维数组G[N][N]的两维分别表示图的顶点标号，G[i][j]的值表示边权（或有无边）。
这种存储方式比较耗内存。
邻接表
设图G(V,E)的顶点标号为0,1,...N-1，把每个顶点的出边放在一个列表中，那么N个顶点就有N个列表，而每个列表的元素可以是一个struct，里面包含边的重点编号和边权。
图的遍历
DFS
沿着一条路径直到无法继续前进，才退回到路径上离当前顶点最近的还存在未访问分支顶点的岔道口，并前往访问那些未访问分支顶点，直到遍历完整个图。
BFS
使用BFS遍历图的基本思想是建立一个队列，并把初始顶点加入队列，此后每次都取出队首顶点进行访问，并把从该顶点出发可以达到的为曾加入过队列（而不是未访问）的顶点全部加入队列，直至队列为空。
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=6;
struct Node {
int v; // 边的终点编号
int w; // 边权
Node(int _v, int _w) : v(_v), w(_w) {} // 构造函数
};
vector<Node> Adj[N];
bool vis[N]={false}; // 顶点是否被访问过
void DFS(int u, int depth) { // u为当前访问顶点，depth为深度
printf("%d ", u);
vis[u]=true;
for(int i=0; i<Adj[u].size(); i++) {
Node temp = Adj[u][i];
if(vis[temp.v]==false) {
DFS(temp.v, depth+1);
}
}
}
void GTravelDFS() {
for(int i=0; i<N; i++) {
if(vis[i] == false) {
DFS(i, 1);
}
}
}
void BFS(int u) {
queue<int> q;
q.push(u);
vis[u]=true;
while(!q.empty()) {
int top = q.front();
printf("%d ", top);
q.pop();
for(int i=0; i<Adj[u].size(); i++) {
Node temp = Adj[u][i];
if(vis[temp.v] == false) {
q.push(temp.v);
vis[temp.v]=true;
}
}
}
}
void GTravelBFS() {
for(int i=0; i<N; i++) {
if(vis[i] == false) {
BFS(i);
}
}
}
int main() {
// 顶点1 》顶点3，边权为2
Adj[0].push_back(Node(1, 2));
Adj[0].push_back(Node(2, 1));
Adj[1].push_back(Node(3, 2));
Adj[1].push_back(Node(4, 2));
Adj[2].push_back(Node(1, 2));
Adj[2].push_back(Node(4, 1));
Adj[4].push_back(Node(3, 1));
Adj[4].push_back(Node(5, 2));
Adj[5].push_back(Node(3, 1));
//GTravelDFS();
GTravelBFS();
return 0;
}
最短路径
给定图G(V,E)，求一条起点到终点的路径，使得这条路径上经过的所有边的边权之和最小，即最短路径。
解决最短路径的常用算法有Dijkstra算法、Bellman-Ford算法、SPFA算法和Floyd算法。
Dijkstra算法
Dijkstra算法解决的是单源最短路径问题，即给定图G(V,E)和起点s(起点又称为源点)，求从起点s到达其他顶点的最短距离。其算法策略如下：
设置集合M存放已被访问的顶点，然后执行n次下面的两个步骤（n为顶点个数）：
- 每次从未被访问的顶点中选择与起点s的最短距离最小的一个顶点（记为u），访问并加入集合M
- 之后，令顶点u为中介点，优化起点s与所有从u能达到的顶点之间的最短距离。
#include<cstdio>
#include<vector>
using namespace std;
const int MAXV=100; // 最大顶点数
const int INF = 1000000; // 设INF为一个很大的数
int n, m, st; // 顶点数, 边数，起点
struct Node {
int v, dis; // v为边的终点顶点，dis为边权
};
int d[MAXV]; // 起点达到各顶点的最短距离
bool vis[MAXV] = {false}; // 标记数组，false表未访问
vector<Node> Adj[MAXV];
vector<int> pre[MAXV]; // pre[v]表示全部的从起点到顶点v的最短路径上v的前一个顶点的数组
void Dijkstra(int s) { // s为起点
fill(d, d+MAXV, INF); // 将整个数组元素赋值INF
d[s] = 0; // 起点到自身的距离是0
pre[s].push_back(s);
for(int i=0; i<n; i++) {
int u=-1, MIN=INF; // u为未被访问的顶点中选择与起点s的最短距离最小的一个顶点
for(int j=0; j<n; j++) {
if(vis[j]==false && d[j]<MIN) {
u = j;
MIN = d[j];
}
}
if(u==-1) return; // 剩下的顶点和u不连通
vis[u]=true; // 标记已访问
for(int j=0; j<Adj[u].size(); j++) {
int v = Adj[u][j].v;
int dis = Adj[u][j].dis;
if(vis[v]==false && d[u]+dis < d[v]) { // 优化起点s与所有从u能达到的顶点之间的最短距离
d[v] = d[u] + dis;
pre[v].clear();
pre[v].push_back(u);
} else if(vis[v]==false && d[u]+dis==d[v]) {
pre[v].push_back(u);
}
}
}
}
int optvalue; // 第二标尺最优值
vector<int> path, tempPath; // 最优路径，临时路径
int W[MAXV]; // 点权
void DFS(int v) { // v为当前访问顶点
if(v == st) {
tempPath.push_back(v);
int value=0;
for(int i=tempPath.size()-1; i>=0; i--) {
int id = tempPath[i];
value += W[id];
}
if(value>optvalue) {
optvalue = value;
path = tempPath;
}
tempPath.pop_back();
return;
}
tempPath.push_back(v);
for(int i=0; i<pre[v].size(); i++) {
DFS(pre[v][i]);
}
tempPath.pop_back();
}
int main() {
scanf("%d%d%d", &n, &m, &st);
for(int i=0; i<n; i++) {
scanf("%d", &W[i]);
}
for(int i=0; i<m; i++) {
int l, r, dis;
Node temp1, temp2;
scanf("%d%d%d", &l, &r, &dis);
temp1.v = r, temp1.dis = dis;
Adj[l].push_back(temp1);
temp2.v = l, temp2.dis = dis;
Adj[r].push_back(temp2);
}
Dijkstra(st);
for(int i=0; i<n; i++) {
//printf("%d:", d[i]);
printf("%d: ",i);
for(vector<int>::iterator it=pre[i].begin(); it != pre[i].end(); it++) {
printf("%d ", *it);
}
printf(" \n");
}
DFS(5);
for(int i=path.size()-1; i>=0; i--) {
printf("%d ", path[i]);
}
return 0;
}
说明：
- Dijkstra算法只能应对边权都是非负数的情况，如果边权出现负数，那么很可能会出错，这是最好使用SPFA算法。
- 如果是无向边，只需要把无向边当成指向相反的有向边即可。对邻接表来说，只需在u的邻接表Adj[u]末尾添加上v，并在v的邻接表末尾添加上u。
Bellman-Ford算法和SPFA算法
Bellman-Ford算法也是解决单源最短路径问题，能处理边权是负数的情况
Floyd算法
Floyd算法用来解决全源最短路径问题，即给定图G(V,E)，求任意两点u，v之间的最短路径长度，时间复杂度是O(n^3)。
如果存在顶点k，使得以k作为中介点时顶点i和顶点j的当前最短距离缩短，则使用顶点k作为顶点i和顶点k的中介点，即当dis[i][k]+dis[k][j] < dis[i][j]时，令dis[i][j]=dis[i][k]+dis[k][j]
最小生成树
定义
最小生成树是在一个给定的无向图G(V,E)中求一棵树T，使得这棵树拥有图G中的所有顶点，且所有的边都是来自图G中的边，并且满足整棵树的边权之和最小。
满足性质
- 最小生成树是树，因此其边数等于顶点数减1，且数内一定不会有环
- 对给定的图G(V,E)，其最小生成树可以不唯一，但其边权之和一定是唯一的。
- 由于最小生成树是在无向图上生成的，因此其根结点可以是这棵树上的任意一个结点。
求解最小生成树一般有两种算法，即prim算法和kruskal算法。
prim算法
prim算法的基本思想是对图G(V,E)设置集合S，来存放已经被访问的顶点，然后执行n次下面的两个步骤（n为顶点个数）
- 每次从集合V-S（即未访问）中选择与集合S最近的一个顶点（记为u），访问u并将其加入集合S，同时把这条离集合S最近的边加入最小生成树中
- 令顶点u作为集合S与集合V-S连接的接口，优化从u能到达的未访问顶点与集合S的最短距离
#include<cstdio>
#include<vector>
using namespace std;
const int MAXV=1000;
const int INF=10000000;
struct Node{
int v, dis;
Node(int _v, int _dis) : v(_v), dis(_dis) {} // 构造函数
};
vector<Node> Adj[MAXV];
int n;
int d[MAXV]; // 顶点与集合S的最短距离，此处与dijkstra不同
bool vis[MAXV]={false};
int prim() { // 默认0号为初始点
fill(d, d+MAXV, INF);
d[0]=0;
int ans=0; // 存放最小生成树的边权之和
for(int i=0; i<n; i++) {
int u=-1, MIN=INF;
for(int j=0; j<n; j++) {
if(vis[j]==false && d[j]<MIN) {
u=j;
MIN=d[j];
}
}
if(u == -1) return -1;
vis[u]=true;
ans += d[u];
for(int k=0; k<Adj[u].size(); k++) {
int v=Adj[u][k].v, dis=Adj[u][k].dis;
if(vis[v]==false && dis<d[v]) { // 此处与dijkstra不同
d[v]=dis;
}
}
}
return ans;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for(int i=0; i<m; i++) {
int l, r, dis;
scanf("%d%d%d", &l, &r, &dis);
Adj[l].push_back(Node(r, dis));
Adj[r].push_back(Node(l, dis));
}
int ans = prim();
printf("%d\n", ans);
for(int i=0; i<n; i++) {
printf("%d ", d[i]);
}
return 0;
}
prim算法的时间复杂度是O(V^2)，其中邻接表实现的prim算法可以通过堆优化使时间复杂度降为O(VlogE+E)
kruskal算法
kruskal算法的基本思想：
- 对所有边按边权从小到大进行排序
- 按边权从小到大测试所有边，如果当前测试边所连接的两个顶点不在同一个连通块中，则把这条测试边加入当前最小生成树中；否则将边舍弃
- 执行步骤2，直到最小生成树中的边数等于总顶点数减1或是测试完所有边时结束。而当结束时如果最小生成树的边数小于总顶点数减1，说明该图不连通
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXV=110; // 最大顶点数
const int MAXE=10010; // 最大边数
struct edge{
int v, u; // 边的两个端点
int cost; // 边权
}E[MAXE];
bool cmp(edge a, edge b) {
return a.cost < b.cost;
}
// 并查集部分
int father[MAXV];
int findFather(int x) {
int a=x;
while(x != father[x]) {
x = father[x];
}
// 路径压缩
while(a != father[a]) {
int z = a;
a = father[a];
father[z] = x;
}
return x;
}
bool noSame(edge E) {
int u = findFather(E.u);
int v = findFather(E.v);
if(u != v) {
return true;
}
return false;
}
int kruskal(int n, int m) { // n顶点数 m边数
int ans=0, numEdge=0;
for(int i=0; i<n; i++) {
father[i]=i;
}
sort(E, E+m, cmp);
for(int i=0; i<m; i++) {
if(noSame(E[i])) {
father[E[i].u] = E[i].v;
ans += E[i].cost;
numEdge++;
if(numEdge == n-1) break;
}
}
if(numEdge != n-1) {
return -1;
}
return ans;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for(int i=0; i<m; i++) {
scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].cost);
}
int ans = kruskal(n, m);
printf("%d\n", ans);
return 0;
}
kruskal算法的时间复杂度主要源于对边进行排序，因此其时间复杂度是O(ElogE)，其中E为图的边数。
如果是稠密图（边多），则用prim算法；如果是稀疏图（边少），则用kruskal算法
拓扑排序
有向无环图
如果一个有向图的任意顶点都无法通过一些有向边回到自身，那么称这个有向图为有向无环图（Directed Acyclic Graph-DAG）。
拓扑排序
拓扑排序是将有向无环图G的所有顶点排成一个线性序列，使得对图中的任意两个顶点u、v，如果存在边u->v，那么序列中u一定在v前面。这个序列又被称为拓扑排序。
基本思路如下：
- 定义一个队列Q，并把所有入度为0的结点加入队列
- 取队列首结点，输出。然后删去所有从它出发的边，并令这些边到达的顶点的入度减1，如果某个顶点的入度减为0，则将其加入队列
- 反复进行2操作，直到队列为空。如果队列为空时入过队的结点数目恰好为N，说明拓扑排序成功，图G为有向无环图；否则，拓扑排序失败，图G中有环
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
const int MAXV=100;
int n, m ,inDegree[MAXV]; // 顶点数，边数，各顶点入度数
vector<int> Adj[MAXV];
void topoLogicalSort() {
int passNum=0;
queue<int> q;
for(int i=0; i<n; i++) {
if(inDegree[i]==0) {
q.push(i);
passNum++;
}
}
while(!q.empty()) {
int top = q.front();
printf("%d ", top);
q.pop();
for(int i=0; i<Adj[top].size(); i++) {
int end = Adj[top][i];
inDegree[end]--;
if(inDegree[end]==0) {
q.push(end);
passNum++;
}
}
}
if(passNum==n) {
printf("\nsuccess\n");
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i=0; i<n; i++) {
scanf("%d", &inDegree[i]);
}
for(int i=0; i<m; i++) {
int st, ed;
scanf("%d%d", &st, &ed);
Adj[st].push_back(ed);
}
topoLogicalSort();
return 0;
}
关键路径
AOV网和AOE网
顶点活动（Activity On Vertex，AOV）网是指用顶点表示活动，而用边集表示活动间优先关系的有向图。
边活动（Activity On Edge，AOE）网是指用带权的边集表示活动，而用顶点表示事件的有向图，其中边权表示完成活动需要的时间。
关键路径
关键路径就是AOE网的最长路径，而把关键路径上的活动成为关键活动。
网友评论