【数据结构—图】邻接表与邻接矩阵的广度优先BFS遍历
·
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MaxSize 50
//邻接矩阵
void BFS(MGraph G,int v,int *visited){
int queue[MaxSize],front = -1,rear = -1; //空间:O(n)
queue[++rear] = v;
visited[v] = 1;
printf("%d",G.vex[v]);
while(front != rear){ //当队列不为空时
v = queue[+//找不是联通的点//找不是联通的点//找不是联通的点//找不是联通的点+front]; //取队头,将v出队
for(int i = 0;i < G.vexnum;i++){ //时间:O(|v|)
if(G.edge[v][i]!=0 && visited[i]==0){
queue[++rear] = v;
visited[i] = 1;
printf("%c",G.vex[i]);
}
}
}
} //时间:O(|v|)
//空间:O(n)
void BFSTravelers(MGraph G){
int visited[MaxSize]; //空间:O(n)
//int *visited = (int*)malloc(sizeof(G.vexnum));
//这里也可以直接动态申请
for(int i=0;i < G.vexnum;i++){ //时间:O(|v|)
visited[i] = 0; //初始化
}
for(int i = 0;i < G.vexnum;i++){ //时间:O(|v|)
if(visited[i] == 0){
BFS(G,i,visited); //时间:O(|v|)
//空间:O(n)
}
} //时间:O(|v|^2)
//空间:O(2n)~O(n)
} //时间:O(|v|^2)
//空间:O(2n)~O(n)
//邻接表
void BFS(AdGraph G,int v,int *visited){
int queue[MaxSize],front = -1,rear = -1 //空间:O(n)
queue[++rear] = v;
visited[v] = 1;
printf("%c",G.vertices[p->adjvex].value);
while(front != rear){ //当队列不为空
v = queue[++front]; //取队头,将v出队
ArcNode *p = G.vertices[v].first;
while(p != NULL){ //时间:O(|E|)
queue[++rear] = p->adjvex;
visited[p->adjvex] = i;
printf("%c",G.vertices[p->adjvex].value);
}
p = p->next;
}
} //空间:O(n)
//时间:O(E)
void BFSTraveler(AdGraph G){
int visited[MaxSize]; //空间:O(n)
for(int i = 0;i < G.vexnum;i++){ //时间:O(|v|)
visited[i] = 0; //初始化
}
for(int i = 0;i < G.vexnum;i++){ //为了找不联通的点O(|v|)
if(visited[i] == 0){ //从未被访问过
//找到了:1.不连通的点
// 2.从未被访问过
//就开始进行 广度优先BFS 遍历
//将与v连通的点全部遍历
//然后再找不连通的点
BFS(G,i,visited); //时间:O(|E|)
}
} //时间:O(|v|+|E|)
//空间:O(2n) ~ O(n)
} //时间:O(|v|+|E|)
//空间:O(2n) ~ O(n)
//总结:
//1.邻接矩阵:1.空间复杂度:O(n)
// 2.时间复杂度:O(|V|^2)
//2.邻接表:1.空间复杂度:O(n)
// 2.时间复杂度:O(|v|+|E|)
更多推荐


所有评论(0)