图的广度优先搜索问题，我的代码超出时间限制求修改或给出新的答案，谢谢！

Question

Description
读入图的邻接矩阵以及一个顶点的编号（图中顶点的编号为从1开始的连续正整数。顶点在邻接矩阵的行和列上按编号递增的顺序排列。邻接矩阵中元素值为1，表示对应顶点间有一条边，元素值为0，表示对应顶点间没有边），输出从该顶点开始进行广度优先搜索（Breadth-First Search, BFS）的顶点访问序列。假设顶点数目<=100，并且，对于同一顶点的多个邻接顶点，按照顶点编号从小到大的顺序进行搜索。
Input
第一行为两个整数n和s (0<n<=100, 0<s<=100)，n表示图中顶点的数目，s为搜索的起始顶点的编号。
后面的n行表示图的邻接矩阵，每行为n个整数，相邻整数间用一个空格间隔。
Output
一行（行末没有换行符），表示从顶点s开始进行BFS的顶点访问序列，相邻顶点间用一个空格间隔。
Sample Input
Copy sample input to clipboard
4 3
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0
Sample Output
3 1 2 4

我的代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<string>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
#include<iomanip>
#include<cmath>
#include<ctime>
#include<climits>           
using namespace std;   
typedef int ElemType ;  
typedef int VrType  ;  
typedef char VertexType ;  
typedef struct ArcCell{  
    VrType adj;                                    
}ArcCell, AdjMatrix[111][111];  

typedef struct{  
    int vexs[111];  
    AdjMatrix arcs;                   
    int vexnum,arcnum;                 
}MGraph;  

bool visited[111]; 
int FirstAdjVex(MGraph G,int v){  
    int i ;  
    for(i = 0; i<G.vexnum; i++)  
        if( G.arcs[v][i].adj ) return i;  
    if(i == (G.vexnum  -1)) return -1;  
    return -1;   
}  

int NextAdjVex(MGraph G,int v,int w){  
    int i;  
    for( i = w+1; i<G.vexnum; i++) 
        if(G.arcs[v][i].adj) return i;  
    if(i == (G.vexnum  -1)) return -1;  
    return -1;  

} 

void CreatUDG(MGraph &G,int m,  int n){  
    int i,j;    
    G.arcnum = m;  
    G.vexnum = m;  
    for(i=0;i<G.vexnum;++i)  
        for(j=0;j<G.vexnum;++j){  
            cin>>G.arcs[i][j].adj;
        }  
    for(int i=0; i<m; i++){
        G.vexs[i]=i+1;
    }
    return ;          
}  

void DFS(MGraph G,int v){  
    visited[v] = true;  
    cout<<G.vexs[v]<<" ";  
    for(int w = FirstAdjVex(G,v); w>=0; w = NextAdjVex(G,v,w)){  
        if(!visited[w]) DFS(G,w); 
    }  
} 

void DFSTraverse(MGraph G,int n){
    int v;  
    for(v = n-1; v<G.vexnum; ++v) visited[v] = false;  
    for(v = n-1; v<G.vexnum; )   
        if(!visited[v]) DFS(G, v); 
        ++v;
}  

int main(){ 
    int m,n;
    cin>>m>>n; 
    MGraph G;  
    CreatUDG(G,m,n);   
    DFSTraverse(G,n);  
} 

Answer 1

//你用邻接矩阵存储，我的使用邻接表...

#include

#include

#define VERTEXNUM 5

//存放顶点的邻接表元素

typedef struct edge{

int vertex;

struct edge* next;

}st_edge;

//队列的元素

typedef struct qElement{

int value;

struct qElement* pre;

struct qElement* next;

}st_qElement;

//队列的前端和后端，最后一个入队列的元素为rear，第一个出队列的元素为front

st_qElement* front = NULL;

st_qElement* rear = NULL;

void createGraph(st_edge** edge, int start, int end);

void displayGraph(st_edge** edge);

void delGraph(st_edge** edge);

void BFT(st_edge** edge,int* vertexStatusArr);

void BFTcore(st_edge** edge,int i,int* vertexStatusArr);

void putQueue(int vertex);

int* getQueue();

void putRelatedInQueue(st_edge** edge, int vertex);

int main(void){

//动态创建存放边的指针数组

st_edge** edge = (st_edge**)malloc(sizeof(st_edge*)*VERTEXNUM);

int i;

for(i=0;i<VERTEXNUM;i++){

edge[i] = NULL;

}

    //存放顶点的遍历状态，0：未遍历，1：已遍历  
    int* vertexStatusArr = (int*)malloc(sizeof(int)*VERTEXNUM);  
    for(i=0;i<VERTEXNUM;i++){  
            vertexStatusArr[i] = 0;  
    }  

    printf("after init:\n");  
    displayGraph(edge);  
    //创建图  
    createGraph(edge,0,3);  
    createGraph(edge,0,4);  
    createGraph(edge,3,1);  
    createGraph(edge,3,2);  
    createGraph(edge,4,1);  

    printf("after create:\n");  
    displayGraph(edge);  

    //广度优先遍历  
    BFT(edge,vertexStatusArr);  

    //释放邻接表占用的内存  
    delGraph(edge);  
    edge = NULL;  
    free(vertexStatusArr);  
    vertexStatusArr = NULL;  
    return 0;  

}

//创建图

void createGraph(st_edge** edge, int start, int end){

st_edge* newedge = (st_edge*)malloc(sizeof(st_edge));

newedge->vertex = end;

newedge->next = NULL;

edge = edge + start;

while(*edge != NULL){

edge = &((*edge)->next);

}

*edge = newedge;

}

//打印存储的图

void displayGraph(st_edge** edge){

int i;

st_edge* p;

for(i=0;i printf("%d:",i);
p = *(edge+i);
while(p != NULL){
printf("%d ",p->vertex);

p = p->next;

}

printf("\n");

}

}

//释放邻接表占用的内存

void delGraph(st_edge** edge){

int i;

st_edge* p;

st_edge* del;

for(i=0;i p = *(edge+i);
while(p != NULL){
del = p;
p = p->next;

free(del);

}

edge[i] = NULL;

}

free(edge);

}

//广度优先遍历

void BFT(st_edge** edge,int* vertexStatusArr){

printf("start BFT graph:\n");

int i;

for(i=0;i<VERTEXNUM;i++){

BFTcore(edge,i,vertexStatusArr);

}

printf("\n");

}

void BFTcore(st_edge** edge,int i,int* vertexStatusArr){

putQueue(i);

int* qeValue = NULL;

while((qeValue = getQueue()) != NULL){

if(vertexStatusArr[*qeValue] == 0){

printf("%d ",*qeValue);

vertexStatusArr[*qeValue] = 1;

putRelatedInQueue(edge, *qeValue);

}

free(qeValue);

qeValue = NULL;

}

}

//将元素放到队列中

void putQueue(int vertex){

st_qElement* qe = (st_qElement*)malloc(sizeof(st_qElement));

qe->value = vertex;

qe->next = NULL;

qe->pre = NULL;

if(front == NULL || rear == NULL){

front = rear = qe;

}else{

rear->next = qe;

qe->pre = rear;

rear = qe;

}

}

//从队列中获取一个元素

int* getQueue(){

if(front == NULL || rear == NULL){

return NULL;

}else{

int* res = (int*)malloc(sizeof(int));

*res = front->value;

            st_qElement* p = front;  
            front = front->next;  
            if(front == NULL){  
                    rear = front;  
            }else{  
                    front->pre = NULL;  
            }  
            free(p);  
            p = NULL;  
            return res;  
    }  

}

//将顶点关联的元素放到队列中

void putRelatedInQueue(st_edge** edge, int vertex){

st_edge* p = *(edge+vertex);

while(p != NULL){

putQueue(p->vertex);

p = p->next;

}

}