代码
/*输入：先输入两个数，代表点的数量和边的数量，
再输入各个边，起点编号 >终点编号，编号从0开始
例子：
6 10
0 3
0 4
1 4
1 3
3 5
0 1
4 5
5 2
4 2
4 3
输出:
0 1 4 3 5 2
思路：
用vector建立邻接表
计算每个点的入度
如果是偏序无环的，一定存在入度为0的点，输出并且删除它，同时删除它出发的边，更新其他点的入度
循环直到移除所有点，输出顺序就是拓扑排序
*/
#include<iostream>
#include<vector>
using namespace std
int main() {
freopen("in.txt","r",stdin)//重定向输入流//in.txt 建在程序所在的文件夹里
int M,N
scanf("%d%d",&M,&N)//M个点，N条边
vector<int>maps[M]
int innode[M]={0}//入度
for(int i=0i<Ni++)
{
int tx,ty
scanf("%d%d",&tx,&ty)
maps[tx].push_back(ty)
++innode[ty]
}
for(int time=0time<Mtime++)
for(int i=0i<Mi++)
{
if(innode[i]==0)
{
printf("%d ",i)
for(vector<int>::iterator it = maps[i].begin()it != maps[i].end()++it)
{
--innode[*it]
}
innode[i]=-1
break
}
}
}
#define Infinity 1000#define MaxVertexNum 35
#define MAX 40
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
#include<iostream.h>
typedef struct arcell //边的权值信息
{
int adj //权值
}arcell,adjmatrix[MaxVertexNum][MaxVertexNum] //图的邻接矩阵类型
typedef struct vexsinfo //顶点信息
{
int position //景点的编号
char name[32] //景点的名称
char introduction[256]//景点的介绍
}vexsinfo
typedef struct mgraph //图结构信息
{
vexsinfo vexs[MaxVertexNum] //顶点向量(数组)
adjmatrix arcs//邻接矩阵
int vexnum,arcnum //分别指定顶点数和边数
}mgraph
//全局变量
int visited[35] //用于标志是否已经访问过
int d[35] //用于存放权值或存储路径顶点编号
mgraph campus//图变量(大学校园)
// (1) 对图初始化
mgraph initgraph()
{
int i=0,j=0
mgraph c
c.vexnum =28 //顶点个数
c.arcnum =39 //边的个数
for(i=0i<c.vexnum i++)//依次设置顶点编号
c.vexs[i].position =i
//依次输入顶点信息
strcpy(c.vexs[0].name ,"小西南门")
strcpy(c.vexs[0].introduction ,"离公交站近")
strcpy(c.vexs[1].name ,"学校南正门")
strcpy(c.vexs[1].introduction ,"学校大门、学校班车进出口")
strcpy(c.vexs[2].name ,"语言文化职业学院")
strcpy(c.vexs[2].introduction ,"语言文化职业学院办公楼，楼高6层")
strcpy(c.vexs[3].name ,"艺术学院")
strcpy(c.vexs[3].introduction ,"音乐系、美术系，楼高4层")
strcpy(c.vexs[4].name ,"行政楼")
strcpy(c.vexs[4].introduction ,"行政办公大楼，楼高5层")
strcpy(c.vexs[5].name,"文学院")
strcpy(c.vexs[5].introduction ,"文学院，楼高6层")
strcpy(c.vexs[6].name ,"体育场")
strcpy(c.vexs[6].introduction ,"室外标准田径场")
strcpy(c.vexs[7].name,"教育科学学院")
strcpy(c.vexs[7].introduction ,"教心系、经管系，楼高5层")
strcpy(c.vexs[8].name ,"南区学生宿舍")
strcpy(c.vexs[8].introduction ,"离西南门近")
strcpy(c.vexs[9].name, "数学与经济管理学院")
strcpy(c.vexs[9].introduction , "数学与经济管理学院大楼，楼高4层")
strcpy(c.vexs[10].name ,"中区学生宿舍")
strcpy(c.vexs[10].introduction ,"若干栋，离学生1、2食堂近")
strcpy(c.vexs[11].name ,"职业学院教学大楼")
strcpy(c.vexs[11].introduction ,"职业学院教学大楼，楼高5层")
strcpy(c.vexs[12].name ,"体育系")
strcpy(c.vexs[12].introduction ,"体育系，楼高5层")
strcpy(c.vexs[13].name ,"游泳馆")
strcpy(c.vexs[13].introduction ,"室内小型游泳馆")
strcpy(c.vexs[14].name ,"报告厅、阶梯教室")
strcpy(c.vexs[14].introduction ,"可举办中、大型学术会议。有大小报告厅1－6个、阶梯教室1－6个")
strcpy(c.vexs[15].name ,"大礼堂、体育馆")
strcpy(c.vexs[15].introduction ,"文艺演出所在地、室内运动场")
strcpy(c.vexs[16].name ,"1食堂")
strcpy(c.vexs[16].introduction ,"教工食堂及学生1食堂在此")
strcpy(c.vexs[17].name ,"新图书馆")
strcpy(c.vexs[17].introduction ,"建筑面积46000平方米")
strcpy(c.vexs[18].name ,"2食堂")
strcpy(c.vexs[18].introduction ,"学校东区，学生食堂")
strcpy(c.vexs[19].name ,"东区学生宿舍")
strcpy(c.vexs[19].introduction ,"离学生2食堂近")
strcpy(c.vexs[20].name ,"计算机学院")
strcpy(c.vexs[20].introduction ,"计算机学院大楼，楼高5层")
strcpy(c.vexs[21].name ,"教工宿舍")
strcpy(c.vexs[21].introduction ,"学校青年教职工租住地")
strcpy(c.vexs[22].name ,"西区学生宿舍")
strcpy(c.vexs[22].introduction ,"离学生3、4食堂近")
strcpy(c.vexs[23].name ,"3食堂")
strcpy(c.vexs[23].introduction ,"学校西区，学生食堂")
strcpy(c.vexs[24].name ,"外国语学院")
strcpy(c.vexs[24].introduction ,"外国语学院大楼，楼高5层")
strcpy(c.vexs[25].name ,"4食堂")
strcpy(c.vexs[25].introduction ,"学校西区，学生食堂，人气较高")
strcpy(c.vexs[26].name ,"校医院")
strcpy(c.vexs[26].introduction ,"看小病的地方")
strcpy(c.vexs[27].name ,"实验楼")
strcpy(c.vexs[27].introduction ,"物电学院、化学与生命科学学院、机电系、建材系所在地，机房及多媒体教室若干")
//依次输入边上的权值信息
for(i=0i<c.vexnum i++)
for(j=0j<c.vexnum j++)
c.arcs [i][j].adj =Infinity//先初始化图的邻接矩阵
//部分弧长
c.arcs[0][2].adj=50 c.arcs[0][3].adj=60
c.arcs[1][4].adj=90
c.arcs[2][3].adj=60 c.arcs[2][8].adj=40
c.arcs[3][4].adj=60 c.arcs[3][6].adj=40
c.arcs[4][5].adj=70 c.arcs[4][9].adj=70 c.arcs[4][10].adj=80 c.arcs[4][17].adj=200
c.arcs[5][7].adj=70
c.arcs[6][9].adj=40
c.arcs[7][18].adj=190
c.arcs[8][11].adj=50
c.arcs[9][12].adj=40
c.arcs[10][18].adj=70
c.arcs[11][12].adj=60 c.arcs[11][14].adj=50 c.arcs[11][15].adj=50
c.arcs[12][16].adj=50
c.arcs[13][14].adj=40 c.arcs[13][22].adj=60
c.arcs[14][15].adj=50 c.arcs[14][20].adj=90
c.arcs[15][16].adj=60 c.arcs[15][21].adj=40
c.arcs[16][17].adj=60
c.arcs[17][18].adj=80
c.arcs[18][19].adj=60
c.arcs[20][21].adj=60 c.arcs[20][24].adj=80
c.arcs[22][23].adj=60 c.arcs[22][25].adj=80
c.arcs[23][24].adj=60
c.arcs[24][26].adj=100 c.arcs[24][27].adj=100
c.arcs[25][26].adj=90
c.arcs[26][27].adj=90
for(i=0i<c.vexnum i++) //邻接矩阵是对称矩阵，对称赋值
for(j=0j<c.vexnum j++)
c.arcs[j][i].adj =c.arcs[i][j].adj
return c
}//initgraph
// (2) 查找景点在图中的序号
int locatevex(mgraph c,int v)
{
int i
for(i=0i<c.vexnum i++)
if(v==c.vexs[i].position)
return i //找到，返回顶点序号i
return -1 //否则，返回-1
}
//(3) 、(4) 求两景点间的所有路径
// (3) 打印序号为m,n景点间的长度不超过8个景点的路径
void path(mgraph c, int m,int n,int k)
{
int s,x=0
int t=k+1 //t 记载路径上下一个中间顶点在d[]数组中的下标
if(d[k]==n &&k<8) //d[k]存储路径顶点。若d[k]是终点n且景点个数<=8，则输出该路径
{ //递归出口，找到一条路径
for(s=0s<ks++)
printf("%s--->",c.vexs[d[s]].name)//输出该路径。s=0 时为起点m
printf("%s",c.vexs[d[s]].name) //输出最后一个景点名(即顶点n的名字，此时s==k)
printf("\n\n")
}
else
{
s=0
while(s<c.vexnum) //从第m个顶点，试探至所有顶点是否有路径
{
if((c.arcs[d[k]][s].adj<Infinity) &&(visited[s]==0)) //初态：顶点m到顶点s有边，且未被访问
{
visited[s]=1
d[k+1]=s //存储顶点编号s 至d[k+1]中
path(c,m,n,t) //求从下标为t=k+1的第d[t]个顶点开始的路径(递归调用)，同时打印出一条m至n的路径
visited[s]=0 //将找到的路径上顶点的访问标志重新设置为0，以用于试探新的路径
}
s++ //试探从下一个顶点 s 开始是否有到终点的路径
}//endwhile
}//endelse
}//endpath
//(4) 打印两景点间的景点个数不超过8的所有路径。调用(3)
int allpath(mgraph c)
{
int k,i,j,m,n
printf("\n\n请输入你要查询的两个景点编号:\n\n")
scanf("%d%d",&i,&j)
printf("\n\n")
m=locatevex(c,i)//调用(2)，确定该顶点是否存在。若存在，返回该顶点编号
n=locatevex(c,j)
d[0]=m //存储路径起点m (int d[]数组是全局变量)
for(k=0k<c.vexnumk++) //全部顶点访问标志初值设为0
visited[k]=0
visited[m]=1//第m个顶点访问标志设置为1
path(c,m,n,0) //调用(3)。k=0，对应起点d[0]==m。k为d[]数组下标
return 1
}
// (5) 用迪杰斯特拉算法，求出一个景点到其他景点间的最短路径，并打印
void shortestpath_dij(mgraph c)
{
//迪杰斯特拉算法，求从顶点v0到其余顶点的最短路经及其带权长度d[v]
//若p[v][w]为1，则w是从v0到v的最短路经上的顶点
//final[v]类型用于设置访问标志
int v,w,i,min,t=0,x,flag=1,v0 //vo为起始景点的编号
int final[35],d[35],p[35][35]
printf("\n请输入一个起始景点的编号：")
scanf("%d",&v0)
printf("\n\n")
while(v0<0||v0>c.vexnum)
{
printf("\n你所输入的景点编号不存在\n")
printf("请重新输入：")
scanf("%d",&v0)
}//while
for(v=0v<c.vexnum v++)
{
final[v]=0 //初始化各顶点访问标志
d[v]=c.arcs[v0][v].adj //v0 到各顶点 v 的权值赋值给d[v]
for(w=0w<c.vexnum w++) //初始化p[][]数组，各顶点间的路径全部设置为空路径0
p[v][w]=0
if(d[v]<Infinity) //v0 到v 有边相连，修改p[v][v0]的值为1
{
p[v][v0]=1
p[v][v]=1 //各顶点自己到自己要连通
}
}//for
d[v0]=0 //自己到自己的权值设为0
final[v0]=1 //v0的访问标志设为1，v 属于 s 集
for(i=1i<c.vexnum i++) //对其余c.vexnum-1个顶点w，依次求 v 到 w 的最短路径
{
min=Infinity
for(w=0w<c.vexnum w++) //在未被访问的顶点中，查找与 v0 最近的顶点v
if(!final[w])
if(d[w]<min) //v0 到 w (有边)的权值<min
{
v=w
min=d[w]
}//if
final[v]=1 //v 的访问标志设置为1，v 属于s集
for(w=0w<c.vexnum w++) //修改v0 到其余各顶点w 的最短路径权值d[w]
if(!final[w]&&(min+c.arcs[v][w].adj <d[w])) //若w 不属于s，且v 到w 有边相连
{
d[w]=min+c.arcs[v][w].adj //修改v0 到w 的权值d[w]
for(x=0x<c.vexnum x++) //所有v0 到v 的最短路径上的顶点x，都是v0 到w 的最短路径上的顶点
p[w][x]=p[v][x]
p[w][w]=1
}//if
}//for
for(v=0v<c.vexnum v++) //输出v0 到其它顶点v 的最短路径
{
if(v!=v0)
printf("%s",c.vexs[v0].name) //输出景点v0 的景点名
for(w=0w<c.vexnum w++) //对图中每个顶点w，试探w 是否是v0 到v 的最短路径上的顶点
{
if(p[v][w] &&w!=v0 &&w!=v) //若w 是且w 不等于v0，则输出该景点
printf("--->%s",c.vexs[w].name)
}
printf("---->%s",c.vexs[v].name)
printf("\n总路线长为%d米\n\n",d[v])
}//for
}//shortestpath
//(6)-(11)修改图的信息。包括建图、更新信息、删除、增加结点和边
//(6) 构造图的邻接矩阵
int creatgragh(mgraph &c) //建图。以图的邻接矩阵存储图
{
int i,j,m,n
int v0,v1
int distance
printf("请输入图的顶点数和边数: \n")
scanf("%d %d",&c.vexnum ,&c.arcnum )
printf("下面请输入景点的信息：\n")
for(i=0i<c.vexnum i++) //构造顶点向量(数组)
{
printf("请输入景点的编号：")
scanf("%d",c.vexs[i].position )
printf("\n请输入景点的名称：")
scanf("%s",c.vexs[i].name )
printf("\n请输入景点的简介：")
scanf("%s",c.vexs[i].introduction )
}
for(i=0i<c.arcnum i++) //初始化邻接矩阵
for(j=0j<c.arcnum j++)
c.arcs[i][j].adj =Infinity
printf("下面请输入图的边的信息：\n")
for(i=1i<=c.arcnum i++) //构造邻接矩阵
{
printf("\n第%d条边的起点 终点 长度为：",i)//输入一条边的起点、终点及权值
scanf("%d %d %d",&v0,&v1,&distance)
m=locatevex(c,v0)
n=locatevex(c,v1)
if(m>=0 &&n>=0)
{
c.arcs[m][n].adj =distance
c.arcs[n][m].adj =c.arcs[m][n].adj
}
}
return 1
}//creatgragh
// (7) 更新图的部分信息。返回值: 1
int newgraph(mgraph &c)
{
int changenum //计数。用于记录要修改的对象的个数
int i,m,n,t,distance,v0,v1
printf("\n下面请输入你要修改的景点的个数：\n")
scanf("%d",&changenum)
while(changenum<0||changenum>c.vexnum )
{
printf("\n输入错误！请重新输入")
scanf("%d",&changenum)
}
for(i=0i<changenumi++)
{
printf("\n请输入景点的编号：")
scanf("%d",&m)
t=locatevex(c,m)
printf("\n请输入景点的名称：")
scanf("%s",c.vexs[t].name )
printf("\n请输入景点的简介：")
scanf("%s",c.vexs[t].introduction )
}
printf("\n下面请输入你要更新的边数")
scanf("%d",&changenum)
while(changenum<0||changenum>c.arcnum )
{
printf("\n输入错误！请重新输入")
scanf("%d",&changenum)
}
printf("\n下面请输入更新边的信息：\n")
for(i=1i<=changenum i++)
{
printf("\n修改的第%d条边的起点 终点 长度为：",i)
scanf("%d %d %d",&v0,&v1,&distance)
m=locatevex(c,v0)
n=locatevex(c,v1)
if(m>=0&&n>=0)
{
c.arcs[m][n].adj =distance
c.arcs[n][m].adj =c.arcs[m][n].adj
}
}
return 1
}//newgraph
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）