|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 pwnmelife 于 2019-1-13 20:00 编辑
- // BFS_DFS.cpp : This file contains the 'main' function. Program execution begins and ends there.
- //
- #include <iostream>
- #include <stdio.h>
- #include <stdlib.h>
- #define MaxVertexNum 100
- typedef char VertexType;
- typedef int ElemType;
- typedef int EdgeType;
- typedef struct QNode{
- ElemType data;
- struct QNode* next;
- }QNode, *QNodePtr;
- typedef struct {
- QNode *front, *rear;
- }Queue, *QueuePtr;
- typedef struct {
- VertexType Vex[MaxVertexNum];
- EdgeType Edge[MaxVertexNum][MaxVertexNum];
- int vexnum, arnum;
- }MGraph;
- bool visited[MaxVertexNum] = {false};
- int number;
- void InitQueue(QueuePtr *q); //初始化
- void InsertQueue(QueuePtr *q, ElemType c); //入队
- void DeleteQueue(QueuePtr *q, ElemType *c);//出队
- bool IsEmpty(QueuePtr *q); //判空
- void InitGraph(MGraph* m, int number);
- void DFS(MGraph* m, int start);
- void BFS(MGraph* m);
- void visit(int);
- int main()
- {
- int start;
- MGraph m;
- printf("Please the vertex number: ");
- scanf("%d", &number);
- InitGraph(&m, number);
- printf("Please input a starting vertex:");
- scanf("%d", &start);
- //DFS(&m, start);
- BFS(&m);
- printf("\n");
- return 0;
- }
- void InitGraph(MGraph *m, int number) {
- printf("please input the whole graph, 1(yes), 0(no)\n");
- int isExist;
- for (int i = 0; i < number; i++) {
- for (int j = 0; j < number; j++) {
- scanf("%d", &isExist);
- m->Edge[i][j] = isExist;
- }
- }
- }
- void DFS(MGraph *m, int start) {
- visit(start);
- visited[start] = true;
- for (int i = 0; i < number; i++) {
- if (!visited[i] && m->Edge[start][i]) {
- DFS(m, i);
- }
- }
- }
- void BFS(MGraph* m) {
- int vertex;
- QueuePtr *q = (QueuePtr *)malloc(sizeof(QueuePtr));
- InitQueue(q);
- for (int i = 0; i < number; i++) {
- if (!visited[i]) {
- visit(i);
- visited[i] = true;
- InsertQueue(q, i);
- while (!IsEmpty(q)) {
- DeleteQueue(q, &vertex);
- for (int j = 0; j < number;j++) {
- if (!visited[j] && m->Edge[vertex][j]) {
- visit(j);
- visited[j] = true;
- InsertQueue(q, j);
- }
- }
- }
- }
- }
- }
- void visit(int vertex) {
- printf("%d ", vertex);
- }
- void InitQueue(QueuePtr *q) {
- (*q) = (QueuePtr)malloc(sizeof(Queue));
- (*q)->front = (*q)->rear = (QNodePtr)malloc(sizeof(QNode)); //头结点
- (*q)->front->next = NULL;
- }
- void InsertQueue(QueuePtr *q, ElemType c) {
- QNodePtr qNode = (QNodePtr)malloc(sizeof(QNode));
- qNode->data = c;
- qNode->next = NULL;
- (*q)->rear->next = qNode;
- (*q)->rear = qNode;
- }
- void DeleteQueue(QueuePtr *q, ElemType *c) {
- if ((*q)->front == (*q)->rear) {
- printf("The Queue is empty\n");
- return;
- }
- QNodePtr headNode = (*q)->front;
- QNodePtr firstNode = headNode->next;
- *c = firstNode->data;
- headNode->next = firstNode->next;
- if ((*q)->rear == firstNode) {
- (*q)->rear = (*q)->front;
- }
- free(firstNode);
- }
- bool IsEmpty(QueuePtr *q) {
- if ((*q)->front == (*q)->rear) {
- return true;
- } else {
- return false;
- }
- }
复制代码
|
|