图的邻接表存储结构实验报告Word下载.doc
- 文档编号:7010002
- 上传时间:2023-05-07
- 格式:DOC
- 页数:9
- 大小:183KB
图的邻接表存储结构实验报告Word下载.doc
《图的邻接表存储结构实验报告Word下载.doc》由会员分享,可在线阅读,更多相关《图的邻接表存储结构实验报告Word下载.doc(9页珍藏版)》请在冰点文库上搜索。
根据序号求节点值
选择操作菜单
求第一、二个邻接点的序号
深度遍历
广度遍历
4.函数的功能
1)建立无向邻接表
GraphCreate1()//建立无向邻接表
{
GraphG;
inti,j,k;
node*s;
G=malloc(M*sizeof(vnode));
printf("
输入图的顶点数和边数:
"
);
scanf("
%d%d"
&
G->
v,&
e);
//读入顶点数和边数
for(i=0;
i<
v;
i++)//建立顶点表
{ printf("
请输入图第%d个元素:
i+1);
scanf("
%s"
List[i].name);
//读入顶点信息
G->
List[i].fnext=NULL;
//边表置为空表
}
for(k=0;
k<
e;
k++)//建立边表--建立了2倍边的结点
{ printf("
请输入边的两顶点序号:
(从0考试)"
i,&
j);
//读入边(Vi,Vj)的顶点对序号
s=(node*)malloc(sizeof(node));
//生成边表结点
s->
adj=j;
next=G->
List[i].fnext;
List[i].fnext=s;
//将新结点*s插入顶点Vi的边表头部
adj=i;
//邻接点序号为i
List[j].fnext;
List[j].fnext=s;
//将新结点*s插入顶点Vj的边表头部
}
returnG;
}
2)建立有向邻接图
GraphCreate2() //有向邻接图
{
node*q;
请输入顶点数和弧数:
for(i=0;
i++)//建立有n个顶点的顶点表
请输入图第%d个元素:
//读入顶点信息
for(k=0;
k++)//建立边表
请输入两顶点的序号:
(从0开始)"
q=(node*)malloc(sizeof(node));
//生成新边表结点s
q->
//邻接点序号为j
List[i].fnext=q;
returnG;
3)输出无向图的邻接表
voidPrint1(GraphG)//输出无向图的邻接表
inti;
node*p;
\n\t\t\t邻接表\n"
for(i=0;
i++)
{ p=G->
printf("
\t\t\t%d|%3s"
i,G->
while(p)
{printf("
->
%d"
p->
adj);
p=p->
next;
\n"
4)输出个元素的度数
voidDu(GraphG)//输出各元素的度数
inti,j;
\n\t\t\t各点度数\n"
\t\t\t顶点%2s的度为:
G->
j=0;
{ j++;
p=p->
%d\n"
j);
5)返回图结点在的序号
intLocateVex(GraphG,char*u)
{//初始条件:
图G存在,u和G中顶点有相同的特征
//操作结果:
若G中存在顶点u,则返回该顶点在图中的位置;
否则返回-1
++i)
if(strcmp(u,G->
List[i].name)==0)
returni;
return-1;
6)返回序号为v的图结点的值
char*VertexGet(GraphG,intv)
if(v>
=G->
v||v<
0)
exit(0);
returnG->
List[v].name;
7)返回图结点v的第一个邻接顶点的序号
intFirstAdjVex(GraphG,char*v)
图G存在,v是G中的某个顶点
返回v中第一个邻接顶点的序号。
若顶点在G中没有邻接顶点
//则返回-1
intv1;
v1=LocateVex(G,v);
p=G->
List[v1].fnext;
if(p)
returnp->
adj;
else
return-1;
8)找到图结点v的第二个邻接顶点的序号
voidNextAdjVex(GraphG,char*v,char*w)
图G存在,v是G中某个顶点,w是v得邻接点
//操作结果:
输出v的(相对于w的)下一个邻接点的序号
intv1,w1;
w1=LocateVex(G,w);
while(p&
&
p->
adj!
=w1)
if(!
p||!
next)
没有第二个邻接点!
第二个邻接点序号是:
next->
9)深度优先遍历图
voidDFS(GraphG,inti,intflag[])
%2s"
flag[i]=1;
while(p)
{
if(!
flag[p->
adj])
DFS(G,p->
adj,flag);
voidDFSTravel(GraphG)//深度优先遍历
intflag[M];
//标志数组
flag[i]=0;
flag[i])
DFS(G,i,flag);
10)广度优先遍历
voidBFSTravel(GraphG)//广度优先遍历
{ QueueQ;
inti,j=0;
Q=malloc(sizeof(M));
InitQueue(Q);
if(flag[i]==0)//此点未被访问
{
flag[i]=1;
printf("
Enter(Q,i);
while(Q->
front!
=Q->
rear)
{
Leave(Q,j);
//队头元素出队并置为j
p=G->
while(p!
=NULL)
{ if(flag[p->
adj]==0)
{
printf("
List[p->
adj].name);
flag[p->
adj]=1;
Enter(Q,p->
}//if
p=p->
}//while
}//while
}//if
5.输入/输出数据
1)选择操作
2)选择“1”
然后输入“33”
输入“a”,“b”,“c”
输入“01”,“12”,“20”
3)选择“2”跟选择“1”类似
4)选择“3”
5)选择“4”
输入“1”
6)选择“5”
输入“a”
7)选择“6”
8)选择“7”
9)选择“0”
6.总结
此次实验要求熟练掌握关于图的各项基本操作,重点在利用邻接表存储图的结构,以及深度、广度优先遍历图的方法。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 邻接 存储 结构 实验 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)