C++编写程序 关于【图的遍历】
ude <iostream>
#include <malloc.h>
using namespace std;
#define int_max 10000
#define inf 9999
#define max 20
//…………………………………………邻接矩阵定义……………………
typedef struct ArcCell
{
int adj;
char *info;
}ArcCell,AdjMatrix[20][20];
typedef struct
{
char vexs[20];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph_L;
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int localvex(MGraph_L G,char v)//返回V的位置
{
int i=0;
while(G.vexs[i]!=v)
{
++i;
}
return i;
}
int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示
{
char v1,v2;
int i,j,w;
cout<<"…………创建无向图…………"<<endl<<"请输入图G顶点和弧的个数:(4 6)不包括“()”"<<endl;
cin>>G.vexnum>>G.arcnum;
for(i=0;i!=G.vexnum;++i)
{
cout<<"输入顶点"<<i<<endl;
cin>>G.vexs[i];
}
for(i=0;i!=G.vexnum;++i)
for(j=0;j!=G.vexnum;++j)
{
G.arcs[i][j].adj=int_max;
G.arcs[i][j].info=NULL;
}
for(int k=0;k!=G.arcnum;++k)
{
cout<<"输入一条边依附的顶点和权:(a b 3)不包括“()”"<<endl;
cin>>v1>>v2>>w;//输入一条边依附的两点及权值
i=localvex(G,v1);//确定顶点V1和V2在图中的位置
j=localvex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=w;
}
cout<<"图G邻接矩阵创建成功！"<<endl;
return G.vexnum;
}
void ljjzprint(MGraph_L G)
{
int i,j;
for(i=0;i!=G.vexnum;++i)
{
for(j=0;j!=G.vexnum;++j)
cout<<G.arcs[i][j].adj<<" ";
cout<<endl;
}
}
int visited[max];//访问标记
int we;
typedef struct arcnode//弧结点
{
int adjvex;//该弧指向的顶点的位置
struct arcnode *nextarc;//弧尾相同的下一条弧
char *info;//该弧信息
}arcnode;
typedef struct vnode//邻接链表顶点头接点
{
char data;//结点信息
arcnode *firstarc;//指向第一条依附该结点的弧的指针
}vnode,adjlist;
typedef struct//图的定义
{
adjlist vertices[max];
int vexnum,arcnum;
int kind;
}algraph;
//…………………………………………队列定义……………………
typedef struct qnode
{
int data;
struct qnode *next;
}qnode,*queueptr;
typedef struct
{
queueptr front;
queueptr rear;
}linkqueue;
//………………………………………………………………………
typedef struct acr
{
int pre;//弧的一结点
int bak;//弧另一结点
int weight;//弧的权
}edg;
int creatadj(algraph &gra,MGraph_L G)//用邻接表存储图
{
int i=0,j=0;
arcnode *arc,*tem,*p;
for(i=0;i!=G.vexnum;++i)
{
gra.vertices[i].data=G.vexs[i];
gra.vertices[i].firstarc=NULL;
}
for(i=0;i!=G.vexnum;++i)
{
for(j=0;j!=G.vexnum;++j)
{
if(gra.vertices[i].firstarc==NULL)
{
if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
{
arc=(arcnode *)malloc(sizeof(arcnode));
arc->adjvex=j;
gra.vertices[i].firstarc=arc;
arc->nextarc=NULL;
p=arc;
++j;
while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
{
tem=(arcnode *)malloc(sizeof(arcnode));
tem->adjvex=j;
gra.vertices[i].firstarc=tem;
tem->nextarc=arc;
arc=tem;
++j;
}
--j;
}
}
else
{
if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
{
arc=(arcnode *)malloc(sizeof(arcnode));
arc->adjvex=j;
p->nextarc=arc;
arc->nextarc=NULL;
p=arc;
}
}
}
}
gra.vexnum=G.vexnum;
gra.arcnum=G.arcnum;
/*for(i=0;i!=gra.vexnum;++i)
{
arcnode *p;
cout<<i<<" ";
p=gra.vertices[i].firstarc;
while(p!=NULL)
{
cout<<p->adjvex;
p=p->nextarc;
}
cout<<endl;
}*/
cout<<"图G邻接表创建成功！"<<endl;
return 1;
}
void adjprint(algraph gra)
{
int i;
for(i=0;i!=gra.vexnum;++i)
{
arcnode *p;
cout<<i<<" ";
p=gra.vertices[i].firstarc;
while(p!=NULL)
{
cout<<p->adjvex;
p=p->nextarc;
}
cout<<endl;
}
}
int firstadjvex(algraph gra,vnode v)//返回依附顶点V的第一个点
//即以V为尾的第一个结点
{
if(v.firstarc!=NULL)
return v.firstarc->adjvex;
}
int nextadjvex(algraph gra,vnode v,int w)//返回依附顶点V的相对于W的下一个顶点
{
arcnode *p;
p=v.firstarc;
while(p!=NULL&&p->adjvex!=w)
{
p=p->nextarc;
}
if(p->adjvex==w&&p->nextarc!=NULL)
{
p=p->nextarc;
return p->adjvex;
}
if(p->adjvex==w&&p->nextarc==NULL)
return -10;
}
int initqueue(linkqueue &q)//初始化队列
{
q.rear=(queueptr)malloc(sizeof(qnode));
q.front=q.rear;
if(!q.front)
return 0;
q.front->next=NULL;
return 1;
}
int enqueue(linkqueue &q,int e)//入队
{
queueptr p;
p=(queueptr)malloc(sizeof(qnode));
if(!p)
return 0;
p->data=e;
p->next=NULL;
q.rear->next=p;
q.rear=p;
return 1;
}
int dequeue(linkqueue &q,int &e)//出队
{
queueptr p;
if(q.front==q.rear)
return 0;
p=q.front->next;
e=p->data;
q.front->next=p->next;
if(q.rear==p)
q.rear=q.front;
free(p);
return 1;
}
int queueempty(linkqueue q)//判断队为空
{
if(q.front==q.rear)
return 1;
return 0;
}
void bfstra(algraph gra)//广度优先遍历
{
int i,e;
linkqueue q;
for(i=0;i!=gra.vexnum;++i)
visited[i]=0;
initqueue(q);
for(i=0;i!=gra.vexnum;++i)
if(!visited[i])
{ visited[i]=1;
cout<<gra.vertices[i].data;
enqueue(q,i);
while(!queueempty(q))
{
dequeue(q,e);
// cout<<" "<<e<<" ";
for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.vertices[e],we))
{
if(!visited[we])
{
visited[we]=1;
cout<<gra.vertices[we].data;
enqueue(q,we);
}
}
}
}
}
int dfs(algraph gra,int i);//声明DFS
int dfstra(algraph gra)
{
int i,j;
for(i=0;i!=gra.vexnum;++i)
{
visited[i]=0;
}
for(j=0;j!=gra.vexnum;++j)
{
if(visited[j]==0)
dfs(gra,j);
}
return 0;
}
int dfs(algraph gra,int i)
{
visited[i]=1;
int we1;
// cout<<i<<visited[i]<<endl;
cout<<gra.vertices[i].data;
// cout<<endl;
for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we))
{
// cout<<we<<visited[we]<<endl;
we1=we;
// cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;
if(visited[we]==0)
// cout<<
dfs(gra,we);//<<endl;
// cout<<i<<we1<<endl;
we=we1;
// cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;
}
return 12;
}
int bfstra_fen(algraph gra)//求连通分量
{
int i,j;
for(i=0;i!=gra.vexnum;++i)
{
visited[i]=0;
}
for(j=0;j!=gra.vexnum;++j)
{
if(visited[j]==0)
{
dfs(gra,j);
cout<<endl;
}
}
return 0;
}
typedef struct
{
int adjvex;
int lowcost;
}closedge;
/*int minimum(closedge *p);
int minispantree(MGraph_L G,char u)
{
int k,j,i;
closedge closedge_a[20];
k=localvex(G,u);
// cout<<k<<endl;
for(j=0;j!=G.vexnum;++j)
{
if(j!=k)
{
closedge_a[j].adjvex=u;
closedge_a[j].lowcost=G.arcs[k][j].adj;
}
for(i=1;i!=G.vexnum;++i)
{
k=minimum(closedge_a);
cout<<k;
cout<<closedge_a[k].adjvex<<" "<<G.vexs[k]<<endl;
closedge_a[k].lowcost=0;
for(j=0;j!=G.vexnum;++j)
if(G.arcs[k][j].adj<closedge_a[j].lowcost)
{
closedge_a[j].adjvex=G.vexs[k];
closedge_a[j].lowcost=G.arcs[k][j].adj;
}
}
}
return 0;
}
int minimum(closedge *p)
{
int s=10000;
for(;p!=NULL;++p)
{
if(s>p->lowcost)
s=p->lowcost;
}
return s;
}*/
int prim(int g[][max],int n) //最小生成树PRIM算法
{
int lowcost[max],prevex[max]; //LOWCOST[]存储当前集合U分别到剩余结点的最短路径
//prevex[]存储最短路径在U中的结点
int i,j,k,min;
for(i=2;i<=n;i++) //n个顶点，n-1条边
{
lowcost[i]=g[1][i]; //初始化
prevex[i]=1; //顶点未加入到最小生成树中
}
lowcost[1]=0; //标志顶点1加入U集合
for(i=2;i<=n;i++) //形成n-1条边的生成树
{
min=inf;
k=0;
for(j=2;j<=n;j++) //寻找满足边的一个顶点在U,另一个顶点在V的最小边
if((lowcost[j]<min)&&(lowcost[j]!=0))
{
min=lowcost[j];
k=j;
}
printf("(%d,%d)%d",prevex[k]-1,k-1,min);
lowcost[k]=0; //顶点k加入U
for(j=2;j<=n;j++) //修改由顶点k到其他顶点边的权值
if(g[k][j]<lowcost[j])
{
lowcost[j]=g[k][j];
prevex[j]=k;
}
printf("
");
}
return 0;
}
int acrvisited[100];//kruscal弧标记数组
int find(int acrvisited[],int f)
{
while(acrvisited[f]>0)
f=acrvisited[f];
return f;
}
void kruscal_arc(MGraph_L G,algraph gra)
{
edg edgs[20];
int i,j,k=0;
for(i=0;i!=G.vexnum;++i)
for(j=i;j!=G.vexnum;++j)
{
if(G.arcs[i][j].adj!=10000)
{
edgs[k].pre=i;
edgs[k].bak=j;
edgs[k].weight=G.arcs[i][j].adj;
++k;
}
}
int x,y,m,n;
int buf,edf;
for(i=0;i!=gra.arcnum;++i)
acrvisited[i]=0;
for(j=0;j!=G.arcnum;++j)
{
m=10000;
for(i=0;i!=G.arcnum;++i)
{
if(edgs[i].weight<m)
{
m=edgs[i].weight;
x=edgs[i].pre;
y=edgs[i].bak;
n=i;
}
}
// cout<<x<<y<<m;
// cout<<endl;
buf=find(acrvisited,x);
edf=find(acrvisited,y);
// cout<<buf<<" "<<edf<<endl;
edgs[n].weight=10000;
if(buf!=edf)
{
acrvisited[buf]=edf;
cout<<"("<<x<<","<<y<<")"<<m;
cout<<endl;
}
}
}
void main()
{
algraph gra;
MGraph_L G;
int i,d,g[20][20];
char a='a';
d=creatMGraph_L(G);
creatadj(gra,G);
vnode v;
cout<<endl<<"……####注意：若该图为非强连通图(含有多个连通分量)时"<<endl
<<" 最小生成树不存在,则显示为非法值。"<<endl<<endl;
cout<<"…………………菜单……………………"<<endl<<endl;
cout<<"0、显示该图的邻接矩阵……………………"<<endl;
cout<<"1、显示该图的邻接表……………………"<<endl;
cout<<"2、深度优先遍历…………………………"<<endl;
cout<<"3、广度优先遍历…………………………"<<endl;
cout<<"4、最小生成树PRIM算法…………………"<<endl;
cout<<"5、最小生成树KRUSCAL算法………………"<<endl;
cout<<"6、该图的连通分量………………………"<<endl<<endl;
int s;
char y='y';
while(y='y')
{
cout<<"请选择菜单："<<endl;
cin>>s;
switch(s)
{
case 0:
cout<<"邻接矩阵显示如下："<<endl;
ljjzprint(G);
break;
case 1:
cout<<"邻接表显示如下："<<endl;
adjprint(gra);
break;
case 2:
cout<<"广度优先遍历：";
bfstra(gra);
cout<<endl;
break;
case 3:
for(i=0;i!=gra.vexnum;++i)
{
visited[i]=0;
}
cout<<"深度优先遍历：";
dfstra(gra);
cout<<endl;
break;
case 4:
for(i=0;i!=G.vexnum;++i)
for(int j=0;j!=G.vexnum;++j)
g[i+1][j+1]=G.arcs[i][j].adj;
cout<<"prim:"<<endl;
prim(g,d);
break;
case 5:
cout<<"kruscal:"<<endl;
kruscal_arc(G,gra);
break;
case 6:
cout<<"连通分量:";
bfstra_fen(gra);
break;
}
cout<<endl<<"是否继续？y/n:";
cin>>y;
if(y=='n')
break;
}
}
另外,虚机团上产品团购,超级便宜
楼主你好，下面是源程序！
/*/////////////////////////////////////////////////////////////*/
/* 图的深度优先遍历 */
/*/////////////////////////////////////////////////////////////*/
#include
#include
struct node /* 图顶点结构定义 */
{
int vertex; /* 顶点数据信息 */
struct node *nextnode; /* 指下一顶点的指标 */
};
typedef struct node *graph; /* 图形的结构新型态 */
struct node head[9]; /* 图形顶点数组 */
int visited[9]; /* 遍历标记数组 */
/********************根据已有的信息建立邻接表********************/
void creategraph(int node[20][2],int num)/*num指的是图的边数*/
{
graph newnode; /*指向新节点的指针定义*/
graph ptr;
int from; /* 边的起点 */
int to; /* 边的终点 */
int i;
for ( i = 0; i < num; i++ ) /* 读取边线信息，插入邻接表*/
{
from = node[i][0]; /* 边线的起点 */
to = node[i][1]; /* 边线的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 建立顶点内容 */
newnode->nextnode = NULL; /* 设定指标初值 */
ptr = &(head[from]); /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode; /* 下一个顶点 */
ptr->nextnode = newnode; /* 插入节点 */
}
}
/********************** 图的深度优先搜寻法********************/
void dfs(int current)
{
graph ptr;
visited[current] = 1; /* 记录已遍历过 */
printf("vertex[%d]
",current); /* 输出遍历顶点值 */
ptr = head[current].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过 */
dfs(ptr->vertex); /* 递回遍历呼叫 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
}
/****************************** 主程序******************************/
void main()
{
graph ptr;
int node[20][2] = { {1, 2}, {2, 1}, /* 边线数组 */
{1, 3}, {3, 1},
{1, 4}, {4, 1},
{2, 5}, {5, 2},
{2, 6}, {6, 2},
{3, 7}, {7, 3},
{4, 7}, {4, 4},
{5, 8}, {8, 5},
{6, 7}, {7, 6},
{7, 8}, {8, 7} };
int i;
clrscr();
for ( i = 1; i <= 8; i++ ) /* 顶点数组初始化 */
{
head[i].vertex = i; /* 设定顶点值 */
head[i].nextnode = NULL; /* 指针为空 */
visited[i] = 0; /* 设定遍历初始标志 */
}
creategraph(node,20); /* 建立邻接表 */
printf("Content of the gragh's ADlist is:
");
for ( i = 1; i <= 8; i++ )
{
printf("vertex%d ->",head[i].vertex); /* 顶点值 */
ptr = head[i].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex); /* 印出顶点内容 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
printf("
"); /* 换行 */
}
printf("
The end of the dfs are:
");
dfs(1); /* 打印输出遍历过程 */
printf("
"); /* 换行 */
puts(" Press any key to quit...");
getch();
}
/*//////////////////////////////////////////*/
/* 图形的广度优先搜寻法 */
/* ///////////////////////////////////////*/
#include
#include
#define MAXQUEUE 10 /* 队列的最大容量 */
struct node /* 图的顶点结构定义 */
{
int vertex;
struct node *nextnode;
};
typedef struct node *graph; /* 图的结构指针 */
struct node head[9]; /* 图的顶点数组 */
int visited[9]; /* 遍历标记数组 */
int queue[MAXQUEUE]; /* 定义序列数组 */
int front = -1; /* 序列前端 */
int rear = -1; /* 序列后端 */
/***********************二维数组向邻接表的转化****************************/
void creategraph(int node[20][2],int num)
{
graph newnode; /* 顶点指针 */
graph ptr;
int from; /* 边起点 */
int to; /* 边终点 */
int i;
for ( i = 0; i < num; i++ ) /* 第i条边的信息处理 */
{
from = node[i][0]; /* 边的起点 */
to = node[i][1]; /* 边的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 顶点内容 */
newnode->nextnode = NULL; /* 设定指针初值 */
ptr = &(head[from]); /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode; /* 下一个顶点 */
ptr->nextnode = newnode; /* 插入第i个节点的链表尾部 */
}
}
/************************ 数值入队列************************************/
int enqueue(int value)
{
if ( rear >= MAXQUEUE ) /* 检查伫列是否全满 */
return -1; /* 无法存入 */
rear++; /* 后端指标往前移 */
queue[rear] = value; /* 存入伫列 */
}
/************************* 数值出队列*********************************/
int dequeue()
{
if ( front == rear ) /* 队列是否为空 */
return -1; /* 为空，无法取出 */
front++; /* 前端指标往前移 */
return queue[front]; /* 从队列中取出信息 */
}
/*********************** 图形的广度优先遍历************************/
void bfs(int current)
{
graph ptr;
/* 处理第一个顶点 */
enqueue(current); /* 将顶点存入队列 */
visited[current] = 1; /* 已遍历过记录标志置疑1*/
printf(" Vertex[%d]
",current); /* 打印输出遍历顶点值 */
while ( front != rear ) /* 队列是否为空 */
{
current = dequeue(); /* 将顶点从队列列取出 */
ptr = head[current].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /*顶点没有遍历过*/
{
enqueue(ptr->vertex); /* 奖定点放入队列 */
visited[ptr->vertex] = 1; /* 置遍历标记为1 */
printf(" Vertex[%d]
",ptr->vertex);/* 印出遍历顶点值 */
}
ptr = ptr->nextnode; /* 下一个顶点 */
}
}
}
/*********************** 主程序 ************************************/
/*********************************************************************/
void main()
{
graph ptr;
int node[20][2] = { {1, 2}, {2, 1}, /* 边信息数组 */
{6, 3}, {3, 6},
{2, 4}, {4, 2},
{1, 5}, {5, 1},
{3, 7}, {7, 3},
{1, 7}, {7, 1},
{4, 8}, {8, 4},
{5, 8}, {8, 5},
{2, 8}, {8, 2},
{7, 8}, {8, 7} };
int i;
clrscr();
puts("This is an example of Width Preferred Traverse of Gragh.
");
for ( i = 1; i <= 8; i++ ) /*顶点结构数组初始化*/
{
head[i].vertex = i;
head[i].nextnode = NULL;
visited[i] = 0;
}
creategraph(node,20); /* 图信息转换，邻接表的建立 */
printf("The content of the graph's allist is:
");
for ( i = 1; i <= 8; i++ )
{
printf(" vertex%d =>",head[i].vertex); /* 顶点值 */
ptr = head[i].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex); /* 打印输出顶点内容 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
printf("
"); /* 换行 */
}
printf("The contents of BFS are:
");
bfs(1); /* 打印输出遍历过程 */
printf("
"); /* 换行 */
puts(" Press any key to quit...");
getch();
}
#define t true
#define f false
#include<iostream.h>
struct node//定义一个结构作为节点类型
{
int data;
bool sign;//标志位,用来标示是否遍历过
node *next;
};
node* creategraph()//建立邻接表，完成无向图的输入
{
int l,m,n;
bool g;
cout<<"请输入节点数: ";
cin>>n;
node *adjacencylist=new node[n+1];//动态分配节点数组内存
adjacencylist[0].data=n;//0地址存放的为节点数
adjacencylist[0].next=NULL;
for(int i=1;i<=n;i++)//给各顶点域赋初值
{
adjacencylist[i].data=0;
adjacencylist[i].next=NULL;
adjacencylist[i].sign=f;//表示未遍历
}
cout<<"请依次输入各条边的始点和尾点:（以0表示结束）"<<endl;
cin>>l;
if(l!=0)//判断输入边是否结束
g=t;
while(g==t)
{
cin>>m;
if((l>0)&&(l<=n)&&(m>0)&&(m<=n))//判断输入顶点是否正确
{
node *p,*q,*top;
p=(node *)new(node);//分配边的一个顶点内存
p->data=m;
p->next=NULL;
if(adjacencylist[l].next==NULL)//为每个节点创建邻接链表
adjacencylist[l].next=p;
else
{
top=adjacencylist[l].next;
while(top->next!=NULL)
top=top->next;
top->next=p;
}
adjacencylist[l].data++;//统计邻接点的个数
q=(node *)new(node);//分配边的另一个顶点内存
q->data=l;
q->next=NULL;
if(adjacencylist[m].next==NULL)//构建邻接表
adjacencylist[m].next=q;
else
{
top=adjacencylist[m].next;
while(top->next!=NULL)
top=top->next;
top->next=q;
}
adjacencylist[m].data++;//统计邻接点的个数
}
else
cout<<"边"<<l<<"--"<<m<<"输入错误！"<<endl;//错误输入标识
cin>>l;
if(l==0)//边的输入结束
g=f;
}
return adjacencylist;//返回邻接表
};
void DepthFirstSearch(node *list)//深度优先搜索
{
int m,n=list[0].data,k,*a=new int[n];//设置一个数组用于存放节点
node *p;
cout<<"采用深度优先搜索："<<endl;
cout<<"请输入搜索起始节点：";
cin>>k;
for(int i=0;i<n;i++)
{
a[i]=k;
list[k].sign=t;
if(i==n-1)
break;
m=0;
while(list[k].sign==t)
{
p=list[k].next;
while(p!=NULL)//找出list[k]链表中的未遍历节点
{
k=p->data;
p=p->next;
if(list[k].sign==f)
break;
}
m++;
if(list[k].sign!=f)//判断是否是p=NULL跳出while循环的
{
if(i<m)//无节点可回溯
{
cout<<"该图为非连通图!"<<endl;
break;
}
else
k=a[i-m]; //回溯
}
}
}
for(i=1;i<=n;i++)//恢复原邻接表
list[i].sign=f;
cout<<"深度优先搜索遍历顺序为:";
for(i=0;i<n;i++)//输出遍历结果
cout<<a[i]<<" ";
cout<<endl;
delete a;//释放动态数组内存
};
void BreadthFirstSearth(node *list)//广度优先搜索
{
int m,r,k,n=list[0].data,*a=new int[n+1];//设置数组存放节点
node *p;
cout<<"采用广度优先搜索："<<endl;
cout<<"请输入搜索起始节点：";
cin>>k;
a[0]=n;
a[1]=k;
list[k].sign=t;//标识遍历的第一个节点
m=0;
r=1;
while(m!=r)
{
m++;
p=list[a[m]].next;
while(p!=NULL)
{
k=p->data;
if(list[k].sign==f)
{
r++;
a[r]=k;//遍历到的节点存入数组
list[k].sign=t;//标识已经遍历过的节点
}
p=p->next;
}
}
for(int i=1;i<=n;i++)//恢复原邻接表
list[i].sign=f;
cout<<"广度优先搜索遍历顺序为: ";
for(i=1;i<=n;i++)//输出遍历
cout<<a[i]<<" ";
cout<<endl;
delete a;//释放动态数组内存
};
void PathSearth(node *list)//路径搜索
{
int *a,c,d,m,k,n=list[0].data;
cout<<"请输入起始点：";
cin>>k;
cout<<"请输入尾节点：";
cin>>c;
cout<<"请输入要找的路径长度：";
cin>>d;
d=d+1;
if(d>n)
cout<<"不存在这样的简单路径！"<<endl;
else
{
a=new int[d];//动态分配数组内存存放路径上的节点
for(int i=0;i<d;i++)
a[i]=0;
a[0]=k;
node *p;
int x;
list[a[0]].sign=t;
i=1;
while(a[d-1]!=c)
{
while(i<d)
{
x=1;
p=list[a[i-1]].next;
while(p!=NULL)
{
m=p->data;
if(i==d-1&&m==a[0]&&a[0]==c)//路径存在且为回路
{
cout<<"该路径为一条回路！"<<endl;
a[i]=m;
i++;
break;
}
if(list[m].sign==f)
{
if(a[i]!=0)
{
if(x==0)//是否为已经判断过的错误路径
{
a[i]=m;
list[a[i]].sign=t;//标识走过节点
i++;
break;
}
if(a[i]==m)//设置错误路径标识
x=0;
}
else
{
a[i]=m;
list[a[i]].sign=t;//标识走过节点
i++;
break;
}
}
p=p->next;
}
if(p==NULL)
{
a[i]=0;
i--;//由此节点往下的路径不存在,回溯
list[a[i]].sign=f; //还原标识符
}
if(i==0)//无法回溯,路径不存在,跳出循环
{
cout<<"不存在这样的简单路径！"<<endl;
break;
}
}
if(i==0)//无法回溯,路径不存在,跳出循环
break;
if(a[d-1]!=c)//路径不是所要找的
{
i--; //回溯
if(i>=0)
list[a[i]].sign=f;//还原标识符
}
}
if(a[d-1]==c)//判断路径是否找到并输出
{
cout<<"从节点"<<k<<"到节点"<<c<<"的一条路径为：";
for(i=0;i<d-1;i++)//输出路径
cout<<a[i]<<"--> ";
cout<<a[d-1]<<endl;
}
delete a;
}
for(int i=1;i<=n;i++)//恢复原邻接表
list[i].sign=f;
};
void AdjacencyListDelete(node *list)//释放邻接表的空间
{
node *p,*q;
int n=list[0].data;
for(int i=1;i<=n;i++)
{
p=list[i].next;
while(p!=NULL)
{
q=p->next;
delete p;//释放链表节点空间
p=q;
}
}
delete list;//释放邻接表空间
};
void main()
{
node *list;
list=creategraph();//以邻接表的形式建立一个无向图
char a,b;
cout<<"请选择遍历方法：（d:深度优先搜索;b:广度优先搜索）";
for(int i=1;i<2;i++)
{
cin>>a;
switch(a)
{
case 'd':
case 'D': DepthFirstSearch(list);
cout<<"是否采用广度优先搜索重新遍历？（y:是;n:否）";
cin>>b;
if((b=='y')||(b=='Y'))
BreadthFirstSearth(list);
break;
case 'b':
case 'B': BreadthFirstSearth(list);
cout<<"是否采用深度优先搜索重新遍历？（y:是;n:否）";
cin>>b;
if((b=='y')||(b=='Y'))
DepthFirstSearch(list);
break;
default: cout<<"输入错误！请重新输入！"<<endl;
i--;
}
}
while(1)
{
cout<<"是否搜索路径？（y:是;n:否）";
cin>>a;
if((a=='y')||(a=='Y'))
PathSearth(list);
else if((a=='n')||(a=='N'))
break;
else
cout<<"输入错误！"<<endl;
}
AdjacencyListDelete(list);//释放邻接表空间
}
以下程序均运行通过：
图的广度优先遍历
/*******************************************/
/* 图形的广度优先搜寻法 */
/*******************************************/
#include <stdlib.h>
#include <stdio.h>
#define MAXQUEUE 10 /* 队列的最大容量 */
struct node /* 图的顶点结构定义 */
{
int vertex;
struct node *nextnode;
};
typedef struct node *graph; /* 图的结构指针 */
struct node head[9]; /* 图的顶点数组 */
int visited[9]; /* 遍历标记数组 */
int queue[MAXQUEUE]; /* 定义序列数组 */
int front = -1; /* 序列前端 */
int rear = -1; /* 序列后端 */
/***********************二维数组向邻接表的转化****************************/
void creategraph(int node[20][2],int num)
{
graph newnode; /* 顶点指针 */
graph ptr;
int from; /* 边起点 */
int to; /* 边终点 */
int i;
for ( i = 0; i < num; i++ ) /* 第i条边的信息处理 */
{
from = node[i][0]; /* 边的起点 */
to = node[i][1]; /* 边的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 顶点内容 */
newnode->nextnode = NULL; /* 设定指针初值 */
ptr = &(head[from]); /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode; /* 下一个顶点 */
ptr->nextnode = newnode; /* 插入第i个节点的链表尾部 */
}
}
/************************ 数值入队列************************************/
int enqueue(int value)
{
if ( rear >= MAXQUEUE ) /* 检查伫列是否全满 */
return -1; /* 无法存入 */
rear++; /* 后端指标往前移 */
queue[rear] = value; /* 存入伫列 */
}
/************************* 数值出队列*********************************/
int dequeue()
{
if ( front == rear ) /* 队列是否为空 */
return -1; /* 为空，无法取出 */
front++; /* 前端指标往前移 */
return queue[front]; /* 从队列中取出信息 */
}
/*********************** 图形的广度优先遍历************************/
void bfs(int current)
{
graph ptr;
/* 处理第一个顶点 */
enqueue(current); /* 将顶点存入队列 */
visited[current] = 1; /* 已遍历过记录标志置疑1*/
printf(" Vertex[%d]\n",current); /* 打印输出遍历顶点值 */
while ( front != rear ) /* 队列是否为空 */
{
current = dequeue(); /* 将顶点从队列列取出 */
ptr = head[current].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /*顶点没有遍历过*/
{
enqueue(ptr->vertex); /* 奖定点放入队列 */
visited[ptr->vertex] = 1; /* 置遍历标记为1 */
printf(" Vertex[%d]\n",ptr->vertex);/* 印出遍历顶点值 */
}
ptr = ptr->nextnode; /* 下一个顶点 */
}
}
}
/*********************** 主程序 ************************************/
/*********************************************************************/
int main()
{
graph ptr;
int node[20][2] = { {1, 2}, {2, 1}, /* 边信息数组 */
{6, 3}, {3, 6},
{2, 4}, {4, 2},
{1, 5}, {5, 1},
{3, 7}, {7, 3},
{1, 7}, {7, 1},
{4, 8}, {8, 4},
{5, 8}, {8, 5},
{2, 8}, {8, 2},
{7, 8}, {8, 7} };
int i;
clrscr();
puts("This is an example of Width Preferred Traverse of Gragh.\n");
for ( i = 1; i <= 8; i++ ) /*顶点结构数组初始化*/
{
head[i].vertex = i;
head[i].nextnode = NULL;
visited[i] = 0;
}
creategraph(node,20); /* 图信息转换，邻接表的建立 */
printf("The content of the graph's allist is:\n");
for ( i = 1; i <= 8; i++ )
{
printf(" vertex%d =>",head[i].vertex); /* 顶点值 */
ptr = head[i].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex); /* 打印输出顶点内容 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
printf("\n"); /* 换行 */
}
printf("The contents of BFS are:\n");
bfs(1); /* 打印输出遍历过程 */
printf("\n"); /* 换行 */
puts(" Press any key to quit...");
getch();
return 0;
}
图的深度优先遍历
/***************************************************************/
/* 图的深度优先遍历 */
/***************************************************************/
#include <stdlib.h>
#include <stdio.h>
struct node /* 图顶点结构定义 */
{
int vertex; /* 顶点数据信息 */
struct node *nextnode; /* 指下一顶点的指标 */
};
typedef struct node *graph; /* 图形的结构新型态 */
struct node head[9]; /* 图形顶点数组 */
int visited[9]; /* 遍历标记数组 */
/********************根据已有的信息建立邻接表********************/
void creategraph(int node[20][2],int num)/*num指的是图的边数*/
{
graph newnode; /*指向新节点的指针定义*/
graph ptr;
int from; /* 边的起点 */
int to; /* 边的终点 */
int i;
for ( i = 0; i < num; i++ ) /* 读取边线信息，插入邻接表*/
{
from = node[i][0]; /* 边线的起点 */
to = node[i][1]; /* 边线的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 建立顶点内容 */
newnode->nextnode = NULL; /* 设定指标初值 */
ptr = &(head[from]); /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode; /* 下一个顶点 */
ptr->nextnode = newnode; /* 插入节点 */
}
}
/********************** 图的深度优先搜寻法********************/
void dfs(int current)
{
graph ptr;
visited[current] = 1; /* 记录已遍历过 */
printf("vertex[%d]\n",current); /* 输出遍历顶点值 */
ptr = head[current].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过 */
dfs(ptr->vertex); /* 递回遍历呼叫 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
}
/****************************** 主程序******************************/
int main()
{
graph ptr; /* 边线数组 */
int node[20][2] = { {1, 2}, {2, 1},
{1, 3}, {3, 1},
{1, 4}, {4, 1},
{2, 5}, {5, 2},
{2, 6}, {6, 2},
{3, 7}, {7, 3},
{4, 7}, {4, 4},
{5, 8}, {8, 5},
{6, 7}, {7, 6},
{7, 8}, {8, 7} };
int i;
clrscr();
for ( i = 1; i <= 8; i++ ) /* 顶点数组初始化 */
{
head[i].vertex = i; /* 设定顶点值 */
head[i].nextnode = NULL; /* 指针为空 */
visited[i] = 0; /* 设定遍历初始标志 */
}
creategraph(node,20); /* 建立邻接表 */
printf("Content of the gragh's ADlist is:\n");
for ( i = 1; i <= 8; i++ )
{
printf("vertex%d ->",head[i].vertex); /* 顶点值 */
ptr = head[i].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex); /* 印出顶点内容 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
printf("\n"); /* 换行 */
}
printf("\nThe end of the dfs are:\n");
dfs(1); /* 打印输出遍历过程 */
printf("\n"); /* 换行 */
puts(" Press any key to quit...");
getch();
return 0;
}
里面多了查找路径功能。
#define
t
true
#define
f
false
#include<iostream.h>
struct
node//定义一个结构作为节点类型
{
int
data;
bool
sign;//标志位,用来标示是否遍历过
node
*next;
};
node*
creategraph()//建立邻接表，完成无向图的输入
{
int
l,m,n;
bool
g;
cout<<"请输入节点数:
";
cin>>n;
node
*adjacencylist=new
node[n+1];//动态分配节点数组内存
adjacencylist[0].data=n;//0地址存放的为节点数
adjacencylist[0].next=NULL;
for(int
i=1;i<=n;i++)//给各顶点域赋初值
{
adjacencylist[i].data=0;
adjacencylist[i].next=NULL;
adjacencylist[i].sign=f;//表示未遍历
}
cout<<"请依次输入各条边的始点和尾点:(以0表示结束)"<<endl;
cin>>l;
if(l!=0)//判断输入边是否结束
g=t;
while(g==t)
{
cin>>m;
if((l>0)&&(l<=n)&&(m>0)&&(m<=n))//判断输入顶点是否正确
{
node
*p,*q,*top;
p=(node
*)new(node);//分配边的一个顶点内存
p->data=m;
p->next=NULL;
if(adjacencylist[l].next==NULL)//为每个节点创建邻接链表
adjacencylist[l].next=p;
else
{
top=adjacencylist[l].next;
while(top->next!=NULL)
top=top->next;
top->next=p;
}
adjacencylist[l].data++;//统计邻接点的个数
q=(node
*)new(node);//分配边的另一个顶点内存
q->data=l;
q->next=NULL;
if(adjacencylist[m].next==NULL)//构建邻接表
adjacencylist[m].next=q;
else
{
top=adjacencylist[m].next;
while(top->next!=NULL)
top=top->next;
top->next=q;
}
adjacencylist[m].data++;//统计邻接点的个数
}
else
cout<<"边"<<l<<"--"<<m<<"输入错误!"<<endl;//错误输入标识
cin>>l;
if(l==0)//边的输入结束
g=f;
}
return
adjacencylist;//返回邻接表
};
void
DepthFirstSearch(node
*list)//深度优先搜索
{
int
m,n=list[0].data,k,*a=new
int[n];//设置一个数组用于存放节点
node
*p;
cout<<"采用深度优先搜索:"<<endl;
cout<<"请输入搜索起始节点:";
cin>>k;
for(int
i=0;i<n;i++)
{
a[i]=k;
list[k].sign=t;
if(i==n-1)
break;
m=0;
while(list[k].sign==t)
{
p=list[k].next;
while(p!=NULL)//找出list[k]链表中的未遍历节点
{
k=p->data;
p=p->next;
if(list[k].sign==f)
break;
}
m++;
if(list[k].sign!=f)//判断是否是p=NULL跳出while循环的
{
if(i<m)//无节点可回溯
{
cout<<"该图为非连通图!"<<endl;
break;
}
else
k=a[i-m];
//回溯
}
}
}
for(i=1;i<=n;i++)//恢复原邻接表
list[i].sign=f;
cout<<"深度优先搜索遍历顺序为:";
for(i=0;i<n;i++)//输出遍历结果
cout<<a[i]<<"
";
cout<<endl;
delete
a;//释放动态数组内存
};
void
BreadthFirstSearth(node
*list)//广度优先搜索
{
int
m,r,k,n=list[0].data,*a=new
int[n+1];//设置数组存放节点
node
*p;
cout<<"采用广度优先搜索:"<<endl;
cout<<"请输入搜索起始节点:";
cin>>k;
a[0]=n;
a[1]=k;
list[k].sign=t;//标识遍历的第一个节点
m=0;
r=1;
while(m!=r)
{
m++;
p=list[a[m]].next;
while(p!=NULL)
{
k=p->data;
if(list[k].sign==f)
{
r++;
a[r]=k;//遍历到的节点存入数组
list[k].sign=t;//标识已经遍历过的节点
}
p=p->next;
}
}
for(int
i=1;i<=n;i++)//恢复原邻接表
list[i].sign=f;
cout<<"广度优先搜索遍历顺序为:
";
for(i=1;i<=n;i++)//输出遍历
cout<<a[i]<<"
";
cout<<endl;
delete
a;//释放动态数组内存
};
void
PathSearth(node
*list)//路径搜索
{
int
*a,c,d,m,k,n=list[0].data;
cout<<"请输入起始点:";
cin>>k;
cout<<"请输入尾节点:";
cin>>c;
cout<<"请输入要找的路径长度:";
cin>>d;
d=d+1;
if(d>n)
cout<<"不存在这样的简单路径!"<<endl;
else
{
a=new
int[d];//动态分配数组内存存放路径上的节点
for(int
i=0;i<d;i++)
a[i]=0;
a[0]=k;
node
*p;
int
x;
list[a[0]].sign=t;
i=1;
while(a[d-1]!=c)
{
while(i<d)
{
x=1;
p=list[a[i-1]].next;
while(p!=NULL)
{
m=p->data;
if(i==d-1&&m==a[0]&&a[0]==c)//路径存在且为回路
{
cout<<"该路径为一条回路!"<<endl;
a[i]=m;
i++;
break;
}
if(list[m].sign==f)
{
if(a[i]!=0)
{
if(x==0)//是否为已经判断过的错误路径
{
a[i]=m;
list[a[i]].sign=t;//标识走过节点
i++;
break;
}
if(a[i]==m)//设置错误路径标识
x=0;
}
else
{
a[i]=m;
list[a[i]].sign=t;//标识走过节点
i++;
break;
}
}
p=p->next;
}
if(p==NULL)
{
a[i]=0;
i--;//由此节点往下的路径不存在,回溯
list[a[i]].sign=f;
//还原标识符
}
if(i==0)//无法回溯,路径不存在,跳出循环
{
cout<<"不存在这样的简单路径!"<<endl;
break;
}
}
if(i==0)//无法回溯,路径不存在,跳出循环
break;
if(a[d-1]!=c)//路径不是所要找的
{
i--;
//回溯
if(i>=0)
list[a[i]].sign=f;//还原标识符
}
}
if(a[d-1]==c)//判断路径是否找到并输出
{
cout<<"从节点"<<k<<"到节点"<<c<<"的一条路径为:";
for(i=0;i<d-1;i++)//输出路径
cout<<a[i]<<"-->
";
cout<<a[d-1]<<endl;
}
delete
a;
}
for(int
i=1;i<=n;i++)//恢复原邻接表
list[i].sign=f;
};
void
AdjacencyListDelete(node
*list)//释放邻接表的空间
{
node
*p,*q;
int
n=list[0].data;
for(int
i=1;i<=n;i++)
{
p=list[i].next;
while(p!=NULL)
{
q=p->next;
delete
p;//释放链表节点空间
p=q;
}
}
delete
list;//释放邻接表空间
};
void
main()
{
node
*list;
list=creategraph();//以邻接表的形式建立一个无向图
char
a,b;
cout<<"请选择遍历方法:(d:深度优先搜索;b:广度优先搜索)";
for(int
i=1;i<2;i++)
{
cin>>a;
switch(a)
{
case
'd':
case
'D':
DepthFirstSearch(list);
cout<<"是否采用广度优先搜索重新遍历?(y:是;n:否)";
cin>>b;
if((b=='y')||(b=='Y'))
BreadthFirstSearth(list);
break;
case
'b':
case
'B':
BreadthFirstSearth(list);
cout<<"是否采用深度优先搜索重新遍历?(y:是;n:否)";
cin>>b;
if((b=='y')||(b=='Y'))
DepthFirstSearch(list);
break;
default:
cout<<"输入错误!请重新输入!"<<endl;
i--;
}
}
while(1)
{
cout<<"是否搜索路径?(y:是;n:否)";
cin>>a;
if((a=='y')||(a=='Y'))
PathSearth(list);
else
if((a=='n')||(a=='N'))
break;
else
cout<<"输入错误!"<<endl;
}
AdjacencyListDelete(list);//释放邻接表空间
}
1楼确实激动了些.....
这个，垃圾自有垃圾收拾
种瓜的瓜，种豆的豆
良莲妥布： void PreOrder(BTNode *b) { if(b!=NULL) { countdata; PreOrder(b->lchild); PreOrder(b->rchild); } }
恩平市13013452809： 数据结构 图的遍历演示.c++语言 - ？
良莲妥布： 程序编程如下:#include#define INFINITY 32767 #define MAX_V 20 //最多顶点个数 #define QUEUE_SIZE (MAX_V+1) //队列长度 using namespace std; bool *visited; //访问标志数组 typedef struct //图的邻接矩阵存储结构 { char *vexs; //顶点向...
恩平市13013452809： 我想写一个用c++语言编写的图的遍历,包括前序遍历、中序遍历、后序遍历. - ？
良莲妥布： 大哥,图的遍历是广度优先遍历和深度优先遍历吧 而且还要分联通图的遍历还有非联通图的遍历
恩平市13013452809： 怎么用C++实现图的遍历深度优先和广度优先搜索 - ？
良莲妥布： #include class Node{ public:int value; Node * left; Node * right; Node(int v): value(v){ left = NULL; right = NULL; } ~Node() { if(left != NULL) delete left; if (right != NULL) delete right; } }; class BTree { private: Node * root; public: BTree(){ root = NULL; } ...
恩平市13013452809： 以gui方式显示图的各种遍历过程用c++怎么做 - ？
良莲妥布： int w=3;main() { int w=10;printf(＂%d\n＂,fun(5)*w);} fun(int k) { if(k==0) return(w);return(fun(k-1)*k);}
恩平市13013452809： C++图的遍历的深度和广度搜索同时要有你运行程序的结果!你编绎的过程也要在下面实现 ! - ？
良莲妥布： #include＂iostream.h＂const int n=8;const int e=15;typedef int elemtype ;bool visited[n+1];class link{public: ...
恩平市13013452809： C语言编程 图的创建与遍历 - ？
良莲妥布： 在C语言编程中,图的创建和遍历: #include<stdio.h> #define N 20 #define TRUE 1 #define FALSE 0 int visited[N]; typedef struct /*队列的定义*/ { int data[N]; int front,rear; }queue; typedef struct /*图的邻接矩e799bee5baa6e4b893e5b19e...
恩平市13013452809： 马的遍历c++怎么写 - ？
良莲妥布： 仅供参考~ int main() { int a[5] = {1,2,3,4,5}; for(int i=0;i { if(a[i] % 2 == 0) printf(＂偶数＂); else printf(＂奇数＂); } return 0; }
恩平市13013452809： 图的遍历操作c++6.0？
良莲妥布： // 图的遍历.cpp : Defines the entry point for the console application. // //#include ＂stdafx.h＂ #include <stdio.h> #include ＂malloc.h＂ #define m 5 #define NULL 0 typedef struct node { int adjvex; struct node *next; }JD; typedef struct tnode { int ...
恩平市13013452809： C++图的遍历问题 - ？
良莲妥布： const MaxSize=20; const MaxQSize=30; 这两行没有声明类型,然后把int_SeqQueue.cpp 代码粘上来!
