dragonir 2015-11-30 10:57 采纳率: 100%

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

Description

Input

Output

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{

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

bool visited[111];
int i ;
for(i = 0; i<G.vexnum; i++)
if(i == (G.vexnum  -1)) return -1;
return -1;
}

int i;
for( i = w+1; i<G.vexnum; 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){
}
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]<<" ";
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停止调试服务