图的广度优先遍历

图这一章我一直觉得自己没学好。。。所以这次就直接放代码,不多说什么了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
typedef int Boolean;			//Boolean是布尔类型,其值为TRUE 或者FLASE
Boolean visited[MAXVEX]; //访问标志的数组

#define QElemType int // 元素类型定义为图结点
#define MAXSIZE 1000

typedef struct {
QElemType data[MAXSIZE];
int front;
int rear;
}SqQueue;

/*----------以下为队列的基本操作函数----------*/

/*初始化一个空队列*/
Status InitQueue(SqQueue *Q){
if (!Q)return ERROR; //若空间分配失败,则返回ERROR
Q->front = 0;
Q->rear = 0;
return OK;
}

/*判断SqQueue是否为空*/
Status IsQueueEmpty(SqQueue Q){
if (Q.rear == Q.front)return TRUE; //若尾指针指向头指针,则为空队列,返回TRUE
else{ return FALSE; } //否则返回FALSE
}

/*插入元素e为新的队尾元素*/
Status EnQueue(SqQueue *Q, QElemType e){
if ((Q->rear + 1) % MAXSIZE == Q->front)return ERROR; // 若队列已满,则返回ERROR
Q->data[Q->rear] = e; //e 入队列
Q->rear = (Q->rear + 1) % MAXSIZE; //队尾指针后移
return OK;
}

/*若队列不空,则删除队头元素,并用e返回其值*/
Status DeQueue(SqQueue *Q, QElemType *e){
if (Q->front == Q->rear)return ERROR; //若队列为空,则返回ERROR
*e = Q->data[Q->front]; //若队列不为空,用e接收队头元素
Q->front = (Q->front + 1) % MAXSIZE; //队头指针后移
return OK;
}
/*----------队列的基本操作函数完----------*/

/*----------以下为广度优先遍历算法---------*/
void BFSTraverse(GraphAdjList G){
int i;
SqQueue Q;
EdgeNode* p;

for (i = 0; i < G.numVertexes; i++){
visited[i] = FALSE;
}

InitQueue(&Q); //初始化一辅助用的队列

for (i = 0; i < G.numVertexes; i++){ //对每一个顶点做循环
if (!visited[i]){ //若未访问过,则如下处理
visited[i] = TRUE; //将当前结点设为已访问
printf("%c", G.adjList[i].data);//打印顶点,也可以改为其它操作
EnQueue(&Q, i); //将该顶点入队列
while (!IsQueueEmpty(Q)){
DeQueue(&Q, &i); //将队头元素出队,并赋给e
p = G.adjList[i].firstedge; //找到当前顶点边表头指针
while (p){
if (!visited[p->adjvex]){//若当前结点未被访问过
printf("%c", G.adjList[p->adjvex].data);
EnQueue(&Q, p->adjvex);
}
p = p->next; //指针指向下一个邻接点
}
}
}
}
}