图的存储
假设是n点m边的图：
邻接矩阵：很简单，但是遍历图的时间复杂度和空间复杂度都为n^2，不适合数据量大的情况
邻接表：略微复杂一丢丢，空间复杂度n+m，遍历图的时间复杂度为m，适用情况更广
前向星：静态链表，即用数组实现邻接表的功能。对于每个顶点，前向星存储的是该顶点的邻接边而非邻接点，head[maxn]存储的是顶点信息，edge[maxm]存储的是顶点对应的边的信息
struct Edge
{
int to;///某个顶点u的邻接点
int next;///顶点u的下一条邻接边的编号
int val;///该邻接边的权值
Edge(){}
Edge(int _to,int _next,int _val){
to=_to;next=_next;val=_val;
} edge[maxm*]; //无向图，建图时边的个数为两倍 int head[maxn],tot=; ///head用来表示以i为起点的第一条边存储的位置，tot读入边的计数器
void add_edge(int from,int to,int valt)///在图中添加边，O(M)
{
edge[tot]=Edge(to,head[from],valt);
head[from]=tot++;
}
void read() //遍历所有边，O(N*M)
{
for(int i=; i<=n; i++)
for(int j=head[i]; j！=-; j=edge[j].next)
}
前向星
DFS/BFS
DFS（深度优先搜索）：递归
BFS（广度优先搜索）：队列（访问顶点，顶点出队，搜索相邻顶点入队；只要队列不空，则重复如下操作：队首元素出队，从队首元素搜索相邻下一步）
记忆化搜索：需要提前计算打表，或者将已经访问的元素保存
适用问题：最优解、计数问题、图论等
- 最优解问题：DFS通常是搜索所有可能的结果来求最优解；BFS本身一层层向下搜索的特点，适合求解最优问题；
- 计数问题：DFS彻底完成一个分支之后再去进行下一个分支，并且搜索所有可能结果，所以更适合计数问题；BFS因为队列里同时有多个未完成的分支、所以在解计数问题中并不常见；
- 图论：DFS、BFS是图论中遍历图的方式，在最短路、迷宫类游戏中很常见。（BFS求最短路径，DFS求所有完整路径）
拓扑序列
适用问题：
- 在某一个有向图graph中，假设每一条有向边(u,v)代表节点u必须排在节点v的前面，那么按照这样的规则，将所有的节点进行排序，最终得出的序列就称为拓扑序列。只要能将事物抽象成有向图，并要求按规则排序，那么就可以考虑拓扑排序，比如选修课程的安排、按胜负排名次等。
- 拓扑排序只适用于有向无环图，所以使用拓扑排序的第一步就是先将问题抽象成有向图，进行图的初始化、建立等工作，然后运行拓扑排序算法即可。
- 顶点的顺序是保证所有指向它的下个节点在被指节点前面！(例如A—>B—>C那么A一定在B前面，B一定在C前面)。所以，这个核心规则下只要满足即可，所以拓扑排序序列不一定唯一！
- 简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
算法步骤：
- 新建node类，包含节点数值和它的指向(这里直接用list集合替代链表了)
- 初始化，添加每个节点指向的时候同时被指的节点入度+1！(A—>C)那么C的入度+1；
- 扫描一遍所有node。将所有入度为0的点加入一个栈(队列)。
- 当栈(队列)不空的时候，抛出其中任意一个node(栈就是尾，队就是头，顺序无所谓，上面分析了只要同时入度为零可以随便选择顺序)。将node输出，并且node指向的所有元素入度减一。如果某个点的入度被减为0，那么就将它加入栈(队列)。
- 重复上述操作，直到栈为空。
const int maxnum=;
bool graph[maxnum][maxnum];///邻接矩阵，保存图
int indegree[maxnum];///每个点的入度
void top_sort(int n)///对n个数进行拓扑排序
{
vector<int> ans;///保存拓扑序
priority_queue<int, vector<int>, greater<int> > myque;///维护节点入度
for(int j=;j<=n;j++)///找出入度为0的点，放入最小优先队列，小的值先弹出
{
if(indegree[j]==) {
myque.push(j);
}
}
for(int i=;i<=n;i++)
{
int toptmp=myque.top();
ans.push_back(toptmp);///把已找出的数放入数组
myque.pop();
for(int j=;j<=n;j++)
{
if(graph[toptmp][j])
{
indegree[j]--;///删除第一个数后，它指向的点的入度-1
if(indegree[j]==)///如果入度为0，加入队列
myque.push(j);
}
}
}
///最后输出即可
for(int i=;i<ans.size()-;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[ans.size()-]);
}
int main()
{
int n=,m=;
while(scanf("%d %d",&n,&m)!=EOF)
{
memset(indegree, , sizeof(indegree));
memset(graph, false, sizeof(graph));
for (int i = ; i < m; i++)
{
int p1, p2;
scanf("%d %d",&p1, &p2);
if (!graph[p1][p2])
indegree[p2]++; ///统计p2的入度
graph[p1][p2] = true;
}
top_sort(n);
}
return ;
}
拓扑序列
最小代价生成树
一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的n-1边，同时这些边的权值和最小。最小生成树是权值之和最小的极小生成树。（假设N点M边）
Prime算法：邻接矩阵实现，时间复杂度O（N^2），对点贪心，适合稠密图
- 输入：一个加权连通图，其中顶点集合为V，边集合为E；
- 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
- 重复下列操作，直到Vnew = V：
- 在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
- 将v加入集合Vnew中，将<u, v>边加入集合Enew中；
- 输出：使用集合Vnew和Enew来描述所得到的最小生成树。
Kruskal算法：邻接表实现，复杂度O(E*lnE)，对边贪心，适用于稀疏图.
- 记Graph中有v个顶点，e个边
- 新建图Graph_new，Graph_new中拥有原图中相同的e个顶点，但没有边
- 将原图Graph中所有e个边按权值从小到大排序
- 循环：从权值最小的边开始遍历每条边，直至图Graph中所有的节点都在同一个连通分量中（if 这条边连接的两个节点于图Graph_new中不在同一个连通分量中，则添加这条边到图Graph_new中）
最短路径
单源最短路径——Dijkstra：
- 单源最短路问题，可以得到一点到其他各点之间的最短路
- 边的权值不能为负
- 使用邻接矩阵，算法的运行时间是 O(N^2)。使用邻接表，时间复杂度O(MlogN)
const int inf=0x3f3f3f3f;
int g[][],low[];///g是邻接矩阵,low是当前顶点到源点的最短距离
bool vis[];///该点是否被访问
int main()
{
int m,m,i,j,k;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(g,inf,sizeof(g));
memset(low,inf,sizeof(low));
memset(vis,inf,sizeof(vis));
for(i=;i<m;i++)///输入图
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b]=c;///单向图
}
for(i=;i<n;i++)///初始化此时low数组
low[i]=cost[][i];
vis[]=true;
for(i=;i<=n;i++)
{
int minn=inf;
for(j=;j<=n;j++)///
{
if(!vis[j]&&low[j]<minn)
{
minn=low[j];
k=j;
}
}
vis[k]=true;
for(j=;j<=n;j++)///更新最短距离
{
if(!vis[j]&&low[k]+g[k][j]<low[j])
{
low[j]=low[k]+g[k][j];
}
}
}
if(low[n]==inf)
printf("-1\n");
else
printf("%d\n",low[n]);
return ;
}
Dijkstra单源最短路径
全源最短路径——Floyed：
- 多源最短路问题，可以得到任意两点之间的最短路；查找无向图中最小环
- 边的权值不能为负值
- 使用邻接矩阵，时间复杂度是O(N^3)。不适用于大量数据。
int n,g[maxn][maxn];///g[i][j]表示从i到j的距离，inf表示i，j之间不直接连通
int dist[maxn][maxn];///dist[i][j]表示i到j的最短距离
int floyed()
{
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
dist[i][j]=g[i][j];
int min_circle=INF;
for(int k=;k<=n;k++)///枚举k
{
///先判断环，后更新，保证判断环时的dist[i][j]不经过 k
for(int i=;i<k;i++)
{
for(int j=i+;j<k;j++)
{
if(dist[i][j]!=INF&&g[i][k]!=INF&&g[j][k]!=INF)///环至少要有3个结点
min_circle=min(min_circle,dist[i][j]+g[i][k]+g[j][k]);
///i-j不经过k的最短路 + 边i-k + 边j-k
}
} ///以下和求全源最短路一致，更新以k为中介点的最短路
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
if(dist[i][k]!=INF&&dist[k][j]!=INF)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
return min_circle;
}
Floyed求无向图的最小环