问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501

数据结构 图的遍历演示。c++语言

发布网友 发布时间：2022-04-29 16:48

我来回答

共1个回答

热心网友 时间：2023-10-20 10:52

程序编程如下：
#include <iostream>
#define INFINITY 32767
#define MAX_V 20 //最多顶点个数
#define QUEUE_SIZE (MAX_V+1) //队列长度
using namespace std;
bool *visited; //访问标志数组
typedef struct //图的邻接矩阵存储结构
{ char *vexs; //顶点向量
int arcs[MAX_V][MAX_V]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和边数
}Graph;
class Queue //队列类
{ public: void InitQueue()
{ base=(int *)malloc(QUEUE_SIZE*sizeof(int)); front=rear=0; }
void EnQueue(int e)
{ base[rear]=e; rear=(rear+1)%QUEUE_SIZE; }
void DeQueue(int &e)
{ e=base[front]; front=(front+1)%QUEUE_SIZE; }
public:
int *base; int front; int rear; };
int Locate(Graph G,char c) //图G中查找元素c的位置
{ for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c) return i; return -1; }
void CreateUDN(Graph &G) //创建无向图
{ int i,j,w,s1,s2; char a,b,temp;
printf("输入顶点的总数和边的总数:");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar(); //接收回车
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目
printf("输入%d个顶点分别为：\n",G.vexnum);
for(i=0;i<G.vexnum;i++) //初始化顶点
{ printf("顶点%d:",i); scanf("%c",&G.vexs[i]); temp=getchar();}
for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("输入%d条边分别为：\n",G.arcnum); //读取边信息并初始化集合
for(i=0;i<G.arcnum;i++) //初始化边
{ printf("边%d:",i);
scanf("%c-%c %d",&a,&b,&w); //输入边和权值
temp=getchar(); //接收回车
s1=Locate(G,a); s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w; } }
int FirstVex(Graph G,int k) //图G中顶点k的第一个邻接顶点
{ if(k>=0 && k<G.vexnum)
{ for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY) return i; }
return -1; }
int NextVex(Graph G,int i,int j) //图G中顶点i的第j个邻接顶点的下一个邻接顶点
{ if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum) //i,j合理
{ for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k; }
return -1; }
void DFS(Graph G,int k) //深度优先搜索
{ int i; if(k==-1) //第一次执行DFS时,k为-1
{ for(i=0;i<G.vexnum;i++) if(!visited[i]) DFS(G,i); } //对尚未访问的顶点调用DFS
else
{ visited[k]=true; //访问第k个顶点
printf("%c ",G.vexs[k]);
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); } }
void BFS(Graph G) //广度优先搜索
{ int k;
Queue Q; //辅助队列Q
Q.InitQueue();
for(int i=0;i<G.vexnum;i++)
if(!visited[i]) //i尚未访问
{ visited[i]=true; printf("%c ",G.vexs[i]);
Q.EnQueue(i); //i入列
while(Q.front!=Q.rear)
{ Q.DeQueue(k); //队头元素出列并置为k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]) //w为k的尚未访问的邻接顶点
{ visited[w]=true; printf("%c ",G.vexs[w]);
Q.EnQueue(w); } } } }
void main() //主函数
{ int i; Graph G; CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("\n深度优先搜索结果为: ");
for(i=0;i<G.vexnum;i++) visited[i]=false; DFS(G,-1);
printf("\n广度优先搜索结果为: ");
for(i=0;i<G.vexnum;i++) visited[i]=false; BFS(G); printf("\n ");
}
以上程序可以在VC6.0上运行成功！你需要按要求输入顶点总数和边的总数，例如6 7
顶点0：A
顶点1：B
......
边0：A-B 1 这里的1代表AB边的权值。
......
最终可以实现深度优先、广度优先搜索算法输出访问序列。
希望可以帮到你，祝你好运！

热心网友 时间：2023-10-20 10:52

程序编程如下：
#include <iostream>
#define INFINITY 32767
#define MAX_V 20 //最多顶点个数
#define QUEUE_SIZE (MAX_V+1) //队列长度
using namespace std;
bool *visited; //访问标志数组
typedef struct //图的邻接矩阵存储结构
{ char *vexs; //顶点向量
int arcs[MAX_V][MAX_V]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和边数
}Graph;
class Queue //队列类
{ public: void InitQueue()
{ base=(int *)malloc(QUEUE_SIZE*sizeof(int)); front=rear=0; }
void EnQueue(int e)
{ base[rear]=e; rear=(rear+1)%QUEUE_SIZE; }
void DeQueue(int &e)
{ e=base[front]; front=(front+1)%QUEUE_SIZE; }
public:
int *base; int front; int rear; };
int Locate(Graph G,char c) //图G中查找元素c的位置
{ for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c) return i; return -1; }
void CreateUDN(Graph &G) //创建无向图
{ int i,j,w,s1,s2; char a,b,temp;
printf("输入顶点的总数和边的总数:");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar(); //接收回车
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目
printf("输入%d个顶点分别为：\n",G.vexnum);
for(i=0;i<G.vexnum;i++) //初始化顶点
{ printf("顶点%d:",i); scanf("%c",&G.vexs[i]); temp=getchar();}
for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("输入%d条边分别为：\n",G.arcnum); //读取边信息并初始化集合
for(i=0;i<G.arcnum;i++) //初始化边
{ printf("边%d:",i);
scanf("%c-%c %d",&a,&b,&w); //输入边和权值
temp=getchar(); //接收回车
s1=Locate(G,a); s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w; } }
int FirstVex(Graph G,int k) //图G中顶点k的第一个邻接顶点
{ if(k>=0 && k<G.vexnum)
{ for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY) return i; }
return -1; }
int NextVex(Graph G,int i,int j) //图G中顶点i的第j个邻接顶点的下一个邻接顶点
{ if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum) //i,j合理
{ for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k; }
return -1; }
void DFS(Graph G,int k) //深度优先搜索
{ int i; if(k==-1) //第一次执行DFS时,k为-1
{ for(i=0;i<G.vexnum;i++) if(!visited[i]) DFS(G,i); } //对尚未访问的顶点调用DFS
else
{ visited[k]=true; //访问第k个顶点
printf("%c ",G.vexs[k]);
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); } }
void BFS(Graph G) //广度优先搜索
{ int k;
Queue Q; //辅助队列Q
Q.InitQueue();
for(int i=0;i<G.vexnum;i++)
if(!visited[i]) //i尚未访问
{ visited[i]=true; printf("%c ",G.vexs[i]);
Q.EnQueue(i); //i入列
while(Q.front!=Q.rear)
{ Q.DeQueue(k); //队头元素出列并置为k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]) //w为k的尚未访问的邻接顶点
{ visited[w]=true; printf("%c ",G.vexs[w]);
Q.EnQueue(w); } } } }
void main() //主函数
{ int i; Graph G; CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("\n深度优先搜索结果为: ");
for(i=0;i<G.vexnum;i++) visited[i]=false; DFS(G,-1);
printf("\n广度优先搜索结果为: ");
for(i=0;i<G.vexnum;i++) visited[i]=false; BFS(G); printf("\n ");
}
以上程序可以在VC6.0上运行成功！你需要按要求输入顶点总数和边的总数，例如6 7
顶点0：A
顶点1：B
......
边0：A-B 1 这里的1代表AB边的权值。
......
最终可以实现深度优先、广度优先搜索算法输出访问序列。
希望可以帮到你，祝你好运！

热心网友 时间：2023-10-20 10:52

程序编程如下：
#include <iostream>
#define INFINITY 32767
#define MAX_V 20 //最多顶点个数
#define QUEUE_SIZE (MAX_V+1) //队列长度
using namespace std;
bool *visited; //访问标志数组
typedef struct //图的邻接矩阵存储结构
{ char *vexs; //顶点向量
int arcs[MAX_V][MAX_V]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和边数
}Graph;
class Queue //队列类
{ public: void InitQueue()
{ base=(int *)malloc(QUEUE_SIZE*sizeof(int)); front=rear=0; }
void EnQueue(int e)
{ base[rear]=e; rear=(rear+1)%QUEUE_SIZE; }
void DeQueue(int &e)
{ e=base[front]; front=(front+1)%QUEUE_SIZE; }
public:
int *base; int front; int rear; };
int Locate(Graph G,char c) //图G中查找元素c的位置
{ for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c) return i; return -1; }
void CreateUDN(Graph &G) //创建无向图
{ int i,j,w,s1,s2; char a,b,temp;
printf("输入顶点的总数和边的总数:");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar(); //接收回车
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目
printf("输入%d个顶点分别为：\n",G.vexnum);
for(i=0;i<G.vexnum;i++) //初始化顶点
{ printf("顶点%d:",i); scanf("%c",&G.vexs[i]); temp=getchar();}
for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("输入%d条边分别为：\n",G.arcnum); //读取边信息并初始化集合
for(i=0;i<G.arcnum;i++) //初始化边
{ printf("边%d:",i);
scanf("%c-%c %d",&a,&b,&w); //输入边和权值
temp=getchar(); //接收回车
s1=Locate(G,a); s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w; } }
int FirstVex(Graph G,int k) //图G中顶点k的第一个邻接顶点
{ if(k>=0 && k<G.vexnum)
{ for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY) return i; }
return -1; }
int NextVex(Graph G,int i,int j) //图G中顶点i的第j个邻接顶点的下一个邻接顶点
{ if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum) //i,j合理
{ for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k; }
return -1; }
void DFS(Graph G,int k) //深度优先搜索
{ int i; if(k==-1) //第一次执行DFS时,k为-1
{ for(i=0;i<G.vexnum;i++) if(!visited[i]) DFS(G,i); } //对尚未访问的顶点调用DFS
else
{ visited[k]=true; //访问第k个顶点
printf("%c ",G.vexs[k]);
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); } }
void BFS(Graph G) //广度优先搜索
{ int k;
Queue Q; //辅助队列Q
Q.InitQueue();
for(int i=0;i<G.vexnum;i++)
if(!visited[i]) //i尚未访问
{ visited[i]=true; printf("%c ",G.vexs[i]);
Q.EnQueue(i); //i入列
while(Q.front!=Q.rear)
{ Q.DeQueue(k); //队头元素出列并置为k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]) //w为k的尚未访问的邻接顶点
{ visited[w]=true; printf("%c ",G.vexs[w]);
Q.EnQueue(w); } } } }
void main() //主函数
{ int i; Graph G; CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("\n深度优先搜索结果为: ");
for(i=0;i<G.vexnum;i++) visited[i]=false; DFS(G,-1);
printf("\n广度优先搜索结果为: ");
for(i=0;i<G.vexnum;i++) visited[i]=false; BFS(G); printf("\n ");
}
以上程序可以在VC6.0上运行成功！你需要按要求输入顶点总数和边的总数，例如6 7
顶点0：A
顶点1：B
......
边0：A-B 1 这里的1代表AB边的权值。
......
最终可以实现深度优先、广度优先搜索算法输出访问序列。
希望可以帮到你，祝你好运！

热心网友 时间：2023-10-20 10:52

程序编程如下：
#include <iostream>
#define INFINITY 32767
#define MAX_V 20 //最多顶点个数
#define QUEUE_SIZE (MAX_V+1) //队列长度
using namespace std;
bool *visited; //访问标志数组
typedef struct //图的邻接矩阵存储结构
{ char *vexs; //顶点向量
int arcs[MAX_V][MAX_V]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和边数
}Graph;
class Queue //队列类
{ public: void InitQueue()
{ base=(int *)malloc(QUEUE_SIZE*sizeof(int)); front=rear=0; }
void EnQueue(int e)
{ base[rear]=e; rear=(rear+1)%QUEUE_SIZE; }
void DeQueue(int &e)
{ e=base[front]; front=(front+1)%QUEUE_SIZE; }
public:
int *base; int front; int rear; };
int Locate(Graph G,char c) //图G中查找元素c的位置
{ for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c) return i; return -1; }
void CreateUDN(Graph &G) //创建无向图
{ int i,j,w,s1,s2; char a,b,temp;
printf("输入顶点的总数和边的总数:");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar(); //接收回车
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目
printf("输入%d个顶点分别为：\n",G.vexnum);
for(i=0;i<G.vexnum;i++) //初始化顶点
{ printf("顶点%d:",i); scanf("%c",&G.vexs[i]); temp=getchar();}
for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("输入%d条边分别为：\n",G.arcnum); //读取边信息并初始化集合
for(i=0;i<G.arcnum;i++) //初始化边
{ printf("边%d:",i);
scanf("%c-%c %d",&a,&b,&w); //输入边和权值
temp=getchar(); //接收回车
s1=Locate(G,a); s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w; } }
int FirstVex(Graph G,int k) //图G中顶点k的第一个邻接顶点
{ if(k>=0 && k<G.vexnum)
{ for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY) return i; }
return -1; }
int NextVex(Graph G,int i,int j) //图G中顶点i的第j个邻接顶点的下一个邻接顶点
{ if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum) //i,j合理
{ for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k; }
return -1; }
void DFS(Graph G,int k) //深度优先搜索
{ int i; if(k==-1) //第一次执行DFS时,k为-1
{ for(i=0;i<G.vexnum;i++) if(!visited[i]) DFS(G,i); } //对尚未访问的顶点调用DFS
else
{ visited[k]=true; //访问第k个顶点
printf("%c ",G.vexs[k]);
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); } }
void BFS(Graph G) //广度优先搜索
{ int k;
Queue Q; //辅助队列Q
Q.InitQueue();
for(int i=0;i<G.vexnum;i++)
if(!visited[i]) //i尚未访问
{ visited[i]=true; printf("%c ",G.vexs[i]);
Q.EnQueue(i); //i入列
while(Q.front!=Q.rear)
{ Q.DeQueue(k); //队头元素出列并置为k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]) //w为k的尚未访问的邻接顶点
{ visited[w]=true; printf("%c ",G.vexs[w]);
Q.EnQueue(w); } } } }
void main() //主函数
{ int i; Graph G; CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("\n深度优先搜索结果为: ");
for(i=0;i<G.vexnum;i++) visited[i]=false; DFS(G,-1);
printf("\n广度优先搜索结果为: ");
for(i=0;i<G.vexnum;i++) visited[i]=false; BFS(G); printf("\n ");
}
以上程序可以在VC6.0上运行成功！你需要按要求输入顶点总数和边的总数，例如6 7
顶点0：A
顶点1：B
......
边0：A-B 1 这里的1代表AB边的权值。
......
最终可以实现深度优先、广度优先搜索算法输出访问序列。
希望可以帮到你，祝你好运！

热心网友 时间：2023-10-20 10:52

程序编程如下：
#include <iostream>
#define INFINITY 32767
#define MAX_V 20 //最多顶点个数
#define QUEUE_SIZE (MAX_V+1) //队列长度
using namespace std;
bool *visited; //访问标志数组
typedef struct //图的邻接矩阵存储结构
{ char *vexs; //顶点向量
int arcs[MAX_V][MAX_V]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和边数
}Graph;
class Queue //队列类
{ public: void InitQueue()
{ base=(int *)malloc(QUEUE_SIZE*sizeof(int)); front=rear=0; }
void EnQueue(int e)
{ base[rear]=e; rear=(rear+1)%QUEUE_SIZE; }
void DeQueue(int &e)
{ e=base[front]; front=(front+1)%QUEUE_SIZE; }
public:
int *base; int front; int rear; };
int Locate(Graph G,char c) //图G中查找元素c的位置
{ for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c) return i; return -1; }
void CreateUDN(Graph &G) //创建无向图
{ int i,j,w,s1,s2; char a,b,temp;
printf("输入顶点的总数和边的总数:");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar(); //接收回车
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目
printf("输入%d个顶点分别为：\n",G.vexnum);
for(i=0;i<G.vexnum;i++) //初始化顶点
{ printf("顶点%d:",i); scanf("%c",&G.vexs[i]); temp=getchar();}
for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("输入%d条边分别为：\n",G.arcnum); //读取边信息并初始化集合
for(i=0;i<G.arcnum;i++) //初始化边
{ printf("边%d:",i);
scanf("%c-%c %d",&a,&b,&w); //输入边和权值
temp=getchar(); //接收回车
s1=Locate(G,a); s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w; } }
int FirstVex(Graph G,int k) //图G中顶点k的第一个邻接顶点
{ if(k>=0 && k<G.vexnum)
{ for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY) return i; }
return -1; }
int NextVex(Graph G,int i,int j) //图G中顶点i的第j个邻接顶点的下一个邻接顶点
{ if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum) //i,j合理
{ for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k; }
return -1; }
void DFS(Graph G,int k) //深度优先搜索
{ int i; if(k==-1) //第一次执行DFS时,k为-1
{ for(i=0;i<G.vexnum;i++) if(!visited[i]) DFS(G,i); } //对尚未访问的顶点调用DFS
else
{ visited[k]=true; //访问第k个顶点
printf("%c ",G.vexs[k]);
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); } }
void BFS(Graph G) //广度优先搜索
{ int k;
Queue Q; //辅助队列Q
Q.InitQueue();
for(int i=0;i<G.vexnum;i++)
if(!visited[i]) //i尚未访问
{ visited[i]=true; printf("%c ",G.vexs[i]);
Q.EnQueue(i); //i入列
while(Q.front!=Q.rear)
{ Q.DeQueue(k); //队头元素出列并置为k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]) //w为k的尚未访问的邻接顶点
{ visited[w]=true; printf("%c ",G.vexs[w]);
Q.EnQueue(w); } } } }
void main() //主函数
{ int i; Graph G; CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("\n深度优先搜索结果为: ");
for(i=0;i<G.vexnum;i++) visited[i]=false; DFS(G,-1);
printf("\n广度优先搜索结果为: ");
for(i=0;i<G.vexnum;i++) visited[i]=false; BFS(G); printf("\n ");
}
以上程序可以在VC6.0上运行成功！你需要按要求输入顶点总数和边的总数，例如6 7
顶点0：A
顶点1：B
......
边0：A-B 1 这里的1代表AB边的权值。
......
最终可以实现深度优先、广度优先搜索算法输出访问序列。
希望可以帮到你，祝你好运！

热心网友 时间：2023-10-20 10:52

程序编程如下：
#include <iostream>
#define INFINITY 32767
#define MAX_V 20 //最多顶点个数
#define QUEUE_SIZE (MAX_V+1) //队列长度
using namespace std;
bool *visited; //访问标志数组
typedef struct //图的邻接矩阵存储结构
{ char *vexs; //顶点向量
int arcs[MAX_V][MAX_V]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和边数
}Graph;
class Queue //队列类
{ public: void InitQueue()
{ base=(int *)malloc(QUEUE_SIZE*sizeof(int)); front=rear=0; }
void EnQueue(int e)
{ base[rear]=e; rear=(rear+1)%QUEUE_SIZE; }
void DeQueue(int &e)
{ e=base[front]; front=(front+1)%QUEUE_SIZE; }
public:
int *base; int front; int rear; };
int Locate(Graph G,char c) //图G中查找元素c的位置
{ for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c) return i; return -1; }
void CreateUDN(Graph &G) //创建无向图
{ int i,j,w,s1,s2; char a,b,temp;
printf("输入顶点的总数和边的总数:");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar(); //接收回车
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目
printf("输入%d个顶点分别为：\n",G.vexnum);
for(i=0;i<G.vexnum;i++) //初始化顶点
{ printf("顶点%d:",i); scanf("%c",&G.vexs[i]); temp=getchar();}
for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("输入%d条边分别为：\n",G.arcnum); //读取边信息并初始化集合
for(i=0;i<G.arcnum;i++) //初始化边
{ printf("边%d:",i);
scanf("%c-%c %d",&a,&b,&w); //输入边和权值
temp=getchar(); //接收回车
s1=Locate(G,a); s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w; } }
int FirstVex(Graph G,int k) //图G中顶点k的第一个邻接顶点
{ if(k>=0 && k<G.vexnum)
{ for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY) return i; }
return -1; }
int NextVex(Graph G,int i,int j) //图G中顶点i的第j个邻接顶点的下一个邻接顶点
{ if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum) //i,j合理
{ for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k; }
return -1; }
void DFS(Graph G,int k) //深度优先搜索
{ int i; if(k==-1) //第一次执行DFS时,k为-1
{ for(i=0;i<G.vexnum;i++) if(!visited[i]) DFS(G,i); } //对尚未访问的顶点调用DFS
else
{ visited[k]=true; //访问第k个顶点
printf("%c ",G.vexs[k]);
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); } }
void BFS(Graph G) //广度优先搜索
{ int k;
Queue Q; //辅助队列Q
Q.InitQueue();
for(int i=0;i<G.vexnum;i++)
if(!visited[i]) //i尚未访问
{ visited[i]=true; printf("%c ",G.vexs[i]);
Q.EnQueue(i); //i入列
while(Q.front!=Q.rear)
{ Q.DeQueue(k); //队头元素出列并置为k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]) //w为k的尚未访问的邻接顶点
{ visited[w]=true; printf("%c ",G.vexs[w]);
Q.EnQueue(w); } } } }
void main() //主函数
{ int i; Graph G; CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("\n深度优先搜索结果为: ");
for(i=0;i<G.vexnum;i++) visited[i]=false; DFS(G,-1);
printf("\n广度优先搜索结果为: ");
for(i=0;i<G.vexnum;i++) visited[i]=false; BFS(G); printf("\n ");
}
以上程序可以在VC6.0上运行成功！你需要按要求输入顶点总数和边的总数，例如6 7
顶点0：A
顶点1：B
......
边0：A-B 1 这里的1代表AB边的权值。
......
最终可以实现深度优先、广度优先搜索算法输出访问序列。
希望可以帮到你，祝你好运！
声明声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com
小鹿的过冬方式是什么 我弟弟生气,拍了下电脑桌,结果再开机就说电源按钮关闭,显示器休眠 为什么进入屏保后几分钟显示器又亮了起来 我的手碰电脑桌显示器经常闪一下 下一站江湖所有隐藏功法 最新隐藏功法级别 《下一站江湖》玄龟软甲获得方法介绍_《下一站江湖》玄龟软甲获得方法是... 如何选购前锋热水器 近年美国校园电影,青春喜剧 最好是08-11年的,新的。不要悲剧的。 推荐几部美国校园喜剧电影,谢谢! 美国 八九十年代 的 电视剧 电影 讲美国 八十年代的也可以 内容要有摇... 人教版小学五年级上学期语文期末试卷 网络流行语热成狗成狗是什么意思 写信给上级开头该怎么写? 图的遍历的实现 热处是什么意思网络用语? 图的深度优先遍历c语言算法 给领导写一封信怎么写,我是一个学生 网络用语热乎乎什么意思呀? 2013最热网络用语是哪些? 网络语言好热是什么意思 oracle的环境变量怎么设置啊?装在F:\Oracle下了。 C++编写程序 关于【图的遍历】 用c++写出图的遍历算法,谢谢! C语言编写程序实现图的遍历操作 图的遍历(c语言)完整上机代码 累计折旧记借方是不是就是转销的意思，转销到底是什么意思呢？是不是就是固定资产的实质减少啊？ 累计折旧的定义,如何记它的增加减少? neighborvogue是什么牌子衣服 your,vouge.style是什么意思 什么情况下固定资产原值增加,累计折旧减少 电流是标量还是矢量,解释一下(高中)谢谢 2017有哪些热门的网络词语? 我想向领导反应一些问题怎么写开头 网络用语暖气是什么意思? 如何给领导回信？开头怎么写，就是表示惶恐、惊喜的语气，如何组织语言。或者还有其他的好语言吗？谢谢 电流是标量还是矢量?为什么? 如何给领导写一封信 我欠网贷十几万!信用卡十几万!有套房能用房子跟银行抵债吗? 信用卡透支还不上可以用房产做抵押吗 电流有方向,为什么是标量 信用卡分期欠款近20万,没逾期,现在想做房屋抵押贷款能通过吗? 电流是按照矢量的计算规则还是标量的计算规则 我想用信用卡透支钱买房,然后用房子抵押贷款还信用卡行么 欠了40多万。信用卡。要怎么样说才能让家里人帮还呢？家里也是没钱。帮还的话，只能拿房子去抵押。 信用卡逾期这么多回,用房子做抵押,能办下贷款嘛。 信用卡欠50000万元,我有房子想卖,房子有抵押贷款怎么办 用房子做抵押办信用卡怎么办 房子被抵押信用卡又透支房产能不能转让 信用卡欠69万能像银行做房屋抵押贷款吗? 你给自己贴的标签是什么?
懂视IT 51dongshi.com 版权所有
Copyright © 2019-2024