论坛 › 数据结构与算法 › BFS_DFS_Adjacency Matrix

pwnmelife 发表于 2019-1-13 19:14:07

BFS_DFS_Adjacency Matrix

本帖最后由 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;
      EdgeType Edge;
      int vexnum, arnum;
}MGraph;

bool visited = {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 = isExist;
                }
      }
}

void DFS(MGraph *m, int start) {
      visit(start);
      visited = true;
      for (int i = 0; i < number; i++) {
                if (!visited && m->Edge) {
                        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) {
                        visit(i);
                        visited = true;
                        InsertQueue(q, i);
                        while (!IsEmpty(q)) {
                              DeleteQueue(q, &vertex);
                              for (int j = 0; j < number;j++) {
                                        if (!visited && m->Edge) {
                                                visit(j);
                                                visited = 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;
      }
}

查看完整版本: BFS_DFS_Adjacency Matrix