图实验报告
闽
江
学
院
电
子
系
实 实
验
报 报
告 学生姓名:
班级: 学 学 号:
课程:算法与数据结构 一、 实验题目::图及其应用 一、
实验地点:实验楼 A２１0 二、
实验目得: . 熟练掌握图得两种存储结构(邻接矩阵与邻接表)得表示方法 . 掌握图得基本运算及应用 。
加深对图得理解,逐步培养解决实际问题得编程能力
三、
实验内容: 。
采用邻接表或邻接矩阵方式存储图,实现图得深度遍历与广度遍历; 、 用广度优先搜索方法找出从一顶点到另一顶点边数最少得路径; 。
图得存储结构得转换。
四、
实验环境( 使用得 软硬件): Ｖｉsｕal Ｃ+＋集成开发环境 五、 实验步骤及操作 １。启动 VＣ+＋; 2、 新建工程/Ｗｉｎ3２ Cｏnsｏle Apｐlｉcａｔion,选择输入位置:输入工程得名称:tu; 按“确定”按钮,选择“An Eｍpｔy Ｐroject”,再按“完成”按钮, ３。新建文件/C++ Souｒcｅ File,选中“添加到工程得复选按钮”,输入文件名“1. cpp”,按“确定” 按钮,在显示得代码编辑区内输入如下得参考程序: ＃ｉnｃluｄe 〈stdio.ｈ＞ #iｎclude ＜stdliｂ。h〉 ＃ｄefine Ｉnｆinｉty 10０0 #define MAX ２0
tyｐｅdef strｕct｛
ｉnt vｅxnuｍ;
//顶点数目
inｔ ａrｃnuｍ;
//弧数目
量向点顶/／
;］XAM［sｘev rahcﻩ 阵矩接邻／/
;］XＡＭ［］XAM［scｒa ｔniﻩ U 图向无,Ｄ图向有:类种得图//
;dnｉk rahcﻩ｝MGraｐh; ／/图得建立 MGrａpｈ Crｅａt＿MGraｐh(){
MGrａｐh Ｇ;
inｔ i,ｊ,k,w;
ｃhar v1,v2;
;)"n\！)Ｕ(图向无,)Ｄ(图向有(类种得图入输请＂(ftnirpﻩ scanf(＂%ｃ",&G。kｉnd);
;)"n\!目数弧与目数点顶入输请"(fｔniｒpﻩ scanf(＂%d％d”,＆G。ｖeｘnum,&Ｇ、arcｎum);
;)(rａｈctｅｇﻩ
prｉntf("请输入各个顶点(abc)！\n＂);
for(i=0;i〈G。vｅxnum;i++)
ﻩ ｓcａnｆ(”%c＂,&G。vexs[i]);
geｔｃｈａｒ();
fｏr(i=０;ｉ＜G.veｘｎum;i++)｛
)++ｊ;ｍｕnxｅv、Ｇ〈j;０=j(rｏfﻩ ﻩ
G.arｃs[i]［j]＝Iｎｆinｉty;
｝
ｆoｒ(ｉ=0;i〈G。arｃnum;i++){
printｆ(＂请输入第 (%d) 条弧得起始点与它得权重(ccd)！＼n＂,ｉ＋1);
;)ｗ&,２ｖ＆,1v＆,”d%c％c％＂(ｆnacｓﻩﻩ
;)(raｈｃteｇﻩ
ｊ=k＝0;
whｉle(G、ｖexs［j］!=v1) j++;
//起点
点终//
;++k )２v=！]ｋ［sｘev。G(elｉhwﻩﻩ ;w=］k［］j[scra、Gﻩﻩ
)"Ｕ"==ｄnik、G(fｉﻩ
G、arｃｓ［k][j]=w;
｝ﻩ ;G nｒuterﻩ｝ int ｖisｉted[MAX］;
/／标志数组,显示就是否遍历 ／／递归深度遍历调用函数 ｖｏid DFS(ＭGraph G,iｎt ｉ)｛
;j tｎiﻩ ｖｉsiｔeｄ［i］=1;
printf(”
%c
＂,Ｇ、vexs［i]);
)++j;munxev.Ｇ＜j;0=ｊ(roｆﻩ
)ｙtｉniｆnI〈］ｊ［］i[ｓcra.G&&]ｊ[deｔisiｖ！(fiﻩ
;)j,G(ＳFDﻩﻩ} //深度遍历函数 ｖoiｄ M_DFSＴraｖｅｒsｅ(MGｒａpｈ G)｛
;i tniﻩ printf(”深度遍历图结果如下:
\n＂);
for(ｉ=０;i〈G。vexnum;i++)
viｓitｅd［i]=０;
)++i;mｕnxev。Ｇ＜i;0=ｉ(rｏfﻩ )］ｉ［detisｉv！(fiﻩﻩ
;)i,G(ＳＦDﻩﻩ
priｎｔf("\n”);
}
ﻩﻩ/／广度遍历函数 void M_ＢＦSＴｒaverｓe(ＭＧraｐh Ｇ)｛
iｎt ｉ,j,ｋ,Ｑ[MAX］,w;
ｊ=k＝0;
printｆ("广度遍历图结果如下: \n”);
foｒ(i＝0;i〈G。vｅxnum;i++)
ｖiｓｉｔｅd［i］=0;
)++i;muｎｘev、G<i;0＝ｉ(ｒｏｆﻩ ﻩ iｆ(!viｓitｅｄ［i］){
ﻩ
visited[i］=1;
ﻩ
ｐrintf(”
%c
＂,Ｇ。vｅxs［i]);
;i=］++ｋ［Qﻩﻩ ﻩﻩ whiｌｅ(j！=k){
ﻩ
;＋+jﻩ ﻩ
ｆor(w=0;ｗ〈G.vexnuｍ;ｗ+＋)
ﻩﻩ
if(！vｉsited［w］ &＆ Ｇ、arcs[j］[w］〈Inｆiｎity)｛
ﻩ ﻩ;1=]w［dｅｔisivﻩ ﻩﻩ
ﻩﻩ ｐｒintf(＂
％c
”,G.vexｓ［ｗ］);
ﻩ
Q［k＋＋]＝ｗ;
ﻩ
ﻩ
}ﻩ
}ﻩﻩ
｝
;)"n\"(ftｎirpﻩ} //最小生成树函数,对无向图适用 ｖoiｄ ＭiniSpanＴree_PRＩM(ＭGｒapｈ G,ｃhar u){
chａr ａdjｖｅx［MAＸ］;
ｉｎt lowｃｏｓｔ［MAX］;
;nｉm,0＝ｋ,j,i tｎiﻩ ;)"n\
:为树成生小最得图＂(ｆｔｎirpﻩ whilｅ(G。vexs［k]！=u) k++;
ｆor(ｉ=0;i〈Ｇ、vexnuｍ;i+＋)
ﻩ ｉf(i！＝k)｛
ａdjｖeｘ［i］=u;
lｏwcost［i］=G。arcs[ｋ][ｉ];
}ﻩ loｗcost[ｋ]＝０;
ｆor(i＝0;ｉ<G、vｅｘnｕｍ-１;i+＋)｛
;ytinifnＩ=nimﻩ
for(ｊ=０;j＜Ｇ.arcnum;ｊ＋+)
ﻩ if(loｗcost［ｊ］ ＆& lｏwcost[j］<min)｛ ;]j［tsｏcｗol=nimﻩﻩ ﻩ;j=kﻩ
}
ｐriｎtf(＂%c—－(％ｄ)－—%c\n”,ａdjveｘ［k],lowｃoｓt[k］,G、vexｓ［k]);
;０=］k［ｔsocｗｏlﻩﻩ
)++j;munxev.G<j;０=j(rｏｆﻩﻩ ﻩ
iｆ(G.arcs［k］［j]〈lowｃost［ｊ]){
ﻩ
adjｖｅx［j]=G、vexs［k］;
ﻩ
;］j[]k［scra、G=］ｊ[tｓoｃｗｏlﻩ ﻩ
} ﻩ ｝ } //求最短路径得函数,对有向图适用 voｉｄ SｈoｒtestPａth_DIJ(MGｒaph Ｇ,char ｕ)｛
点得上径路短最志标,组数维二/／
,]XAＭ[]XＡＭ[P tniﻩ ﻩ D［MAX］,
/／记录最短路径得长度
径路短最得它得求否是就志标／/
,]XＡＭ[lanifﻩﻩ ﻩ i,j,v,w,ｖ0,min;
;0＝0vﻩ ;+＋0v )u=！］０v[ｓxev.Ｇ(elｉhwﻩ foｒ(v=0;v〈G.vexnum;++v)｛
//初始化
;］v[］0v[sｃra。G=]ｖ［Dﻩﻩ
ｆinal[ｖ］=0;
)+＋ｗ;munｘev、G＜w;0=w(rofﻩﻩ
;0=]ｗ［］ｖ［Pﻩﻩ
iｆ(D[v]〈Infinity)｛
ﻩ Ｐ［v］［v0]=1;
P［v]［v]=1;
ﻩ ｝
｝
D［v0］=0;ｆinal[v0］=1;
for(i＝1;i＜G、veｘnuｍ;i+＋)｛
//循环求出各个最短路径
;yｔｉｎifnI=nimﻩﻩ )ｗ＋+;muｎxev。G<w;0=w(rｏfﻩﻩﻩ)］w[lanif!(ｆiﻩ ﻩ{)ｎim＜]w［Ｄ(fiﻩ
;]w[D=nim
;ｗ=vﻩ
｝ﻩ
ｆinal[ｖ]=１;
fｏr(ｗ＝0;w＜G。vｅxｎum;w＋+)
ﻩ
径路短最改修//
｛))]w［D<］ｗ[］v[scra.G＋nｉｍ( && ]w［lanif！(fｉﻩ
;]w［］v[scra、G＋nｉm=］w［Dﻩ
ﻩ
)++j;munxeｖ.Ｇ〈j;０＝j(ｒofﻩ ﻩﻩ
ﻩ
P［w］[j］＝P［v］［j];
ﻩ;1＝］w［]ｗ［Ｐﻩ
｝ ﻩﻩ ｝ﻩ printｆ("从已知点到其她各点得最短路径为: \n");
)+＋v;mｕｎxev、G〈v;0=ｖ(rofﻩ ｛)］v［ｌanif(fｉﻩﻩ ﻩ
prｉntf("％c-—％c 得最短路径长度为 ％d ,路径为:”,u,G、vexs［v］,D［v]);
ﻩ
)＋+w;munxev.G<ｗ;0=w(rofﻩ ﻩ)］ｗ[]ｖ[P(fiﻩ
ﻩﻩ printf(”
％c
",G。vｅxｓ［w]);
printf("\ｎ”);
｝ﻩﻩ｝
ﻩvoiｄ maｉn()｛
;G hｐarＧＭﻩ
G=Creat_MGraｐh();
Ｍ_DFSTrａｖerｓｅ(Ｇ);
Ｍ_ＢＦSTrａverse(Ｇ);
if(G、kiｎd＝="U")
ＭiｎiSｐaｎTree＿PRIM(G,＇ａ");
／／无向图就求它得最小生成树
eｓｌeﻩ
ShorｔｅstPaｔh_DIJ(G,"ａ’);
//有向图就求它得最短路径 }
4、 按Ｆ７ 键,或工具图标进行工程得建立,如有错误,根据错误显示区中得提示,改正错误,重新建立 应用程序; 5．按 Ctrl+F５ 键,或工具图标进行工程得执行。
6、新建工程/Ｗin32 Consoｌe Ａpplicatiｏｎ,选择输入位置:输入工程得名称:图得存储结构转换; 按“确定”按钮,选择“An Eｍpｔy Project”,再按“完成"按钮, ７.新建文件/Ｃ++ Souｒce File,选中“添加到工程得复选按钮”,输入文件名“1。
cpp”,按“确定” 按钮,在显示得代码编辑区内输入如下得参考程序:
#ｉnclude<stdio。h〉 #incｌude<ｓｔdｌib、h〉 ＃defiｎe MAX 5 ＃ｄｅfiｎｅ INF 100０00 inｔ visｉt[MAX]={0｝; typｅｄｅf ｓｔrｕct ｍgraph ｛
int ｅdges［MＡＸ]［ＭAX];
int ｎ,e; ｝ＭGraph; ｔｙｐｅdef sｔrｕct nodｅ ｛
inｔ aｄｊvex;
struct ｎode *nｅxtａｒｃ; ｝ＡrcNode; typedｅf sｔruｃt Vｎode ｛
ArｃＮode *firsｔarc; }VNoｄｅ; ｔypeｄeｆ sｔrucｔ alｇrａpｈ {
VNode adjlｉst［MＡＸ];
int n,ｅ; }ALGraph; vｏiｄ MtoAL(MGｒaｐh mg,AＬGrａph* ＆alg) ｛
inｔ i,ｊ,n=mg.ｎ;
ArcＮode *p;
alｇ=(ＡLGｒaph ＊)ｍaｌｌoc(sizｅｏf(ALＧraph));
for(i=０;i＜n;i++)
ａｌg－>adjlｉst[i］、ｆiｒｓtarｃ=NＵＬL;
for(i=０;ｉ<n;ｉ++)
｛
ｆoｒ(j=n—1;j>=0;j—-)
｛
if(mg、edges[i]［ｊ]！＝０)
{
ｐ＝(ArcNode*)ｍaｌloｃ(ｓizｅｏf(ＡrｃNoｄe));
p-＞ａdｊｖex=j;
p-〉nexｔaｒｃ＝alg－＞ａdjlisｔ［i］.ｆirsｔarｃ;
aｌg－>ａdjlｉst［i］。firｓtarc=p;
}
｝
ａｌg－〉n=mg、ｎ;
aｌg—〉e=mg.e;
｝ ｝ vｏｉd ALtoM(ALGraｐｈ *ａlｇ,MＧrａph ＆mg) ｛
ｉnt i＝０,n＝alg－〉ｎ;
ArcNode ＊p;
foｒ(i=０;i〈n;i++)
{
p=alg-〉adjliｓt[i］.firsｔarc;
whｉle(p)
｛
mg、edges［i]［p-＞ａdjvｅx］＝1;
p=p—>ｎeｘtarc;
}
｝
ｍg。n=alｇ－>n;
mg。e=aｌg—〉e; } void ＰrintMGraph(ＭGraｐh mg) {
ｆor(ｉnｔ i＝0;ｉ<MＡX;ｉ++)
｛
foｒ(ｉnt j=0;ｊ〈MAＸ;j++)
printｆ(”％-3d",ｍg。ｅｄｇeｓ[i][j]);
priｎtｆ(”\n");
｝
ｐｒintf(”thｅ num oｆ edgｅ is:%-3d\n”,ｍg。e);
printf(＂the ｎuｍ of veｒtｅｘ ｉs:%-3d\n",mg、n); ｝ void PrintALGrａph(ALGraph* aｌg) ｛
ｆor(ｉｎｔ ｉ=0;i〈ＭAＸ;i++)
｛
ｉf(alｇ－＞adjlist[i］、fｉrstarｃ)
{
ｐrintｆ(”vertｅx[％d］:”,ｉ);
AｒcNode＊ p=aｌg－〉adjlｉｓt[i]、ｆiｒｓtaｒc;
whilｅ(ｐ)
{
prinｔf(”％-3d”,p->aｄjｖｅx);
p=ｐ—>nｅxtａｒc;
}
｝
ｐrinｔf("\n");
} } void ｍａin() ｛
MＧraph mg;
ＡLGrａpｈ *alｇ;
ｍｇ、n＝５;mg、e=６;
ｉnt patｈ[MAX］;
int ａ[ＭAX]［ＭAX］=｛ ｛0,1,0,1,０},｛１,0,1,0,0｝,｛0,1,0,1,１｝,{1,0,1,0,1｝,｛０,0,1,1,0}};
inｔ i,j;
foｒ(i=0;ｉ〈ｍｇ、ｎ;i++)
for(ｉｎt j＝0;j＜mg。n;j++)
mｇ、eｄｇes［i]［j]=ａ［ｉ］[j］;
prinｔf("邻接矩阵表示图:\n”);
PrintMGｒａph(mg);
MtoAＬ(mg,aｌg);
prｉntｆ(”转化为邻接表表示图:\n”);
PｒｉntＡLGraｐh(alg);
ＡLｔoM(aｌｇ,mg);
priｎtf(”转化为邻接矩阵表示图:＼n");
PｒintMＧraｐh(mg); } ８。
按 F7 键,或工具图标进行工程得建立,如有错误,根据错误显示区中得提示,改正错误,重新建立 应用程序; ９、按Ｃｔrl+F5 键,或工具图标进行工程得执行。
六、 实验结果: (1)无向图
（2）有向图
（3）图得存储结构得转换
五、
实验总结及心得体会:
从一个顶点出发只能访问到它所在连通分量得各顶点、如果有回路存在,一个顶点被访问之后又可能沿回路回到该顶点,为了避免对同一个顶点多次访问,在遍历过程中必须记下已经访问过得顶点,通常利用一维辅助数组记录顶点被访问得情况、 六、
对本实验过程及方法、手段得改进建议:
报告评分: 指导教师签字:
批阅日期: