BFS&DFS

简单总结一下BFS与DFS在图中的实现

• BFS&DFS in C++

  由于对class不熟，没有写成类，但是单独写了头文件，作为一个标准例子吧

  这是头文件

  /*****************************************************************//**
   * \file   BFS.hpp
   * \brief  For Ms.Winter 
   *  To demonstrate the BFS and DFS in graph 
   * as well as wellas review the queue and graph
   * \author Winter
   * \date   March 2023
   *********************************************************************/
  
  #pragma once		/* Two lines just in case */
  #ifndef _BFS_H_
  #define _BFS_H_
  
  #define _CRT_SECURE_NO_WARNINGS
  #include<iostream>	
  #include<string>
  #include<cstdlib>
  using namespace std;
  // Macro 
  #define OK	1
  #define BAD	0
  #define OVERFLOW	-1
  #define INFEASIBLE	-2
  #define MVNum	50	// Maximum number of vertices
  #define MAXSIZE	100
  //ADT
  using Status = int;
  using Len = int;		//C++ version
  // ALGraph
  typedef char VertexType;
  typedef int ArcType;
  typedef int OtherInfo;	//Maybe the weight
  
  typedef struct anode {
  	int adjvex;		//the index of this node
  	OtherInfo info;
  	struct anode* next;
  }Arcnode;
  typedef struct vnode {
  	VertexType data;
  	struct Arcnode* firstarc;
  	// struct Arcnode*antifirst;	the out degree
  }Vnode;
  
  typedef Vnode AdjList[MVNum];	
  typedef struct {
  	AdjList vertices;
  	int vernum{ 0 };
  	int arcnum{ 0 };
  }ALGraph;
  
  //AMGraph
  typedef struct {
  	VertexType vertices[MVNum];
  	ArcType arcs[MVNum][MVNum];
  	int vernum{ 0 };
  	int arcnum{ 0 };
  }AMGraph;
  
  // Queue the Squeue and list queue
  typedef int ElemType;
  typedef struct {
  	ElemType* data;
  	int front;
  	int rear;
  }SQueue;
  typedef struct qnode {
  	ElemType data;
  	struct qnode* next;
  }Qnode;
  typedef struct {
  	Qnode* front;
  	Qnode* rear;
  }Queue;
  //
  // the external value we will use in the main.cpp
  Arcnode* static_ = nullptr;
  bool visited[MVNum];		//BFS
  bool Visited[MAXSIZE];		//DFS
  //static funcion 
  inline int	FirstAdjVex(const ALGraph G, int v)
  {
  	if (!static_)
  		static_ = G.vertices[v].firstarc;
  	return G.vertices[v].firstarc->adjvex;
  }
  inline int NextAdjVex(const ALGraph G, int v, int w)
  {
  	if (!static_)
  		return -1;
  	static_ = static_->next;
  	if (static_)
  		return static_->adjvex;
  	else
  		return -1;
  }
  // Func
  Status InitQueue_S(SQueue& Q);
  Status QueueIsEmpty_S(const SQueue& Q);
  Status DestroyQueue_S(SQueue& Q);
  Status EnQueue_S(SQueue& Q, ElemType add);
  Status DeQueue_S(SQueue& Q, ElemType& del);
  
  Status InitQueue(Queue& Q);
  Status QueueIsEmpty(const Queue& Q);
  Status DestroyQueue(Queue& Q);
  Status EnQueue(Queue& Q, ElemType add);
  Status DeQueue(Queue& Q, ElemType&del);
  
  void BFS(const ALGraph& G, int v);	
  void DFS(const AMGraph& G, int v);
  
  #endif

  这是cpp文件

  /*****************************************************************//**
   * \file   BFS.cpp
   * \brief  For Ms.Winter
   *  21/3/2023
   * \author 86158
   * \date   March 2023
   *********************************************************************/
  // ?Here we come the BFS
  
  #include"BFS.hpp"
  //
  Status InitQueue_S(SQueue& Q)
  {
  	Q.data = (ElemType*)malloc(sizeof(ElemType) * MVNum);
  	if (!Q.data)
  		exit(EXIT_FAILURE);
  	return OK;
  }
  
  Status DestroyQueue_S(SQueue& Q)
  {
  	free(Q.data);
  	return OK;
  }
  
  Status QueueIsEmpty_S(const SQueue& Q)
  {
  	return Q.front == Q.rear;
  }
  
  Status EnQueue_S(SQueue&Q,ElemType add)
  {
  	if ((Q.rear + 1) % MVNum == Q.front)
  		return BAD;
  	Q.data[Q.rear] = add;
  	Q.rear = (Q.rear + 1) % MVNum;
  	return OK;
  }
  
  Status DeQueue_S(SQueue& Q, int& del)
  {
  	if (Q.front == Q.rear)
  		return BAD;
  
  }
  
  Status InitQueue(Queue& Q)
  {
  	Qnode*pnew = (Qnode*)malloc(sizeof(Qnode));
  	if (!pnew)
  		exit(EXIT_FAILURE);
  	Q.front = Q.rear = pnew;
  	Q.front->next = nullptr;
  }
  
  Status QueueIsEmpty(const Queue& Q)
  {
  	return Q.front == Q.rear;
  }
  
  Status DestroyQueue(Queue& Q)
  {
  	Q.rear = Q.front;
  	while (Q.front)
  	{
  		Q.rear = Q.front->next;
  		free(Q.front);
  		Q.front = Q.rear;
  	}
  	return OK;
  }
  
  Status EnQueue(Queue& Q, ElemType add)
  {
  	Qnode* pnew = (Qnode*)malloc(sizeof(Qnode));
  	pnew->data = add;
  	pnew->next = nullptr;
  	Q.rear->next = pnew;
  	Q.rear = pnew;
  	return OK;
  }
  
  Status DeQueue(Queue& Q, ElemType& del)
  {
  	if (Q.front == Q.rear)
  		return BAD;
  	Qnode* psave = Q.front->next;
  	del = psave->data;
  	Q.front->next = psave->next;
  	if (Q.rear == psave)
  		Q.rear = Q.front;
  	free(psave);
  	return OK;
  }
  //
  void BFS(const ALGraph& G, int v)	//? v the start of the BFS
  {
  	Queue vessel;
  	InitQueue(vessel);
  	cout << G.vertices[v].data;
  	visited[v] = true;
  	EnQueue(vessel, v);
  	int u{ 0 };
  	while (!QueueIsEmpty(vessel))
  	{
  		DeQueue(vessel, u);
  		for (int w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
  		{
  			if (!visited[w])
  			{
  				visited[w] = true;
  				cout << G.vertices[w].data;
  				EnQueue(vessel, w);
  			}
  		}
  	}
  }
  
  void DFS(const AMGraph& G, int v)
  {
  	if (v < 0 || v >= G.vernum)
  		exit(EXIT_FAILURE);
  	cout << G.vertices[v];
  	Visited[v] = true;
  	for (int w = 0; w < G.vernum; ++w)
  		if (G.arcs[v][w] && !Visited[w])
  			DFS(G, w);
  }
  //inline int FirstAdjvex(const ALGraph& G, int v)
  //{
  //	if (!static_)
  //		static_ = G.vertices[v].firstarc;
  //	return G.vertices[v].firstarc->adjvex;
  //}
  //
  //inline int NextAdjvex(const ALGraph& G, int v, int u)
  //{
  //	ArcNode* scan;
  //	for (scan = G.vertices[v].firstarc; scan->adjvex != u && !scan->next; scan = scan->next)
  //		continue;
  //	if (u == scan->adjvex && !scan->next)
  //		return scan->next->adjvex;
  //	return -1;
  //}
  //// ?May I create the new writing
  //inline int NextNeighbor(const ALGraph& G,int v)
  //{
  //	if (!static_||!static_->next)
  //		return -1;
  //	static_=static_->next;
  //	return static_->adjvex;
  //}
  
  //Macro
  //#define MVNum	50
  //#define OK	1
  //#define BAD	0
  ////
  //using Status = int;
  //using VertexType = char;
  //using ArcType = int;
  //using Len = int;
  //// the adjency list
  //typedef struct anode{
  //	int adjvex;
  //	ArcType info;
  //	struct anode* next;
  //}ArcNode;
  //
  //typedef struct vnode {
  //	VertexType data{ 0 };
  //	ArcNode* firstarc;	//?there we don't care the out degree
  //}Vnode;
  //
  //typedef Vnode AdjList[MVNum];	// ? Very special !!!
  //typedef struct {
  //	AdjList vertices;
  //	int vertexnum{ 0 };
  //	int arcnum{ 0 };
  //}ALGraph;
  //
  ////? we just can handle the adjlist like list and insert 
  //// ? from the head of the list!!!
  ////we will use the queue
  //typedef int ElemType;		// just to store the index of the vex
  //typedef struct {
  //	ElemType* data;
  //	int front{ 0 };
  //	int rear{ 0 };
  //}SQueue;
  //// the loop queue

• BFS in Python

然后写了一个在python中BFS实现 主要用python可以省略一些细节而着重于思想理解

#BFS in python
from collections import deque   # double queue
graph={}
graph["you"] = ["alice", "bob", "claire"] 
graph["bob"] = ["anuj", "peggy"] 
graph["alice"] = ["peggy"] 
graph["claire"] = ["thom", "jonny"] 
graph["anuj"] = [] 
graph["peggy"] = [] 
graph["thom"] = [] 
graph["jonny"] = []

#function
def person_is_seller(name):
    return name[-1]=='m'        #just give an example

def search(graph,name):       #we start from this guy
    search_queue=deque()
    search_queue+=graph[name]
    searched=[]
    while search_queue:     #not null
        person=search_queue.popleft()
        if person not in searched:
            if person_is_seller(person):
                print(person+' is a wolfman')
                return True
            else:
                search_queue+=graph[person]
                search.append(person)
    return False

• 总结思路

BFS主要应用了队列的思想 DFS主要运用了递归的思想 最终图的表示使用了离散数学的邻接矩阵于邻接表 Done!