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);
}
//你用邻接矩阵存储，我的使用邻接表...
#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;
}
}