问题 F: 案例6-1.2：邻接表存储图的广度优先遍历

题目描述

一个图有n个节点编号从0至n-1和m条边编号从0至m-1。 输出从点x开始的广度优先遍历顺序。

输入格式

第一行为n、m、x。 
接下来m行每行有一组u,v。表示点u可以到达点v，点v也可以到达点u。

输出格式

输出经过点的顺序。（输出字典序最小的答案）

输入样例

7 9 5
0 3
0 2
0 4
3 1
3 2
4 5
1 5
2 5
5 6

输出样例  

5 1 2 4 6 3 0

代码展示 

emmm函数不一定全用上了有些是别的题留下的为了之后方便使用没删

#include
#include
#include
#include
using namespace std;
 
#define MAX_SIZE 100
 //领接矩阵存储的图
struct Graph{
    int vexNumber;
    string vexInfo[MAX_SIZE];
    int adjMatrix[MAX_SIZE][MAX_SIZE];
};
 //弧结点定义
struct ArcNode{
    int weight;//弧上的信息部分
    int adj;//邻接点的序号
    ArcNode *nextarc;
};
 //顶点结点定义
struct VexNode{
    string Info;
    ArcNode *firstarc;
};
 //领接表结构的图的定义
struct linkGraph{
    VexNode *vexes;
    int vexnumber;
};
  
int preInitGraph(linkGraph &G,const Graph &g){
    G.vexes=new VexNode[g.vexNumber];
    G.vexnumber=g.vexNumber;
    for(int i=0;i
        G.vexes[i].firstarc=NULL;
        G.vexes[i].Info=g.vexInfo[i];
    }
    return 0;
}
//将邻接矩阵存储的图转换为领接表存储的图
void InitGraph(linkGraph &G,const Graph &g){
    preInitGraph(G,g);
    for(int i=0;i
        for(int j=0;j
            if(g.adjMatrix[i][j]==1){
                ArcNode *p=new ArcNode();
                p->nextarc=NULL;
                p->adj=j;
                ArcNode *q=G.vexes[i].firstarc;
                if(G.vexes[i].firstarc==NULL)
                    G.vexes[i].firstarc=p;
                else{
                    while(q->nextarc!=NULL){
                        q=q->nextarc;
                    }
                    q->nextarc=p;
                }
            }
        }
    }
}
 
int DestroyGraph(linkGraph &G){
    for(int i=0;i
        while(G.vexes[i].firstarc!=NULL){
            ArcNode *p=G.vexes[i].firstarc;
            G.vexes[i].firstarc=p->nextarc;
            delete p;
        }
    }
    delete[]G.vexes;
    G.vexes=NULL;
    G.vexnumber=0;
    return 0;
}
//输出领接表存储的图
void PrintGraph(const linkGraph &G){
    for(int i=0;i
        cout<
        ArcNode *p=G.vexes[i].firstarc;
        while(p!=NULL){
            cout<<" --> "<adj].Info;
            p=p->nextarc;
        }
        cout<
    }
}
//查找v0的未被访问的邻接点
int findAdjVex(const Graph &G,int v0,int visited[]){
 
}
//以顶点v0为起点，进行一趟DFS
string oneDFS(const linkGraph &G,int v0,int visited[],string &result){
    result+=G.vexes[v0].Info;
    result+=" ";
    stacks;
    ArcNode *p=G.vexes[v0].firstarc;
    s.push(p);
    while(!s.empty()){
        ArcNode *vNode=s.top();
        for(p=vNode;p!=NULL;p=p->nextarc){
            if(visited[p->adj]==0){
                result+=G.vexes[p->adj].Info;
                result+=" ";
                visited[p->adj]=1;
                if(p->nextarc!=NULL)  s.push(p->nextarc);
                break;
            }
        }
        if(p==NULL)  s.pop();
    }
 
    return result;
}
//对整个图进行DFS
string DFS(const Graph &G){
    string result="";
    linkGraph LG;
    InitGraph(LG,G);
    //test
    //PrintGraph(LG);
    int *visited=new int[G.vexNumber];
    for(int i=0;i
        visited[i]=0;//初始化visited数组
    for(int i=0;i
        if(!visited[i]){//以每个未被遍历的顶点为起点，进行DFS
            result=oneDFS(LG,i,visited,result);
        }
    }
    delete[]visited;
 
    return result;
}
 
 
 
int oneBFS(Graph &G,int v0,int visited[]){
    linkGraph LG;
    InitGraph(LG,G);
    queue<int>q;
    q.push(v0);
    visited[v0]=1;
    while(!q.empty()){
        int v=q.front();
        q.pop();
        cout<" ";
        for(ArcNode *p=LG.vexes[v].firstarc;p!=NULL;p=p->nextarc){
            if(!visited[p->adj]){
                q.push(p->adj);
                visited[p->adj]=1;
            }
        }
    }
    return 0;
}
 
 
int BFS(Graph &G,int x){
    int *visited=new int[G.vexNumber];
    for(int i=0;i
        visited[i]=0;
    for(int i=x;i
        if(!visited[i])
            oneBFS(G,i,visited);
    }
    delete[]visited;
    return 0;
}
 
 
//comment
 
int main(){
    //freopen("/config/workspace/test/test","r",stdin);
    int n,m,x;
    cin>>n>>m>>x;
    if(n==0){
        cout<<0;
        return 0;
    }
    Graph G;
    G.vexNumber=n;
    for(int i=0;i
        G.vexInfo[i]=to_string(i);
    }
    G.adjMatrix[MAX_SIZE][MAX_SIZE]={0};
    for(int i=0;i
        int a,b;
        cin>>a>>b;
        G.adjMatrix[a][b]=1;
        G.adjMatrix[b][a]=1;
    }
    BFS(G,x);
    return 0;
}