图的邻接矩阵存储 C语言实现BFS

图的邻接矩阵存储，以及在此基础上实现的广度优先遍历（BFS）
/图的邻接矩阵+广度优先遍历/
#include<stdio.h>
#include<stdlib.h>

#define INFINITE 65535
#define MaxSize 100

typedef char VertexType;
typedef int EdgeType;
typedef int ElemType;

typedef struct{
ElemType data[MaxSize];
int front, rear;
}SqQueue;

typedef struct Graph{
VertexType vexs[MaxSize]; //顶点表
EdgeType arc[MaxSize][MaxSize]; //邻接矩阵
int vexNum, arcNum;
}Graph;

void InitQueue(SqQueue *Q); //初始化循环队列
int IsEmpty(SqQueue Q); //判队空
int EnQueue(SqQueue *Q, ElemType e); //入队
int DeQueue(SqQueue *Q, ElemType *e); //出队

/-----------------------------------------------------------------------------/

int visited[MaxSize];
SqQueue Q;

void CreateGraph(Graph *G); //创建图
void OutputGraph(Graph G); //输出图中所有顶点
int GetVexIndex(Graph G,VertexType vex); //根据顶点信息得出其对应的顶点序号
int FirstNeighbor(Graph G,int v); //输入一个顶点信息，输出与其相连的一个点的序号,若无则返回-1
int NextNeighbor(Graph G, int v, int w); //检测v除w以外的邻接点
void Visit(Graph G,int v); //访问顶点号为v的顶点
void BFS(Graph G,int v);
void BFSTraverse(Graph G);

void main(){
Graph G;
CreateGraph(&G);
OutputGraph(G);
BFSTraverse(G);
}

void Visit(Graph G, int v){
printf("%c ", G.vexs[v]);
}

void BFS(Graph G, int v){
Visit(G,v);
visited[v] = 1;
EnQueue(&Q, v);

while (!IsEmpty(Q)){
	DeQueue(&Q, &v);
	for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){
		if (!visited[w]){
			Visit(G, w);
			visited[w] = 1;
			EnQueue(&Q, w);
		}
	}
}
1
2
3
4
5
6
7
8
9
10

}

void BFSTraverse(Graph G){
printf(“\n广度优先遍历xulie：\n”);
int i;
for (i = 0; i < G.vexNum; i++)
visited[i] = 0;
InitQueue(&Q);
for (i = 0; i < G.vexNum; i++){
if (!visited[i])
BFS(G, i);
}
}

int FirstNeighbor(Graph G, int v){
int i;
for (i = 0; i < G.vexNum; i++){
if (G.arc[v][i] == 1){
return i;
}
}

return -1;
1

}

int NextNeighbor(Graph G, int v, int w){
int i;
for (i = w+1; i < G.vexNum; i++){
if (G.arc[v][i] == 1)
return i;
}

return -1;
1

}

void CreateGraph(Graph *G){
int i, j;
VertexType vs, ve;
printf(“请输入顶点数,边数：”);
scanf(“%d %d”, &G->vexNum, &G->arcNum);
for (i = 0; i < G->vexNum; i++){ //图的初始化
for (j = 0; j < G->vexNum; j++){
if (i == j)
G->arc[i][j] = 0;
else
G->arc[i][j] = INFINITE;
}
}
fflush(stdin);
for (i = 0; i < G->vexNum; i++){
printf(“请输入顶点%d:”, i+1);
scanf(“%c”, &G->vexs[i]);
getchar();
}
for (i = 0; i < G->arcNum; i++){
printf(“请输入起点，终点:”);
scanf(“%c %c”, &vs, &ve);
getchar();
int vs_index=0, ve_index=0;
for (j = 0; j < G->vexNum; j++){ //找到起始点、终点下标
if (vs == G->vexs[j])
vs_index = j;
if (ve == G->vexs[j])
ve_index = j;
}
G->arc[vs_index][ve_index] = 1; //无向图，上下三角都要保存
G->arc[ve_index][vs_index] = 1;
}
}

void OutputGraph(Graph G){
int i, j;
printf(“图中顶点：\n”);
for (i = 0; i < G.vexNum; i++){
printf(“%c “, G.vexs[i]);
}
printf(”\n图中的弧：\n”);
for (i = 0; i < G.vexNum; i++){
for (j = 0; j < G.vexNum; j++){
if (G.arc[i][j] == 1){
printf(“%c------>%c\n”, G.vexs[i], G.vexs[j]);
}
}
}

}

int GetVexIndex(Graph G, VertexType vex){
int i;
for (i = 0; i < G.vexNum; i++){
if (G.vexs[i] == vex)
return i;
}

return -1;
1

}

/队列基本操作实现/

void InitQueue(SqQueue *Q){
Q->rear = Q->front = 0;
}

int IsEmpty(SqQueue Q){
if (Q.rear == Q.front)
return 1;
else
return 0;
}

int EnQueue(SqQueue *Q, ElemType e){
if ((Q->rear + 1) % MaxSize == Q->front) //队满
return 0;
Q->data[Q->rear] = e;
Q->rear = (Q->rear + 1) % MaxSize;
return 1;
}

int DeQueue(SqQueue *Q, ElemType *e){
if (Q->front == Q->rear) //队空
return 0;
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % MaxSize;
return 1;
}
运行结果，如图：