数据结构中图的全部操作Word下载.docx
- 文档编号:6022313
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:29
- 大小:21.91KB
数据结构中图的全部操作Word下载.docx
《数据结构中图的全部操作Word下载.docx》由会员分享,可在线阅读,更多相关《数据结构中图的全部操作Word下载.docx(29页珍藏版)》请在冰点文库上搜索。
i++)//遍历所有顶点
if(G.vexs[i]==v)
returntrue;
returnfalse;
}StatusCreatUDN(MGraph&
G)//构造无向网{inti,j,w;
charch;
VertexTypev1,v2;
StatusLocateVex(MGraphG,VertexTypev);
//函数声明cout<
<
"
输入顶点数,弧数:
endl;
cout<
输入顶点(字符型):
i++)//初始化邻接矩阵{for(j=0;
j<
j++){G.arcs[i][j].adj=MAX;
G.arcs[i][j].info=NULL;
}}
i++)//顶点信息{cout<
输入第"
i+1<
个顶点:
;
cin>
>
ch;
if(VexExist(G,ch))//判断是否存在{cout<
顶点输入有误!
"
v1>
v2;
cout<
输入弧的权值:
w;
if((i=LocateVex(G,v1))!
=-2)//
if((j=LocateVex(G,v2))!
=-2){G.arcs[i][j].adj=w;
//对弧写入权值
G.arcs[j][i].adj=w;
//对称弧赋值
k++;
continue;
};
顶点输入错误!
}returnOK;
}StatusLocateVex(MGraphG,VertexTypev)//若图中存在v,返回v在图中的位置{for(inti=0;
i++){if(v==G.vexs[i])
returni;
}return-2;
}//对无向图求每个顶点的度,或对有向图求每个顶点的入度和出度(5分)
StatusGetDegree(MGraphG,VertexTypev){inti=0;
intdegree=0;
i=LocateVex(G,v);
////若图中存在v,返回v在图中的位置if(i!
=-2)//如果存在
for(intj=0;
j++)
if(G.arcs[i][j].adj>
0)degree++;
if(i==-2){cout<
returnERROR;
}returndegree;
}//完成插入顶点和边(或弧)的功能(5分)
StatusInsertVex(MGraph&
G,VertexTypev)//{intk=G.vexnum;
if(G.vexnum<
MAX_VERTEX_NUM){G.vexs[k]=v;
G.vexnum++;
for(inti=0;
i++){G.arcs[k][i].adj=MAX;
图中插入顶点
G.arcs[k][i].info=NULL;
G.arcs[i][k].adj=MAX;
G.arcs[i][k].info=NULL;
}cout<
插入成功!
}returnERROR;
}StatusInsertArc(MGraph&
G,VertexTypev1,VertexTypev2)图中插入弧{intw,i,j;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
if(i!
=-2)
if(j!
{//cout<
G.arcs[i][j].adj=w;
G.arcs[j][i]=G.arcs[i][j];
returnOK;
输入有误,插入失败!
}//完成删除顶点和边(或弧)的功能(5分)
StatusDelVex(MGraph&
G,VertexTypev)//{inti,j;
=-2){for(j=0;
G.vexnum-i-1;
G.vexs[i+j]=G.vexs[i+j+1];
图中删除顶点//顶点的删除
if(i<
G.vexnum)//与顶点相关的弧的删除{for(j=0;
for(intk=0;
k<
k++){G.arcs[i+j][k].adj=G.arcs[i+j+1][k].adj;
G.arcs[i+j][k].info=G.arcs[i+j+1][k].info;
}for(j=0;
k++){G.arcs[k][i+j].adj=G.arcs[k][i+j+1].adj;
G.arcs[k][i+j].info=G.arcs[k][i+j+1].info;
}G.vexnum--;
}StatusDelArc(MGraph&
G,VertexTypev1,VertexTypev2)//删除弧{inti,j;
=-2){G.arcs[i][j].adj=MAX;
G.arcs[j][i].adj=MAX;
G.arcs[j][i].info=NULL;
删除成功!
}voidScanAll(MGraphG)//显示图的所有信息{inti;
图中顶点信息如下:
i++)
G.vexs[i]<
邻接矩阵如下:
setw
(5)<
矩阵:
G.vexs[i];
i++){cout<
(6)<
G.arcs[i][j].adj;
///////////////////////////////////////////////////////////////////////////////////////////////
//定义图的邻接多重表结构
typedefstructEbox{VisitIfmark;
//访问标志
intivex,jvex;
//该边依附的两个顶点位置
intweight;
structEbox*ilink,*jlink;
//分别指向依附这两个顶点的下一条边
InfoTypeinfo;
//弧信息指针
}Ebox;
typedefstructVexBox//顶点定义{VertexTypedata;
Ebox*firstedge;
//指向第一条依附该顶点的边
}VexBox;
typedefstruct//图定义{VexBoxvexes[MAX_VERTEX_NUM];
intvexnum,edgenum;
//无向图的当前顶点数和边数}UdGraph;
//////////////////////////////////////////////////////////////////////////////////////////////
//以邻接多重表创建无向网
StatusCreatUdGraph(UdGraph&
G){inti;
intm,n,w;
Ebox*p;
StatusUdGLocateVex(UdGraph&
G,VertexTypev);
//声明cout<
输入图顶点的个数和边的数目:
G.vexnum>
G.edgenum;
i++)//顶点信息的输入{cout<
顶点:
G.vexes[i].data;
G.vexes[i].firstedge=NULL;
}for(i=0;
i++)//边信息输入{
共"
G.edgenum<
条边"
条边:
输入权值:
if((m=UdGLocateVex(G,v1))!
if((n=UdGLocateVex(G,v2))!
=-2){p=(Ebox*)malloc(sizeof(Ebox));
if(!
p)returnERROR;
p->
ivex=m;
jvex=n;
weight=w;
ilink=G.vexes[m].firstedge;
//插入顶点m表头
G.vexes[m].firstedge=p;
jlink=G.vexes[n].firstedge;
//插入顶点n的表头
G.vexes[n].firstedge=p;
}StatusUdGLocateVex(UdGraph&
G,VertexTypev)//v在图G中的位置{for(inti=0;
i++){if(v==G.vexes[i].data)
}StatusUdGInsertVex(UdGraph&
G)//
{返回插入顶点if(G.vexnum<
MAX_VERTEX_NUM){cout<
输入要插入的顶点的信息:
G.vexes[G.vexnum].data;
G.vexes[G.vexnum-1].firstedge=NULL;
}StatusUdGInsertEadge(UdGraph&
G,VertexType
v2,intw)//插入边{intm,n;
m=UdGLocateVex(G,v1);
n=UdGLocateVex(G,v2);
if(m!
=-2)//如果点v1存在,并返回值给m
if(n!
{v1,VertexTypep=(Ebox*)malloc(sizeof(Ebox));
//申请一个结点
//
m表头
n的表头
边信息输入有误!
}StatusUdGGetDegree(UdGraphG,VertexTypev)//
度数
{插入顶点返回v的intdegree=0;
if((i=UdGLocateVex(G,v))==-2){cout<
输入的顶点信息有误!
}p=G.vexes[i].firstedge;
while(p){degree++;
if(p->
ivex==i)p=p->
ilink;
elsep=p->
jlink;
}StatusUdGFirstVex(UdGraphG,inti)//点{返回v的第一个邻接if(i>
G.vexnum||i<
0){cout<
输入的顶点有误!
}if(G.vexes[i].firstedge==NULL)return-2;
//接点
if(G.vexes[i].firstedge->
ivex==i)
G.vexes[i].firstedge->
jvex;
//返回邻接点
elsereturnG.vexes[i].firstedge->
ivex;
}//返回i相对于j的下一个邻接点
StatusUdGNextVex(UdGraphG,inti,intj){Ebox*p;
if(i>
0||j>
G.vexnum||j<
输入的两个顶点有误!
没有邻returnwhile(p){if(p->
ivex==j){p=p->
break;
}if(p->
jvex==j){p=p->
}if(!
p)return-2;
//没有邻接点
ivex==i)returnp->
elsereturnp->
}//邻接多重表转换为邻接矩阵
MGraphStructTransform(UdGraphG1){inti,j;
MGraphG;
G.vexnum=G
1.vexnum;
G
i++){G.vexs[i]=G
1.vexes[i].data;
//复制顶点数组}
i++)//初始化邻接矩阵for(j=0;
G.arcs[i][j].adj=MAX;
visited[i]=false;
//访问标记初始化
i++)//邻接矩阵赋值{p=G
1.vexes[i].firstedge;
while(p){G.arcs[p->
ivex][p->
jvex].adj=G.arcs[p->
jvex][p->
ivex].adj=p->
weight;
returnG;
}//邻接矩阵转换为邻接多重表
UdGraphStructTransform(MGraphG1){inti,j;
UdGraphG;
//顶点数组的复制
G.vexes[i].data=G
1.vexs[i];
//根据邻接矩阵构造边
for(j=i+1;
if(G
1.arcs[i][j].adj>
0)
UdGInsertEadge(G,G.vexes[i].data,G.vexes[j].data,G
1.arcs[i][j].adj);
}/********二叉树*******/
typedefstructCSNode{VertexTypev;
CSNode*lchild;
CSNode*nextsibling;
}CSNode,*CSTree;
//输出图的深度优先遍历序列或广度优先遍历序列(5分)StatusDFSTraverse(UdGraphG)//返回连通分量{inti;
intcount=0;
voidDFS(UdGraphG,inti);
//访问标志初始化cout<
深度优先遍历结果:
i++){if(!
visited[i]){count++;
//连通分量计数器DFS(G,i);
returncount;
}voidDFS(UdGraphG,inti){intw;
visited[i]=true;
for(w=UdGFirstVex(G,i);
w!
=-2;
w=UdGNextVex(G,i,w))if(!
visited[w])DFS(G,w);
}StatusScanUdGraph(UdGraphG)//输出无向网{inti;
图中顶点信息:
编号"
\t"
G.vexes[i].data<
i++){p=G.vexes[i].firstedge;
p){cout<
没有与该顶点相关的边"
与顶点"
相连的边:
while(p){cout<
ivex<
-"
jvex<
权值:
weight<
}//求图的深度优先或广度优先的生成树(或生成森林)(存储结构为孩子-兄弟链表),并对生成树进行遍历(15分)
//xx优先遍历生成树
voidDFSForest(UdGraphG,CSTree&
T){intv;
T=NULL;
CSTreep=NULL;
CSTreeq=NULL;
voidDFSTreeSet(UdGraphG,intv,CSTree&
T);
for(v=0;
v<
++v)
visited[v]=false;
visited[v]){p=(CSTree)malloc(sizeof(CSNode));
内存分配失败"
return;
}p->
v=G.vexes[v].data;
lchild=p->
nextsibling=NULL;
T)T=p;
elseq->
nextsibling=p;
q=p;
DFSTreeSet(G,v,p);
T){intw;
boolfirst;
visited[v]=true;
first=true;
CSTreep,q=T->
lchild;
for(w=UdGFirstVex(G,v);
w=UdGNextVex(G,v,w))if(!
visited[w]){p=(CSTree)malloc(sizeof(CSNode));
内存分配失败!
v=G.vexes[w].data;
if(first){T->
lchild=p;
first=false;
}else{q->
}q=p;
DFSTreeSet(G,w,q);
//xx优先遍历孩子兄弟链表
StatusDFSTree(CSTreeT){if(!
T)returnOK;
T->
if(T->
lchild)DFSTree(T->
lchild);
nextsibling)DFSTree(T->
nextsibling);
}//判断图中有没有环
boolUdGLoopJudge(UdGraphG){intVD[MAX_VERTEX_NUM];
boolflag=false;
//数组中点空标志
inti,j,m;
intcount;
//记录数组中为-1的数目
//VexDegreeVD[MAX_VEX_NUM];
i++)//保存顶点的度数VD[i]=UdGGetDegree(G,G.vexes[i].data);
while(!
flag){count=1;
for(j=0;
j++)//遍历数组检测度数为的点{
if(VD[j]==1){VD[j]=-1;
m=j;
}if(VD[j]==-1)count++;
if(j==G.vexnum-1)
m=-1;
}//cout<
-1点:
count<
if(m==-1){if(count==G.vexnum)break;
fl
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 全部 操作
![提示](https://static.bingdoc.com/images/bang_tan.gif)