C语言创建图、广度深度优先遍历、输出邻接矩阵...

ゝ一纸荒年。 2023-03-14 10:49 5阅读 0赞

## 源代码 ##

#include <stdio.h>
    // Adjacency Matrix 邻接矩阵
    // 定义顶点最多个数
    #define VERTEX_MAX 100
    // 定义队列最大长度
    #define QUEUE_MAXSIZE 100
    // 定义最大值，表示两顶点之间不可达
    #define MAXVALUE 32767
    // 定义图
    typedef struct { 
    	// 保存所有顶点
    	char vertexs[VERTEX_MAX];
    	// 邻接矩阵
    	int edges[VERTEX_MAX][VERTEX_MAX];
    	// 用于判断顶点是否被访问过
    	int isVisited[VERTEX_MAX];
    	int vertexNum;	// 点数
    	int edgeNum;	// 边数
    
    }MatrixGraph;
    
    // 定义队列 
    typedef struct { 
    	int data[QUEUE_MAXSIZE];
    	int head;	// 队头
    	int tail;	// 队尾
    }Queue;
    
    void queueInit(Queue *q) { 
    	q->head = q->tail = 0;
    }
    int queueIsEmpty(Queue *q) { 
    	return q->head == q->tail;
    }
    void queueIn(Queue *q, int ch) { 
    	// 判断队列是否已满
    	if ((q->tail + 1) % QUEUE_MAXSIZE == q->head) { 
    		printf("\n队列已满!\n");
    		return;
    	}
    	q->data[q->tail] = ch;
    	q->tail = (q->tail + 1) % QUEUE_MAXSIZE;
    }
    int queueOut(Queue *q) { 
    	if (queueIsEmpty(q)) { 
    		return -1;
    	}
    	int ch = q->data[q->head];
    	q->head = (q->head + 1) % QUEUE_MAXSIZE;
    	return ch;
    }
    
    // 返回顶点在数组中的下标
    int locateVertex(MatrixGraph *G, char vertex) { 
    	for (int i = 0; i < G->vertexNum; i++) { 
    		if (vertex == G->vertexs[i]) { 
    			return i;
    		}
    	}
    	// 如果没有找到返回-1
    	return -1;
    }
    
    // 创建图
    void createGraph(MatrixGraph *G) { 
    	int i, j, k, weight;
    	// 边的两个顶点
    	char start, end;
    
    	printf("\n输入各顶点信息\n");
    	for (i = 0; i < G->vertexNum; i++) { 
    		// 吸收多余的回车
    		getchar();
    		printf("第%d个顶点：", i + 1);
    		scanf("%c", &(G->vertexs[i]));
    	}
    
    	printf("\n输入构成各边的两个顶点及其权值（用逗号分隔）：\n");
    	for (k = 0; k < G->edgeNum; k++) { 
    		// 吸收多余的回车
    		getchar();
    		printf("第%d条边：", k + 1);
    		scanf("%c,%c,%d", &start, &end, &weight);
    		// 获取两个顶点在数组中的下标
    		i = locateVertex(G, start);
    		j = locateVertex(G, end);
    		// 如果两个顶点都存在
    		if (i != -1 && j != -1) { 
    			G->edges[i][j] = weight;
    			G->edges[j][i] = weight;
    		}
    		else
    		{ 
    			printf("输入的顶点有误,创建图失败！\n");
    			return;
    		}
    	}
    }
    
    // 输出图的邻接矩阵
    void printMatrix(MatrixGraph *G) { 
    	int i, j;
    	for (j = 0; j < G->vertexNum; j++) { 
    		printf("\t%c", G->vertexs[j]);
    	}
    	printf("\n");
    	for (i = 0; i < G->vertexNum; i++) { 
    		printf("%c", G->vertexs[i]);
    		for (j = 0; j < G->vertexNum; j++) { 
    			if (G->edges[i][j] == MAXVALUE) { 
    				printf("\t∞");
    			}
    			else { 
    				printf("\t%d", G->edges[i][j]);
    			}
    		}
    		printf("\n");
    	}
    }
    
    // 从第i个顶点开始遍历
    void dfs(MatrixGraph *G, int i) { 
    	int j;
    	// 把该顶点设置为已被访问
    	G->isVisited[i] = 1;
    	// 输出该顶点
    	printf("%c->", G->vertexs[i]);
    	for (j = 0; j < G->vertexNum; j++) { 
    		// 查找该顶点的第一个未被访问的邻接顶点
    		if (G->edges[i][j] != MAXVALUE && !G->isVisited[j]) { 
    			dfs(G, j);
    		}
    	}
    }
    
    // 深度优先遍历
    void DFSTraverse(MatrixGraph *G) { 
    	int i;
    	// 初始化是否访问标志数组
    	for (i = 0; i < G->vertexNum; i++) { 
    		G->isVisited[i] = 0;
    	}
    	printf("\n深度优先遍历：\n");
    	for (i = 0; i < G->vertexNum; i++) { 
    		// 如果该顶点没有被访问过
    		if (!G->isVisited[i]) { 
    			dfs(G, i);
    		}
    	}
    	printf("\n");
    }
    
    // 广度优先遍历
    void bfs(MatrixGraph *G, int k) { 
    	int i, j;
    	Queue q;
    	// 初始化队列 
    	queueInit(&q);
    	G->isVisited[k] = 1;	// 将该顶点设置为已访问
    	printf("%c->", G->vertexs[k]);	// 输出该顶点
    
    	// 将该顶点入队
    	queueIn(&q, k);
    	while (!queueIsEmpty(&q)) { 
    		i = queueOut(&q);
    		// 遍历该顶点的所有邻接顶点
    		for (j = 0; j < G->vertexNum; j++) { 
    			// 如果该邻接顶点未被访问
    			if (G->edges[i][j] != MAXVALUE && !G->isVisited[j]) { 
    				printf("%c->", G->vertexs[j]);
    				G->isVisited[j] = 1;
    				queueIn(&q, j);
    			}
    		}
    	}
    }
    
    void BFSTraverse(MatrixGraph *G) { 
    	int i;
    	for (i = 0; i < G->vertexNum; i++) { 
    		G->isVisited[i] = 0;
    	}
    	printf("\n广度优先遍历:\n");
    	for (i = 0; i < G->vertexNum; i++) { 
    		if (!G->isVisited[i]) { 
    			bfs(G, i);
    		}
    	}
    	printf("\n");
    }
    
    int main() { 
    	int i, j;
    	MatrixGraph G;
    
    	printf("\n请输入图的顶点数量和边的数量：");
    	scanf("%d%d", &G.vertexNum, &G.edgeNum);
    	// 初始化邻接矩阵
    	for (i = 0; i < G.vertexNum; i++) { 
    		for (j = 0; j < G.edgeNum; j++) { 
    			G.edges[i][j] = MAXVALUE;
    		}
    	}
    	createGraph(&G);
    
    	printf("\n邻接矩阵如下：\n");
    	printMatrix(&G);
    
    	DFSTraverse(&G);
    	BFSTraverse(&G);
    
    	printf("\n\n");
    	return 0;
    }