【文件属性】:
文件名称:图的两种遍历
文件大小:5KB
文件格式:CPP
更新时间:2018-02-05 14:56:49
图的两种遍历
void CreateGraph Graph graph 图的创建图
{
ENode p q e;
int i;
cout<<"请输入连通无向图的顶点数和边数 例如 3 3: n";
scanf "%d %d" &graph >numberOfVerts &graph >numberOfEerts ;
for i 1;i< graph >numberOfVerts;i++
{
cout<<"请输入第"<<i<<"个顶点的信息: n";
cin>>graph >amlist [i] data;
graph >amlist [i] number i;
graph >amlist[i] firstedge NULL;
graph >amlist [i] mark 0;
}
for i 1;i< graph >numberOfEerts;i++
{
p ENode malloc sizeof ENode ;
cout<<"请输入每条边的信息(编号小的在前 例如1 3回车1 2回车2 3) n";
cin>>p >ivex>>p >jvex;
p >ilink p >jlink NULL;
if graph >amlist [p >ivex ] firstedge NULL
graph >amlist [p >ivex ] firstedge p;
else
{
q graph >amlist [p >ivex ] firstedge ;
while q NULL
{
e q;
if q >ivex p >ivex
q q >ilink ;
else
q q >jlink ;
}
if e >ivex p >ivex
e >ilink p;
else
e >jlink p;
}
if graph >amlist [p >jvex ] firstedge NULL
graph >amlist [p >jvex ] firstedge p;
else
{
q graph >amlist [p >jvex ] firstedge ;
while q NULL
{
e q;
if q >ivex p >ivex
q q >ilink ;
else
q q >jlink ;
}
if e >ivex p >ivex
e >ilink p;
else
e >jlink p;
}
}
}
void SetMark Graph graph 设置访问标记
{
int i;
for i 1;i< graph >numberOfVerts ;i++
graph >amlist [i] mark 0;
}
void DFS Graph graph int v 深度遍历
{
ENode p;
cout<<v<<" ";
graph >amlist [v] mark 1;
p graph >amlist [v] firstedge ;
while p NULL
{
if p >ivex v
{
if graph >amlist [p >jvex ] mark 0
{
cout<<"<"<<p >ivex<<" "<<p >jvex<<">"<<endl;
DFS graph p >jvex ;
}
p p >ilink ;
}
else
{
if graph >amlist [p >ivex] mark 0
{
cout<<"<"<<p >jvex<<" "<<p >ivex<<">"<<endl;
DFS graph p >ivex ;
}
p p >jlink ;
}
}
}">void CreateGraph Graph graph 图的创建图
{
ENode p q e;
int i;
cout<<"请输入连通无向图的顶点数和边数 例如 3 3: n";
scanf "%d %d" &graph >numberOfVerts &graph >numberOfEerts ;
for i 1;i< graph >numberOfVerts;i++
{
cou [更多]