(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条)