BFS_DFS_Adjacency Matrix

pwnmelife

// 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;
        }
}