（1）图的类型：有向图、无向图、加权图；
有向图和无向图从字面理解就可以知道一个有方向，一个无方向；
而加权图则是每条边都有权重，权重可以是任何一种度量，比如时间，距离，尺寸等。
（2）图的专业术语：
>>顶点、边、路径（从一个顶点到另一个顶点之间经过的所有顶点的集合）、路径长度（边数）。
>>环：起点和终点为同一个顶点的路径。
>>负权环：在「加权图」中，如果一个环的所有边的权重加起来为负数，我们就称之为「负权环」。
>>连通性：两个不同顶点之间存在至少一条路径，则称这两个顶点是连通的。
>>顶点的度：「度」适用于无向图，指的是和该顶点相连接的所有边数称为顶点的度。
>>顶点的入度：「入度」适用于有向图，一个顶点的入度为d，则表示有d条与顶点相连的边指向该顶点。
>>顶点的出度：「出度」适用于有向图，它与「入度」相反。一个顶点的出度为dd，则表示有dd条与顶点相连的边以该顶点为起点。
>>单源最短路：已知起始点，求起点到其他任意点最短路径的问题。
>>多源最短路：已知起点和终点，求任意两点之间的最短路径。
2.图的存储（1）矩阵存图法：
#include
#define maxn 102
using namespace std;
int n,a[maxn][maxn],x,y,k;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x>>y>>k;
a[x][y]=k;
a[y][x]=k; //无向图需要(元素对称)
}
//依次对每个顶点访问
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]) cout<"<
（2）邻接表存图法：
#include
#define maxn 1002
using namespace std;
int num;
int head[1001],next[maxn],to[maxn],w[maxn];
void add(int x,int y,int k){
++num;
to[num]=y; //储存终点
w[num]=k; //储存权值
next[num]=head[x]; //进行记录可查找邻边
head[x]=num; //随时更新表头
}
int main(){
int n,m,x,y,k;
cin>>n>>m; //n为边数，m为顶点数
for(int i=1;i<=n;i++){ //i为边的编号
cin>>x>>y>>k;
add(x,y,k);
add(y,x,k); //无向图需要
}
//依次对每个顶点访问
for(int i=1;i<=m;i++){
for(int j=head[i];j ;j=next[j]){
cout<"<
（3）链式前向星存图法：
3.图的深度优先搜索(dfs)
注：欧拉回路有0个奇点，欧拉路有2个奇点（起点是一个奇点，终点是另一个奇点）！
1341：【例题】一笔画问题
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 14352 通过数: 5157
【题目描述】
如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。
根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行dfs，时间复杂度为O(m+n)，m为边数，n是点数。
【输入】
第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。
【输出】
欧拉路或欧拉回路,输出一条路径即可。
【输入样例】
5 5
1 2
2 3
3 4
4 5
5 1
【输出样例】
1 5 4 3 2 1
题解：
#include //欧拉路2个奇点，欧拉回路0个奇点
#define maxn 1002
using namespace std;
int n,m,a[maxn][maxn],vis[maxn],p[maxn],t=0;
void dfs(int i){
vis[++t]=i;
for(int j=1;j<=n;j++){
if(a[i][j]){
a[i][j]=0,a[j][i]=0; //删除已走边
dfs(j);
}
}
}
int main(){
cin>>n>>m;
for(int x,y,i=1;i<=m;i++){
cin>>x>>y;
a[x][y]=1;
a[y][x]=1;
p[x]++;
p[y]++;
}
int flag=1;
for(int i=1;i<=n;i++){ //找奇点
if(p[i]%2){
flag=0;
dfs(i);
break;
}
}
if(flag) dfs(1);
for(int i=1;i<=t;i++) cout<
1375：骑马修栅栏(fence)
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 10644 通过数: 3109
【题目描述】
农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。
John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。
每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(≥1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。
你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个 (也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的，等等)。 输入数据保证至少有一个解。
【输入】
第1行:一个整数F(1≤F≤1024)，表示栅栏的数目;
第2到F+1行:每行两个整数i,j(1≤=i,j≤500)表示这条栅栏连接i与j号顶点。
【输出】
输出应当有F+1行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。
【输入样例】
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6
【输出样例】
1
2
3
4
2
5
4
6
5
7
题解：
分析：和一笔画问题有一点点不一样，需要回溯记录路径，两点之间的栅栏不一定只有一个 。
#include
#include
#define maxn 1030
using namespace std;
int n,a[maxn][maxn],mx,mn=1000,vis[maxn],s,p[maxn];
void dfs(int x){
for(int i=mn;i<=mx;i++){
if(a[x][i]){
a[x][i]--,a[i][x]--;
dfs(i);
}
}
p[++s]=x; //需要回溯记录路径 ！！！
}
int main(){
cin>>n;
for(int x,y,i=1;i<=n;i++){
cin>>x>>y;
//两点之间的栅栏不一定只有一个 ！！！
a[x][y]++;
a[y][x]++;
mx=max(mx,max(x,y));
mn=min(mn,min(x,y));
vis[x]++,vis[y]++;
}
int flag=1;
for(int i=mn;i<=mx;i++){
if(vis[i]%2){
flag=0;
dfs(i);
break;
}
}
if(flag) dfs(mn);
for(int i=s;i>0;i--){
cout<
4.图的广度优先搜索（bfs）
5.最短路径（详细文章）
（1）Floyd算法（求多源最短路）
1342：【例4-1】最短路径问题
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 16583 通过数: 7507
【题目描述】
平面上有n个点（n<=100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。
若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
【输入】
共n+m+3行，其中:
第一行为整数n。
第2行到第n+1行（共n行） ，每行两个整数x和y，描述了一个点的坐标。
第n+2行为一个整数m，表示图中连线的个数。
此后的m 行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。
最后一行：两个整数s和t，分别表示源点和目标点。
【输出】
一行，一个实数（保留两位小数），表示从s到t的最短路径长度。
【输入样例】
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
【输出样例】
3.41
题解：
#include
#include
#include
#include
#define maxn 1000000
using namespace std;
int n,x[102],y[102],m,s,t;
double g[102][102];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
for(int j=1;j<=n;j++) g[i][j]=maxn;
} //memset(g,0x7f,sizeof g);
cin>>m;
for(int a,b,t1,t2,i=1;i<=m;i++){
cin>>a>>b;
t1=x[a]-x[b];
t2=y[a]-y[b];
g[a][b]=sqrt(1.0*t1*t1+1.0*t2*t2);
g[b][a]=g[a][b];
}
cin>>s>>t;
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(k!=i&&k!=j&&i!=j)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
}
}
printf("%.2lf",g[s][t]);
return 0;
}
（2）Dijkstra算法（主要求单源最短路） 详细文章
1381：城市路(Dijkstra)
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 14709 通过数: 4666
【题目描述】
罗老师被邀请参加一个舞会，是在城市n，而罗老师当前所处的城市为1,附近还有很多城市2~n-1，有些城市之间没有直接相连的路，有些城市之间有直接相连的路，这些路都是双向的，当然也可能有多条。
现在给出直接相邻城市的路长度，罗老师想知道从城市1到城市n，最短多少距离。
【输入】
输入n, m，表示n个城市和m条路;
接下来m行，每行a b c， 表示城市a与城市b有长度为c的路。
【输出】
输出1到n的最短路。如果1到达不了n，就输出-1。
【输入样例】
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
【输出样例】
90
【提示】
【数据规模和约定】
1≤n≤2000
1≤m≤10000
0≤c≤10000
题解：
#include
#define maxn 10000000
using namespace std;
int n,m,g[2003][2003],dp[2003],vis[2003];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) g[i][j]=maxn;
}
for(int a,b,c,i=1;i<=m;i++){
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
g[b][a]=g[a][b];
}
for(int i=1;i<=n;i++) dp[i]=g[1][i];
vis[1]=1;
for(int i=1;i
（3）Bellman－Ford算法
（4）SPFA算法
6.并查集
7.最小生成树相关算法
8.拓扑排序
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）