假设是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*2]; //无向图，建图时边的个数为两倍 int head[maxn],tot=0; ///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=0; i<=n; i++) for(int j=head[i]; j！=-1; j=edge[j].next) }
DFS（深度优先搜索）：递归
BFS（广度优先搜索）：队列（访问顶点，顶点出队，搜索相邻顶点入队；只要队列不空，则重复如下操作：队首元素出队，从队首元素搜索相邻下一步）
记忆化搜索：需要提前计算打表，或者将已经访问的元素保存
适用问题：最优解、计数问题、图论等
适用问题：
算法步骤：
const int maxnum=505; 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=1;j<=n;j++)///找出入度为0的点，放入最小优先队列，小的值先弹出 { if(indegree[j]==0) { myque.push(j); } } for(int i=1;i<=n;i++) { int toptmp=myque.top(); ans.push_back(toptmp);///把已找出的数放入数组 myque.pop(); for(int j=1;j<=n;j++) { if(graph[toptmp][j]) { indegree[j]--;///删除第一个数后，它指向的点的入度-1 if(indegree[j]==0)///如果入度为0，加入队列 myque.push(j); } } } ///最后输出即可 for(int i=0;i<ans.size()-1;i++) printf("%d ",ans[i]); printf("%d\n",ans[ans.size()-1]); } int main() { int n=0,m=0; while(scanf("%d %d",&n,&m)!=EOF) { memset(indegree, 0, sizeof(indegree)); memset(graph, false, sizeof(graph)); for (int i = 0; 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 0; }
一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的n-1边，同时这些边的权值和最小。最小生成树是权值之和最小的极小生成树。（假设N点M边）
Prime算法：邻接矩阵实现，时间复杂度O（N^2），对点贪心，适合稠密图
Kruskal算法：邻接表实现，复杂度O(E*lnE)，对边贪心，适用于稀疏图.
单源最短路径——Dijkstra：
const int inf=0x3f3f3f3f; int g[605][605],low[605];///g是邻接矩阵,low是当前顶点到源点的最短距离 bool vis[605];///该点是否被访问 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=0;i<m;i++)///输入图 { int a,b,c; scanf("%d%d%d",&a,&b,&c); g[a][b]=c;///单向图 } for(i=1;i<n;i++)///初始化此时low数组 low[i]=cost[1][i]; vis[1]=true; for(i=2;i<=n;i++) { int minn=inf; for(j=1;j<=n;j++)/// { if(!vis[j]&&low[j]<minn) { minn=low[j]; k=j; } } vis[k]=true; for(j=1;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 0; }
全源最短路径——Floyed：
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=1;i<=n;i++) for(int j=1;j<=n;j++) dist[i][j]=g[i][j]; int min_circle=INF; for(int k=1;k<=n;k++)///枚举k { ///先判断环，后更新，保证判断环时的dist[i][j]不经过 k for(int i=1;i<k;i++) { for(int j=i+1;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=1;i<=n;i++) { for(int j=1;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; }
图论相关知识（DFS、BFS、拓扑排序、最小代价生成树、最短路径）
原文：https://www.cnblogs.com/Littlejiajia/p/13359977.html
