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

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

#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);
		}
	}
}

}

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;

}

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;

}

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;

}

/队列基本操作实现/

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; } 运行结果，如图：