主题：[讨论]求教 关于图的遍历
lixuantea
[专家分：0] 发布于 2006-04-20 22:12:00
程序是用VC＋＋编的，只能执行n-1个节点，到第n个节点时就出错，其中构造邻接多重表的部分如下
void CreateGraph(int n,amlgraph &G)//构造邻接多重表
{
pebox p1,p2;
int i,j,k,m;
int mark;
initgraph(G,n);
printf("请输入边的数量:");
scanf("%d",&m);
for(k=0;k<m;k++)
{
printf("请输入第%d条边的两个顶点:",k+1);
scanf("%d%d",&i,&j);
p1=(pebox)malloc(sizeof(ebox));
p1->ivex=i;
p1->jvex=j;
p1->ilink=NULL;
p1->jlink=NULL;
p2=G.adjmulist[i].firstedge;
if(p2==NULL)
G.adjmulist[i].firstedge=p1;
else
{
mark=0;
while(mark==0)
{
if(p2->ivex==i && p2->ilink==NULL) mark=1;
else if(p2->jvex==i && p2->jlink==NULL) mark=2;
else if(p2->ivex==i) p2=p2->ilink;
else p2=p2->jlink;
}
if(mark==1) p2->ilink=p1;
else p2->jlink=p1;
}
p2=G.adjmulist[j].firstedge;
if(p2==NULL)
G.adjmulist[j].firstedge=p1;
else
{
mark=0;
while(mark==0)
{
[color=FF0000]if(p2->ivex==j && p2->ilink==NULL) mark=1;[/color] else if(p2->jvex==j && p2->jlink==NULL) mark=2;
else if(p2->ivex==j) p2=p2->ilink;
else p2=p2->jlink;
}
if(mark==1) p2->ilink=p1;
else p2->jlink=p1;
}
}
}
只要输入最后一个节点就出错，调试显示是if(p2->ivex==i && p2->ilink==NULL) mark=1这句出错，哪位高人指点一二
回复列表 （共17个回复）
11 楼
lt19870917 [专家分：750] 发布于 2006-05-09 12:53:00
//访问函数
void f(VexNode v)
{
printf("%c ",v.data);
}
void DFS(ALGraph g,VexNode v,bool visit[])//同时可以得到连通分量
{
int spot,stack[max_vertex_num],top=-1;
spot=LocateVex(g,v);
do{
if(!visit[spot]){
f(g.vertices[spot]);
visit[spot]=true;
top++;
stack[top]=spot;
}
for(spot=FirstAdjVex(g,v);spot>=0;spot=NextAdjVex(g,v,g.vertices[spot])){
if(!visit[spot])
break;
}
if(spot>=0){
v=g.vertices[spot];
continue;
}
else{
top--;
if(top!=-1)
spot=stack[top];
}
}while(top!=-1);
}
//深度优先搜索
void DFSTraverse(ALGraph g)
{
bool visit[max_vertex_num];
int i;
for(i=0;i<max_vertex_num;i++)
visit[i]=false;
for(i=0;i<g.vexnum;i++){
if(!visit[i]) DFS(g,g.vertices[i],visit);
}
}
//可一得到连通分量
void BFS(ALGraph g,VexNode v,bool visit[])
{
int spot,front=-1,rear=-1,queue[max_vertex_num];
spot=LocateVex(g,v);
f(v);
visit[spot]=true;
do{
for(spot=FirstAdjVex(g,v);spot>=0;spot=NextAdjVex(g,v,g.vertices[spot])){
if(!visit[spot]){
f(g.vertices[spot]);
visit[spot]=true;
rear=(rear+1)%max_vertex_num;
queue[rear]=spot;
}
}
front=(front+1)%max_vertex_num;
spot=queue[front];
}while(rear==front);
}
//广度优先搜索
void BFSTraverse(ALGraph g)
{
int i;
bool visit[max_vertex_num];
for(i=0;i<max_vertex_num;i++)
visit[i]=false;
for(i=0;i<g.vexnum;i++){
if(!visit[i]) BFS(g,g.vertices[i],visit);
}
}
void main()
{
ALGraph T;
CreateGraph(&T);
print(T);
printf("\n**深度优先搜索**\n");
DFSTraverse(T);
printf("\n**广度优先搜索**\n");
BFSTraverse(T);
printf("\n");
}
这是邻接表实现图,vc通过
12 楼
lt19870917 [专家分：750] 发布于 2006-05-09 12:55:00
接下来是十字链表...
13 楼
lt19870917 [专家分：750] 发布于 2006-05-10 17:35:00
#include "iostream.h"
#include "stdio.h"
#include "stdlib.h"
#define max_vertex_num 20
typedef char vertextype;
struct ArcBox{
int tailvex,headvex;
struct ArcBox *hlink,*tlink;
int info;//权
};
struct VexNode{
vertextype data;
ArcBox *firstin,*firstout;
};
struct OLGraph{
VexNode xlist[max_vertex_num];
int vexnum,arcnum;
};
//
void CreateGraph(OLGraph &g)
{
int i,j,w;
vertextype m,n;
ArcBox *arc,*tl,*hl;
int spot1,spot2;
for(i=0;i<max_vertex_num;i++){
g.xlist[i].firstin=(ArcBox *)malloc(sizeof(ArcBox));
g.xlist[i].firstout=(ArcBox *)malloc(sizeof(ArcBox));
g.xlist[i].firstin->hlink=NULL;
g.xlist[i].firstout->tlink=NULL;
}
printf("顶点数和弧数:");
scanf("%d,%d",&g.vexnum,&g.arcnum);
printf("顶点为:");
for(i=0;i<g.vexnum;i++)
cin>>g.xlist[i].data;
for(;i<max_vertex_num;i++)
g.xlist[i].data=NULL;
printf("弧为:");
for(i=0;i<g.arcnum;i++){
cin>>m>>n>>w;
for(j=0;j<max_vertex_num;j++){
if(g.xlist[j].data!=NULL&&g.xlist[j].data==m)
break;
}
spot1=j;
for(j=0;j<max_vertex_num;j++){
if(g.xlist[j].data!=NULL&&g.xlist[j].data==n)
break;
}
spot2=j;
arc=(ArcBox *)malloc(sizeof(ArcBox));
arc->tailvex=spot1;
arc->headvex=spot2;
arc->info=w;
arc->hlink=NULL;
arc->tlink=NULL;
tl=g.xlist[spot1].firstout;
while(tl->tlink!=NULL)
tl=tl->tlink;
tl->tlink=arc;
hl=g.xlist[spot2].firstin;
while(hl->hlink!=NULL)
hl=hl->hlink;
hl->hlink=arc;
}
}
int LocateVex(OLGraph g,VexNode v)
{
int i;
for(i=0;i<max_vertex_num;i++){
if(g.xlist[i].data!=NULL&&g.xlist[i].data==v.data)
return(i);
}
return(-1);//
}
14 楼
lt19870917 [专家分：750] 发布于 2006-05-10 17:37:00
int FirstAdjVex(OLGraph g,VexNode v)
{
int spot;
ArcBox *arc;
spot=LocateVex(g,v);
arc=g.xlist[spot].firstout->tlink;
if(arc!=NULL)
return(arc->headvex);
return(-1);//
}
int NextAdjVex(OLGraph g,VexNode v,VexNode w)
{
int spot;
ArcBox *arc;
spot=LocateVex(g,v);
arc=g.xlist[spot].firstout->tlink;
while(arc!=NULL&&arc->headvex!=w.data)
arc=arc->tlink;
if(arc!=NULL&&arc->tlink!=NULL)
return(arc->tlink->headvex);
return(-1);//
}
//print函数
void print(OLGraph g)
{
int i;
ArcBox *arc;
for(i=0;i<max_vertex_num;i++){
if(g.xlist[i].data!=NULL){
printf("顶点为:%c ",g.xlist[i].data);
printf("邻接点为:");
arc=g.xlist[i].firstout->tlink;
while(arc!=NULL){
printf("%c ",g.xlist[arc->headvex].data);
arc=arc->tlink;
}
printf("\n");
}
}
}
//访问函数
void f(VexNode v)
{
printf("%c ",v.data);
}
void DFS(OLGraph g,VexNode v,bool visit[])//同时可以得到连通分量
{
int spot,stack[max_vertex_num],top=-1;
spot=LocateVex(g,v);
do{
if(!visit[spot]){
f(g.xlist[spot]);
visit[spot]=true;
top++;
stack[top]=spot;
}
for(spot=FirstAdjVex(g,v);spot>=0;spot=NextAdjVex(g,v,g.xlist[spot])){
if(!visit[spot])
break;
}
if(spot>=0){
v=g.xlist[spot];
continue;
}
else{
top--;
if(top!=-1)
spot=stack[top];
}
}while(top!=-1);
}
//深度优先搜索
void DFSTraverse(OLGraph g)
{
bool visit[max_vertex_num];
int i;
for(i=0;i<max_vertex_num;i++)
visit[i]=false;
for(i=0;i<g.vexnum;i++){
if(!visit[i]) DFS(g,g.xlist[i],visit);
}
}
//可一得到连通分量
void BFS(OLGraph g,VexNode v,bool visit[])
{
int spot,front=-1,rear=-1,queue[max_vertex_num];
spot=LocateVex(g,v);
f(v);
visit[spot]=true;
do{
for(spot=FirstAdjVex(g,v);spot>=0;spot=NextAdjVex(g,v,g.xlist[spot])){
if(!visit[spot]){
f(g.xlist[spot]);
visit[spot]=true;
rear=(rear+1)%max_vertex_num;
queue[rear]=spot;
}
}
front=(front+1)%max_vertex_num;
spot=queue[front];
}while(rear==front);
}
//广度优先搜索
void BFSTraverse(OLGraph g)
{
int i;
bool visit[max_vertex_num];
for(i=0;i<max_vertex_num;i++)
visit[i]=false;
for(i=0;i<g.vexnum;i++){
if(!visit[i]) BFS(g,g.xlist[i],visit);
}
}
void main()
{
OLGraph T;
CreateGraph(T);
print(T);
printf("\n**深度优先搜索**\n");
DFSTraverse(T);
printf("\n**广度优先搜索**\n");
BFSTraverse(T);
printf("\n");
}
15 楼
lt19870917 [专家分：750] 发布于 2006-05-10 17:38:00
最后就是邻接多重表...
16 楼
康伟 [专家分：0] 发布于 2006-06-18 01:12:00
能不能把用邻接多重表做的那个完整的贴出来啊？
17 楼
flybird883 [专家分：0] 发布于 2006-06-29 19:13:00
对啊，有没有用邻接多重表做的完整程序啊？
我来回复
您所在位置：