dragonir 2015-11-30 10:57 采纳率: 100%
浏览 1859
已采纳

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

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);  
} 
  • 写回答

1条回答 默认 最新

  • 普通网友 2015-12-02 07:20
    关注

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

    #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;

    }

    }

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 已采纳回答 9月30日

悬赏问题

  • ¥15 英飞凌TC387使用MCAL唤醒TJA1145问题
  • ¥15 android tv图标显示异常
  • ¥20 (标签-AR|关键词-预测分析)
  • ¥15 MATLAB矩阵分离问题
  • ¥15 QT IFW 自定义界面添加lineedit小键盘输入数字无效果
  • ¥15 python thinter动态建立Entry并读取数据
  • ¥150 电路仿真,演示反激变压器升压
  • ¥100 libcurl使用无法连接服务器问题
  • ¥30 链表栈表达式求值求解
  • ¥15 关于龙芯1b,JTAG停止调试服务