一,基本概念
1.有向图：图的边有方向，只能按箭头方向从一点到另一点。
2.无向图：图的边没有方向，可以双向。
3.节点的度：无向图中与节点相接的数目，称为结点的度。
4.节点的入度：在有向图中，以这个节点为终点的有向边的数目。
5.节点的出度：在有向图中，以这个节点为起点的有向边的数目。
6.权值：边的长度。
7.连通：两点之间有通路，就称这两点是连通的。
8.回路：起点与终点相同的路径，称为回路。
9.强连通分量：有向图中任意两点都连通的最大子图。
二,图的存储
1.邻接矩阵存储
/*
a[i][j]的值｛
1.1或权值
2.0或无穷大
｝
如：
0 1 1 1
1 0 1 1
1 1 0 0
1 1 0 0
*/
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=0x7fffffffx7fffffff//无穷大
}
}
cin>>m;
int u,v,w;//u：点u v:点v w:权值
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
a[i][j]=a[j][i]=w;
}
2.邻接表存储
用数组模拟链表进行存储。
三,图的遍历
深度优先搜索和广度优先搜索
四,Floyd
最短路径算法之一，时间复杂度为O（n^3）。
//Floyd主要代码
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]>a[i][k]+a[k][j]){
a[i][j]=a[i][k]+a[k][j];
}
}
}
}
如果要打印路径，可以用pash[i][j]来存储从i到j的路径中j的前驱。代码如下：
//最短路径打印
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]>a[i][k]+a[k][j]){
pash[i][j]=push[i][k];
a[i][j]=a[i][k]+a[k][j];
}
}
}
}
//最后要倒序打印