一个无向图的邻接矩阵从某一点进行深度优先搜索遍历和广度优先搜索遍历可能的遍历序列是不是有很多种
该回答通过自己思路及引用到GPTᴼᴾᴱᴺᴬᴵ搜索,得到内容具体如下：
对于一个给定的无向图和起始点，深度优先搜索遍历和广度优先搜索遍历可能的遍历序列是不同的。下面是一些关于这两种搜索方法的特点和可能的遍历序列的说明：
深度优先搜索遍历：
广度优先搜索遍历：
总之，对于一个给定的无向图和起始点，深度优先搜索遍历和广度优先搜索遍历可能的遍历序列是不同的，但是它们都能够遍历到图中的所有节点。同时，在遍历过程中，可能存在多个等效的遍历序列，但是它们都会访问到同样的节点。
如果以上回答对您有所帮助，点击一下采纳该答案～谢谢
图采用邻接矩阵表示，实现无向图的深度优先搜索与有向图的广度优先搜索。
#include "stdio.h"
#include "stdlib.h"
#define MAX_VERTEX_NUM 20//最大顶点个数
typedef struct {
char vexs[MAX_VERTEX_NUM];//存放节点
int visited[MAX_VERTEX_NUM];//访问标志
int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum;//结点个数,边的个数
}mgraph,*Mgraph;
//广度优先遍历需要的循环队列
typedef struct {
int base[MAX_VERTEX_NUM];
int front,rear;
}SqQueue;
void InitQueue(SqQueue *Q){
Q->front = Q->rear = 0;
}
void EnQueue(SqQueue *q,int e){
q->base[q->rear]=e;
q->rear++;
}
void DeQueue(SqQueue *q,int *e){
*e=q->base[q->front];
q->front++;
}
int emptyQueue(SqQueue *q){ //队列是否满函数
if((q->rear+1)%(MAX_VERTEX_NUM-1)==q->front)
return 1;
return 0;
}
//增加节点
void add_vexs(Mgraph *g){
char c;
printf("请输入节点值,以#结束: \n");
scanf("%c",&c);
while(c!='#'){
(*g)->vexs[(*g)->vexnum]=c;
(*g)->vexnum++;//累计结点个数
getchar();
scanf("%c",&c);
}
printf("输入完毕！！！\n");
printf("%d\n",(*g)->vexnum);
}
//无向图增加边
void add_arc_w(Mgraph *g){
char v1,v2;
int row=0,col=0;
printf("请输入边的个数：\n");
scanf("%d",&((*g)->arcnum));
printf("请输入每条边的端点\n");
for(int i=0;i<(*g)->arcnum;i++)//控制边的个数
{
getchar();
scanf("%c %c",&v1,&v2);
for(int j = 0; j < (*g)->vexnum; j++)
{
if((*g)->vexs[j] == v1)
row = j;
if((*g)->vexs[j] == v2)
col=j;
}
(*g)->matrix[row][col] = 1;
printf("matrix[%d][%d]=1\n",row,col);
(*g)->matrix[col][row] = 1;//行和列在无向图的邻接矩阵是对称的
}
}
//有向图增加边
void add_arc_y(Mgraph *g) {
char v1,v2;
int row=0,col=0;
printf("请输入边的个数：\n");
scanf("%d",&((*g)->arcnum));
printf("请输入每条边的端点\n");
for(int i=0;i<(*g)->arcnum;i++)//控制边的个数
{
getchar();
scanf("%c %c",&v1,&v2);
for(int j = 0; j < (*g)->vexnum; j++)
{
if((*g)->vexs[j] == v1)
row = j;
if((*g)->vexs[j] == v2)
col=j;
}
(*g)->matrix[row][col] = 1;
printf("matrix[%d][%d]=1\n",row,col);
}
}
//初始化图
void init_mgraph(Mgraph *g){
int i,j;
(*g)=(Mgraph)malloc(sizeof(mgraph));
(*g)->vexnum=(*g)->arcnum=0;
for(i=0;i<MAX_VERTEX_NUM;i++){
(*g)->vexs[i]=0;//节点值初始化为0
(*g)->visited[i] = 0;//访问标志初始化为0
}
for(i=0;i<MAX_VERTEX_NUM;i++)
for(j=0;j<MAX_VERTEX_NUM;j++){
(*g)->matrix[i][j]=0;//初始化矩阵
}
add_vexs(g);
add_arc_w(g);
}
void visited(Mgraph *g,int i)
{
printf("%c ",(*g)->vexs[i]);
(*g)->visited[i] = 1;
}
//深度遍历算法
void DFS(Mgraph *g,int i)
{
visited(g,i);
for (int j = 0; j < (*g)->vexnum; j++)
{
if((*g)->matrix[i][j] && !(*g)->visited[j])
{
DFS(g,j); //对v的尚未访问的邻接顶点w
}
}
}
void DFSTraverse(Mgraph *g){
int i;
for (i=0; i<(*g)->vexnum; ++i){
if (!(*g)->visited[i])
DFS(g, i); //对尚未访问的顶点调用DFS
}
}
//广度遍历算法
void BFS(Mgraph *g,int nowi,SqQueue *Q){
int i,j;
for(i=nowi;i<(*g)->vexnum;i++)
{
if(!(*g)->visited[i]){
visited(g,i);
EnQueue(Q,i);//入队
while(!emptyQueue(Q)){
DeQueue(Q,&i);//队首元素出队置为u
for (j=0; j<(*g)->vexnum; ++j){
if (!(*g)->visited[j] && (*g)->matrix[i][j]){
visited(g,j);
EnQueue(Q,j);
}//if
}//for
}
}//if
}//for
}//BFS
void BFSTraverse(Mgraph *g){
SqQueue Q;
InitQueue(&Q);
int i;
for (i=0; i<(*g)->vexnum; ++i){
if (!(*g)->visited[i])
BFS(g,i,&Q); //对尚未访问的顶点调用DFS
}
}
//打印邻接矩阵
void print_mgraph(Mgraph g){
printf("邻接矩阵为：\n");
for(int i=0;i<g->vexnum;i++){
printf("%3c",g->vexs[i]);
}
printf("\n");
for(int i=0;i<g->vexnum;i++){
printf("%c ",g->vexs[i]);
for(int j=0;j<g->vexnum;j++){
printf("%2d ",g->matrix[i][j]);
}
printf("\n");
}
}
int main(){
Mgraph g1,g2;//g1为无向图，g2为有向图
init_mgraph(&g1);
print_mgraph(g1);
printf("图的DFS遍历结果：\n");
DFSTraverse(&g1);
getchar();
printf("\n");
init_mgraph(&g2);
print_mgraph(g2);
printf("图的BFS遍历结果：\n");
BFSTraverse(&g2);
return 0;
}