數(shù)據(jù)結(jié)構(gòu)（C實(shí)現(xiàn)）------- 圖的廣度優(yōu)先遍歷
來源：程序員人生 發(fā)布時(shí)間：2015-01-21 09:00:02 閱讀次數(shù)：3720次
[本文是自己學(xué)習(xí)所做筆記，歡迎轉(zhuǎn)載，但請(qǐng)注明出處：http://blog.csdn.net/jesson20121020]
算法描寫：
設(shè)圖G的初始狀態(tài)是所有頂點(diǎn)均未被訪問過，在G中的任選1頂點(diǎn)vi為初始動(dòng)身點(diǎn)，則廣度優(yōu)先遍歷 可定義以下：首先，訪問初始動(dòng)身點(diǎn)vi，接著順次訪問vi的所有鄰接點(diǎn)w1,w2,...,wk;然后，順次訪問w1,w2,...,wk 的鄰接的所有未被訪問過的頂點(diǎn)，順次類推，直到圖中所有的和初始點(diǎn)vi有路徑相通的頂點(diǎn)都被訪問過為止。
算法實(shí)現(xiàn)：
(1) 訪問初始頂點(diǎn)vi
(2) 置頂點(diǎn)v已訪問標(biāo)記
(3) 頂點(diǎn)v入隊(duì)
(4) while(隊(duì)不空)｛
取出隊(duì)首頂點(diǎn)i；
順次搜索頂點(diǎn)i的所有的鄰接點(diǎn)；
如果未被訪問，則訪問該鄰接點(diǎn)，并將其入隊(duì)。
｝
用鄰接矩陣實(shí)現(xiàn)圖的廣度優(yōu)先遍歷的源代碼以下：
/**
* 廣度遍歷圖
**/
void BFS_MG(MGraph MG,int s){
//清空訪問標(biāo)志
init_Visit();
//定義隊(duì)列，用于保存當(dāng)前節(jié)點(diǎn)的鄰接頂點(diǎn)
int Q[MAX_VEX_NUM];
int front = 0;
int rear = 0;
int i,j,k;
printf("%c ",MG.vexs[s]);
visit[s] = 1;
Q[rear++] = s;
//遍歷隊(duì)列
while(front < rear){
i = Q[front++];
for (j = 1; j <= MG.vexnum;j++){
if(visit[j] == 0 && MG.arcs[i][j] == 1){
printf("%c ",MG.vexs[j]);
visit[j] = 1;
Q[rear++] = j;
}
}
}
}
用鄰接表實(shí)現(xiàn)圖的廣度優(yōu)先遍歷的源代碼以下：
/**
* 廣度遍歷圖
**/
void BFS_AG(ALGraph AG,int s){
ArcPtr p;
//清空訪問標(biāo)志
init_Visit();
//定義隊(duì)列，用于保存當(dāng)前節(jié)點(diǎn)的鄰接頂點(diǎn)
int Q[MAX_VERTEX_NUM];
int front = 0;
int rear = 0;
int i,j,k;
printf("%c ",AG.vertices[s]);
visit[s] = 1;
Q[rear++] = s;
//遍歷隊(duì)列
while(front < rear){
i = Q[front++];
for(p = AG.vertices[i].firstarc;p;p=p->nextarc){
j = p->adjvex;
if(visit[j] == 0){
printf("%c ",AG.vertices[j].vexdata);
visit[j] = 1;
Q[rear++] = j;
}
}
}
}
算法說明：
對(duì)有具有n個(gè)頂點(diǎn)和e條邊的連通圖，由于每一個(gè)基點(diǎn)均需要入隊(duì)1次，所以while語句需要履行n次，對(duì)鄰接矩陣而言，內(nèi)循環(huán)搜索鄰接點(diǎn)時(shí)一樣需要履行n次，故BFS_MG的時(shí)間復(fù)雜度為O(n^2)；對(duì)鄰接表而言，內(nèi)循環(huán)的次數(shù)取決于各頂點(diǎn)的邊表結(jié)點(diǎn)的總個(gè)數(shù)，所以BFS_AG的時(shí)間復(fù)雜度為O(n+e)。
可以看出，廣度優(yōu)先遍歷需要1個(gè)輔助隊(duì)列，和標(biāo)志數(shù)組，故空間復(fù)雜度為O(n)。
完全代碼：
用鄰接矩陣實(shí)現(xiàn)廣度優(yōu)先遍歷的完全代碼：
/*
============================================================================
Name : Graph.c
Author : jesson20121020
Version : 1.0
Description : create Graph using Adjacency Matrix, Ansi-style
============================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_VEX_NUM 50
typedef char VertexType;
typedef enum {
DG, UDG
} GraphType;
typedef struct {
VertexType vexs[MAX_VEX_NUM];
int arcs[MAX_VEX_NUM][MAX_VEX_NUM];
int vexnum, arcnum;
GraphType type;
} MGraph;
//設(shè)置圖中頂點(diǎn)訪問標(biāo)志
int visit[MAX_VEX_NUM];
/**
* 根據(jù)名稱得到指定頂點(diǎn)在頂點(diǎn)集合中的下標(biāo)
* vex 頂點(diǎn)
* return 如果找到，則返回下標(biāo)，否則，返回０
*/
int getIndexOfVexs(char vex, MGraph *MG) {
int i;
for (i = 1; i <= MG->vexnum; i++) {
if (MG->vexs[i] == vex) {
return i;
}
}
return 0;
}
/**
* 創(chuàng)建鄰接矩陣
*/
void create_MG(MGraph *MG) {
int i, j, k;
int v1, v2, type;
char c1, c2;
printf("Please input graph type DG(0) or UDG(1) :");
scanf("%d", &type);
if (type == 0)
MG->type = DG;
else if (type == 1)
MG->type = UDG;
else {
printf("Please input correct graph type DG(0) or UDG(1)!");
return;
}
printf("Please input vexmun : ");
scanf("%d", &MG->vexnum);
printf("Please input arcnum : ");
scanf("%d", &MG->arcnum);
getchar();
for (i = 1; i <= MG->vexnum; i++) {
printf("Please input %dth vex(char):", i);
scanf("%c", &MG->vexs[i]);
getchar();
}
//初始化鄰接矩陣
for (i = 1; i <= MG->vexnum; i++) {
for (j = 1; j <= MG->vexnum; j++) {
MG->arcs[i][j] = 0;
}
}
//輸入邊的信息，建立鄰接矩陣
for (k = 1; k <= MG->arcnum; k++) {
printf("Please input %dth arc v1(char) v2(char) : ", k);
scanf("%c %c", &c1, &c2);
v1 = getIndexOfVexs(c1, MG);
v2 = getIndexOfVexs(c2, MG);
if (MG->type == 1)
MG->arcs[v1][v2] = MG->arcs[v2][v1] = 1;
else
MG->arcs[v1][v2] = 1;
getchar();
}
}
/**
* 打印鄰接矩陣和頂點(diǎn)信息
*/
void print_MG(MGraph MG) {
int i, j;
if(MG.type == DG){
printf("Graph type: Direct graph
");
}
else{
printf("Graph type: Undirect graph
");
}
printf("Graph vertex number: %d
",MG.vexnum);
printf("Graph arc number: %d
",MG.arcnum);
printf("Vertex set:
");
for (i = 1; i <= MG.vexnum; i++)
printf("%c ", MG.vexs[i]);
printf("
Adjacency Matrix:
");
for (i = 1; i <= MG.vexnum; i++) {
j = 1;
for (; j < MG.vexnum; j++) {
printf("%d ", MG.arcs[i][j]);
}
printf("%d
", MG.arcs[i][j]);
}
}
/**
* 初始化頂點(diǎn)訪問標(biāo)志
**/
void init_Visit(){
int i;
for(i = 0;i < MAX_VEX_NUM;i++)
visit[i] = 0;
}
/**
* 廣度遍歷圖
**/
void BFS_MG(MGraph MG,int s){
//清空訪問標(biāo)志
init_Visit();
//定義隊(duì)列，用于保存當(dāng)前節(jié)點(diǎn)的鄰接頂點(diǎn)
int Q[MAX_VEX_NUM];
int front = 0;
int rear = 0;
int i,j,k;
printf("%c ",MG.vexs[s]);
visit[s] = 1;
Q[rear++] = s;
//遍歷隊(duì)列
while(front < rear){
i = Q[front++];
for (j = 1; j <= MG.vexnum;j++){
if(visit[j] == 0 && MG.arcs[i][j] == 1){
printf("%c ",MG.vexs[j]);
visit[j] = 1;
Q[rear++] = j;
}
}
}
}
/**
* 主函數(shù)
*/
int main(void) {
MGraph MG;
create_MG(&MG);
print_MG(MG);
printf("
The result of BFS:
");
BFS_MG(MG,1);
return EXIT_SUCCESS;
}
用鄰接表實(shí)現(xiàn)廣度優(yōu)先遍歷的完全代碼：
/*
============================================================================
Name : ALGraph.c
Author : jesson20121020
Version :
Copyright : Your copyright notice
Description : Graph using linkList, Ansi-style
============================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdio.h>
#define MAX_VERTEX_NUM 50
typedef enum {
DG, UDG
} GraphType;
typedef char VertexType;
//表節(jié)點(diǎn)
typedef struct ArcNode {
int adjvex; //鄰接節(jié)點(diǎn)
int weight; //邊權(quán)重
struct ArcNode *nextarc; //下1個(gè)節(jié)點(diǎn)指針
} ArcNode, *ArcPtr;
//頭節(jié)點(diǎn)
typedef struct {
VertexType vexdata;
int id;
ArcPtr firstarc;
} VNode;
//頭節(jié)點(diǎn)數(shù)組
typedef struct {
VNode vertices[MAX_VERTEX_NUM];
int vexnum, arcnum;
GraphType type;
} ALGraph;
int visit[MAX_VERTEX_NUM];
/**
* 根據(jù)頂點(diǎn)字符得到在頂點(diǎn)數(shù)組中的下標(biāo)
*/
int getIndexOfVexs(char vex, ALGraph *AG) {
int i;
for (i = 1; i <= AG->vexnum; i++) {
if (AG->vertices[i].vexdata == vex) {
return i;
}
}
return 0;
}
/**
* 創(chuàng)建鄰接表
*/
void create_AG(ALGraph *AG) {
ArcPtr p,q;
int i, j, k, type;
VertexType v1, v2;
printf("Please input graph type UG(0) or UDG(1) :");
scanf("%d", &type);
if (type == 0)
AG->type = DG;
else if (type == 1)
AG->type = UDG;
else {
printf("Please input correct graph type UG(0) or UDG(1)!");
return;
}
printf("please input vexnum:");
scanf("%d", &AG->vexnum);
printf("please input arcnum:");
scanf("%d", &AG->arcnum);
getchar();
for (i = 1; i <= AG->vexnum; i++) {
printf("please input the %dth vex(char) : ", i);
scanf("%c", &AG->vertices[i].vexdata);
getchar();
AG->vertices[i].firstarc = NULL;
}
for (k = 1; k <= AG->arcnum; k++) {
printf("please input the %dth arc v1(char) v2(char) :", k);
scanf("%c %c", &v1, &v2);
i = getIndexOfVexs(v1, AG);
j = getIndexOfVexs(v2, AG);
//根據(jù)圖的類型創(chuàng)建鄰接表
//方法1，插入到鏈表頭
/*
if (AG->type == DG) { //有向圖
p = (ArcPtr) malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = AG->vertices[i].firstarc;
AG->vertices[i].firstarc = p;
} else { //無向圖
p = (ArcPtr) malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = AG->vertices[i].firstarc;
AG->vertices[i].firstarc = p;
p = (ArcPtr) malloc(sizeof(ArcNode));
p->adjvex = i;
p->nextarc = AG->vertices[j].firstarc;
AG->vertices[j].firstarc = p;
}
*/
//方法2，插入到鏈表尾
if (AG->type == DG) { //有向圖
p = (ArcPtr) malloc(sizeof(ArcNode));
p->adjvex = j;
//表為空
if(AG->vertices[i].firstarc == NULL){
AG->vertices[i].firstarc = p;
}
else{
//找最后1個(gè)表節(jié)點(diǎn)
q = AG->vertices[i].firstarc;
while(q->nextarc != NULL){
q = q->nextarc;
}
q->nextarc = p;
}
p->nextarc = NULL;
} else { //無向圖
p = (ArcPtr) malloc(sizeof(ArcNode));
p->adjvex = j;
//表為空
if(AG->vertices[i].firstarc == NULL){
AG->vertices[i].firstarc = p;
}
else{
//找最后1個(gè)表節(jié)點(diǎn)
q = AG->vertices[i].firstarc;
while(q->nextarc != NULL){
q = q->nextarc;
}
q->nextarc = p;
}
p->nextarc = NULL;
p = (ArcPtr) malloc(sizeof(ArcNode));
p->adjvex = i;
//表為空
if(AG->vertices[j].firstarc == NULL){
AG->vertices[j].firstarc = p;
}
else{
//找最后1個(gè)表節(jié)點(diǎn)
q = AG->vertices[j].firstarc;
while(q->nextarc != NULL){
q = q->nextarc;
}
q->nextarc = p;
}
p->nextarc = NULL;
}
getchar();
}
}
/**
* 輸出圖的相干信息
*/
void print_AG(ALGraph AG) {
ArcPtr p;
int i;
if (AG.type == DG) {
printf("Graph type: Direct graph
");
} else {
printf("Graph type: Undirect graph
");
}
printf("Graph vertex number: %d
", AG.vexnum);
printf("Graph arc number: %d
", AG.arcnum);
printf("Vertex set :
");
for (i = 1; i <= AG.vexnum; i++)
printf("%c ", AG.vertices[i].vexdata);
printf("
Adjacency List:
");
for (i = 1; i <= AG.vexnum; i++) {
printf("%d", i);
p = AG.vertices[i].firstarc;
while (p != NULL) {
printf("-->%d", p->adjvex);
p = p->nextarc;
}
printf("
");
}
}
/**
* 初始化頂點(diǎn)訪問標(biāo)志
**/
void init_Visit(){
int i;
for(i = 0;i < MAX_VERTEX_NUM;i++)
visit[i] = 0;
}
/**
* 廣度遍歷圖
**/
void BFS_AG(ALGraph AG,int s){
ArcPtr p;
//清空訪問標(biāo)志
init_Visit();
//定義隊(duì)列，用于保存當(dāng)前節(jié)點(diǎn)的鄰接頂點(diǎn)
int Q[MAX_VERTEX_NUM];
int front = 0;
int rear = 0;
int i,j,k;
printf("%c ",AG.vertices[s]);
visit[s] = 1;
Q[rear++] = s;
//遍歷隊(duì)列
while(front < rear){
i = Q[front++];
for(p = AG.vertices[i].firstarc;p;p=p->nextarc){
j = p->adjvex;
if(visit[j] == 0){
printf("%c ",AG.vertices[j].vexdata);
visit[j] = 1;
Q[rear++] = j;
}
}
}
}
int main(void) {
ALGraph AG;
create_AG(&AG);
print_AG(AG);
printf("
The result of BFS:
");
BFS_AG(AG,1);
return EXIT_SUCCESS;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
