BFS&DFS

BFS&DFS

Winter Lv4
  2023-03-23 16:01:45 2023-03-23 16:01 Created   2023-03-23 16:53:24 2023-03-23 16:53 Updated    1.3k Words  7 Mins  

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

  • BFS&DFS in C++

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

    这是头文件

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    /*****************************************************************//**
     * \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文件

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    /*****************************************************************//**
     * \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可以省略一些细节而着重于思想理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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!

  • Post title：BFS&DFS
  • Post author：Winter
  • Create time：2023-03-23 16:01:45
  • Post link：https://spikeihg.github.io/2023/03/23/BFS-DFS/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
On this page
BFS&DFS
  1. 简单总结一下BFS与DFS在图中的实现
    1. BFS&DFS in C++
      1. 这是头文件
      2. 这是cpp文件
    2. BFS in Python
  2. 总结思路