BFS广度优先

题目描述如下：
使用邻接矩阵实现BFS：

输入
8,10
1
2
3
4
5
6
7
8
1,2
1,5
2,6
3,6
3,4
3,7
4,7
4,8
6,7
7,8
2
输出
请输入顶点数和边数:请输入顶点本身的数据:
请输入边的数据:
0 1 0 0 1 0 0 0
1 0 0 0 0 1 0 0
0 0 0 1 0 1 1 0
0 0 1 0 0 0 1 1
1 0 0 0 0 0 0 0
0 1 1 0 0 0 1 0
0 0 1 1 0 1 0 1
0 0 0 1 0 0 1 0
输入BFS遍历的起始结点：2 1 6 5 3 7 4 8

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include
//#include 
#define MAX_VERTICES 100 //假设图有100个顶点
#define MAX_WEIGHT 32767 //加权图（网）不邻接时为10000，但输出为“∞”
#define Maxsize 100

typedef struct
{
	int Vertices[MAX_VERTICES]; //顶点信息的数组
	int AdjacencyMatrix[MAX_VERTICES][MAX_VERTICES]; //边信息的数组。
	int numV; //当前的顶点数
	int numA; //当前的边数
}AdMatrix;
typedef struct
{
	int  *base;
	int front;
	int rear;
}CyQueue;


//图的生成函数
void CreateGraph(AdMatrix *G)
{
    int n, e, vi, vj;
	printf("请输入顶点数和边数:");
	scanf("%d,%d", &n, &e);
	G->numV = n;
	G->numA = e;
	//Vertices数组的创建
	printf("请输入顶点本身的数据:\n");
	for (int i = 0; i < G->numV; i++)
	{

		scanf("%d", &G->Vertices[i]);
	}
	//AdjacencyMatrix数组的建立
	printf("请输入边的数据:\n");
	for (int i = 0; i < G->numA; i++)
	{
		scanf("%d,%d", &vi, &vj);
		G->AdjacencyMatrix[vi - 1][vj - 1] = 1;
		G->AdjacencyMatrix[vj - 1][vi - 1] = 1;
	}
}
//输出邻接矩阵的信息
void ShowGraph(AdMatrix *G)
{
	int i, j;
	for (i = 0; i < G->numV; i++)
	{
		//printf("\n%d ", i + 1);
		for (j = 0; j < G->numV; j++)
		{
			/*if (G->AdjacencyMatrix[i][j] == MAX_WEIGHT)
			{
				printf("%s ", "∞");
			}
			else
			{
				printf("%d ", G->AdjacencyMatrix[i][j]);
			}*/
			printf("%d ", G->AdjacencyMatrix[i][j]);
		}
		printf("\n");
	}
}


/*循环队列基本操作*/
void create(CyQueue *q)
{
	q->base=(int  *)malloc(Maxsize*sizeof(int));
	if(!q->base)
	{
		printf("Space allocation failed!\n");
		return;
	}
	q->front=q->rear=0;
	return;
}

void EnQueue(CyQueue *q,int value)
{
	if((q->rear+1)%Maxsize==q->front)
	{
		printf("Cyclic Queue is Full!\n");
		return;
	}
	q->base[q->rear]=value;
	q->rear=(q->rear+1)%Maxsize;
	return;
}

void DeQueue(CyQueue *q,int *value)
{
	if(q->front==q->rear)
	{
		printf("Cyclic Queue is Empty!\n");
		return;
	}
	*value=q->base[q->front];
	q->front=(q->front+1)%Maxsize;
	return;
}

int QueueEmpty(CyQueue *q)
{
    if (q->front==q->rear)//队列为空返回1，不为空返回0
	{
        return 1;
    }
    return 0;
}

/*广度优先遍历BFS*/
int visited[MAX_VERTICES];//定义"标志"数组为全局变量

void BFS(AdMatrix *G,int i)
{
	int j;
	CyQueue q;
	create(&q);
   //1.设置起始点
	printf("%d ",G->Vertices[i]);//1.输出当前结点
	visited[i]=1;//2.将已访问的结点标志成1
	EnQueue(&q,i);//3.将第一个结点入队

    //2.由起始点开始，对后续结点进行操作
	while(!QueueEmpty(&q))
	{

		DeQueue(&q,&i);

		for(j=0;jnumV;j++)
		{
			if(G->AdjacencyMatrix[i][j]==1&&visited[j]==0)
			{
				printf("%d ",G->Vertices[j]);//输出符合条件的顶点
	            visited[j]=1;//设置成已访问状态1
	            EnQueue(&q,j);//入队
			}
		}
	}
}

/*void BFSTraverse(AdMatrix *G)
{
	int i;

	//数组初始化为全0
	for(i=0;inumV;i++)
	{
		visited[i]=0;
	}

	for(i=0;inumV;i++)
	{
		if(visited[i]==0)
		{
			BFS(G,i);
		}
	}
}
*/
int main()
{
	AdMatrix G;
	CreateGraph(&G);
	ShowGraph(&G);
	printf("输入BFS遍历的起始结点：");
	int n;
	scanf("%d",&n);
	BFS(&G,n-1);
	return 0;
}

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180