深度优先搜索

深度优先搜索（Depth First Search，DFS），是最常见的图搜索方法之一。深度优先搜索沿着一条路径一直走下去，无法行进时，回退回退到刚刚访问的结点，似不撞南墙不回头，不到黄河不死心。深度优先遍历是按照深度优先搜索的方式对图进行遍历。

后被访问的顶点，其邻接点先被访问。

根据深度优先遍历秘籍，后来先服务，可以借助于栈实现。递归本身就是使用栈实现的，因此使用递归方法更方便。

算法步骤：

  1. 初始化图中所有顶点未被访问。
  2. 从图中的某个顶点v出发，访问v并标记已访问；
  3. 依次检查v的所有邻接点w，如果w未被访问，则从w出发进行深度优先遍历（递归调用，重复2—3步）。

基于邻接矩阵的DFS算法

查找每个顶点的邻接点需要$O(n)$时间，一共n个顶点，总的时间复杂度为$O(n^2)$，使用了一个递归工作栈，空间复杂度为$O(n)$。

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
// DFS遍历邻接矩阵
#include <stdio.h>
#include <stdlib.h>

// 无向图

// 最大顶点
#define MAXVNUM 100

// 顶点类型
typedef char VexType;
// 边上权值数据类型
typedef int EdgeType;
// 访问标志
int visited[MAXVNUM] = {0};

typedef struct AMGraph {
  VexType Vex[MAXVNUM];
  EdgeType Edge[MAXVNUM][MAXVNUM];
  // 顶点数 边数
  int vexnum, edgenum;
} AMGraph;

AMGraph* createAMGraph() {
  AMGraph *G = (AMGraph*) malloc(sizeof(AMGraph));
  // 顶点数
  G->vexnum = 3;
  // 边数
  G->edgenum = 3;
  // 存入顶点信息
  G->Vex[0] = 'A';
  G->Vex[1] = 'B';
  G->Vex[2] = 'C';
  // 初始化邻接矩阵
  for(int i = 0; i < G->vexnum; i ++) {
    for(int j = 0; j < G->vexnum; j ++) {
      G->Edge[i][j] = 0;
    }
  }
  // 边
  G->Edge[0][1] = G->Edge[1][0] = 1;
  G->Edge[1][2] = G->Edge[2][1] = 1;
  G->Edge[0][2] = G->Edge[2][0] = 1;


  return G;
}

int locatevex(AMGraph* G, VexType x) {
  for(int i = 0; i < G->vexnum; i ++) {
    if(x == G->Vex[i]) return i;
  }
  return -1;
}

void printAMGraph(AMGraph* G) {
  printf("邻接矩阵为：\n");
  /* printf("%d\t", G->vexnum); */
  for(int i = 0; i < G->vexnum; i ++) {
    for(int j = 0; j < G->vexnum; j ++) {
      printf("%d\t", G->Edge[i][j]);
    }
    printf("\n");
  }
}

// 深度优先遍历
void dfsAM(AMGraph* G, int v) {
  printf("%c\t", G->Vex[v]);
  visited[v] = 1;
  for (int i = 0; i < G->vexnum; i ++) {
    if(G->Edge[v][i] && !visited[i]) dfsAM(G, i);
  }
}

void clearVisited() {
  for (int i = 0; i < MAXVNUM; i ++) {
    visited[i] = 0;
  }
}

int main(int argc, char *argv[])
{
  AMGraph *G = createAMGraph();
  printAMGraph(G);
  dfsAM(G, 0);
  printf("\n");
  clearVisited();
  dfsAM(G, 1);
  printf("\n");
  clearVisited();
  dfsAM(G, 2);
  printf("\n");
  clearVisited();
  return 0;
}

基于邻接表的DFS算法

查找顶点$v_i$的邻接点需要$O(d(v_i)$时间，$d(v_i)$为$v_i$的出度（无向图为度），对有向图而言，所有顶点的出度之和等于边数e，对无向图而言，所有顶点的度之和等于2e，因此查找邻接点的时间复杂度为$O(e)$，加上初始化时间$O(n)$，总的时间复杂度为$O(n+e)$，使用了一个递归工作栈，空间复杂度为$O(n)$。

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
// DFS有向邻接表
#include <stdio.h>
#include <stdlib.h>

// 有向图邻接表

// 顶点最大值
#define MAXVNUM 100

// 访问标志
int visited[MAXVNUM] = {0};

// 顶点数据类型
typedef char VexType;
typedef struct AdjNode {
  // 邻接点下标
  int v;
  // 下一个邻接点
  struct AdjNode *next;
} AdjNode;

typedef struct VexNode {
  // 顶点
  VexType data;
  // 指向第一个邻接点
  AdjNode *first;
} VexNode;

typedef struct ALGraph {
  VexNode *Vex;
  int vexnum, edgenum;
} ALGraph;

// 查找顶点的下标
int locatevex(ALGraph* G, VexType x) {
  for(int i = 0; i < G->vexnum; i ++) {
    if(x == G->Vex[i].data) return i;
  }
  return -1;
}

// 插入一条边
void insertEdge(ALGraph* G, int i, int j) {
  AdjNode *s = (AdjNode*) malloc(sizeof(AdjNode));
  s->v = j;
  s->next = G->Vex[i].first;
  G->Vex[i].first = s;
}

ALGraph* createALGraph() {
  ALGraph *G = (ALGraph*) malloc(sizeof(ALGraph));
  // 顶点和边
  G->vexnum = 3;
  G->edgenum = 3;
  G->Vex = (VexNode*) malloc(G->vexnum * sizeof(VexNode));
  G->Vex[0].data = 'A';
  G->Vex[1].data = 'B';
  G->Vex[2].data = 'C';
  G->Vex[0].first = NULL;
  G->Vex[1].first = NULL;
  G->Vex[2].first = NULL;
  insertEdge(G, locatevex(G, 'A'), locatevex(G, 'B'));
  insertEdge(G, locatevex(G, 'B'), locatevex(G, 'C'));
  insertEdge(G, locatevex(G, 'C'), locatevex(G, 'A'));

  return G;
}

void printALGraph(ALGraph* G) {
  printf("邻接矩阵为：\n");
  /* printf("%d\t", G->vexnum); */
  for(int i = 0; i < G->vexnum; i ++) {
    AdjNode *t = G->Vex[i].first;
    printf("%c: ", G->Vex[i].data);
    while(t != NULL) {
      printf(" [%d] ", t->v);
      t = t->next;
    }
    printf("\n");
  }
}

void dfsAL(ALGraph* G, int v) {
  AdjNode *p;
  printf("%c\t", G->Vex[v].data);
  visited[v] = 1;
  p = G->Vex[v].first;
  while(p) {
    if(!visited[p->v]) {
      dfsAL(G, p->v);
    }
    p = p->next;
  }
}

void clearVisited() {
  for (int i = 0; i < MAXVNUM; i ++) {
    visited[i] = 0;
  }
}

int main(int argc, char *argv[])
{
  ALGraph *G = createALGraph();
  printALGraph(G);
  dfsAL(G, 0);
  printf("\n");
  clearVisited();
  dfsAL(G, 1);
  printf("\n");
  clearVisited();
  dfsAL(G, 2);
  printf("\n");
  clearVisited();
  return 0;
}

广度优先搜索

广度优先搜索（Breadth First Search，BFS），又称为宽度优先搜索，是最常见的图搜索方法之一。广度优先搜索是从某个顶点（源点）出发，一次性访问所有未被访问的邻接点，再依次从这些访问过邻接点出发，…，似水中涟漪，似声音传播，一层层地传播开来。广度优先遍历是按照广度优先搜索的方式对图进行遍历。

image-20200825153327439

先被访问的顶点，其邻接点先被访问。

根据广度优先遍历秘籍，先来先服务，可以借助于队列实现。每个结点访问一次且只访问一次，因此可以设置一个辅助数组。

步骤：

  1. 初始化图中所有顶点未被访问，初始化一个空队列。
  2. 从图中的某个顶点v出发，访问v并标记已访问，将v入队；
  3. 如果队列非空，则继续执行，否则算法结束；
  4. 队头元素v出队，依次访问v的所有未被访问邻接点，标记已访问并入队。转向步骤3；

基于邻接矩阵的BFS算法

查找每个顶点的邻接点需要$O(n)$时间，一共n个顶点，总的时间复杂度为$O(n^2)$，使用了一个辅助队列，最坏的情况下每个顶点入队一次，空间复杂度为$O(n)$。

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
// BFS遍历邻接矩阵
#include <stdio.h>
#include <stdlib.h>

// 无向图

// 最大顶点
#define MAXVNUM 100

// 顶点类型
typedef char VexType;
// 边上权值数据类型
typedef int EdgeType;
// 访问标志
int visited[MAXVNUM] = {0};

typedef struct AMGraph {
  VexType Vex[MAXVNUM];
  EdgeType Edge[MAXVNUM][MAXVNUM];
  // 顶点数 边数
  int vexnum, edgenum;
} AMGraph;

// 实现队列
typedef struct Queue {
  int val;
  struct Queue *next;
} *Queue;

// 最顶部不保存数据
Queue initialQueue() {
  Queue q = (Queue) malloc(sizeof(Queue));
  if(!q) return NULL;
  q->next = NULL;
  return q;
}

int isEmpty(Queue q) {
  return q->next == NULL;
}

void enQueue(Queue q, int val) {
  Queue p = q;
  while(p->next) {
    p = p->next;
  }
  Queue elem = (Queue) malloc(sizeof(Queue));
  elem->val = val;
  p->next = elem;
}

void deQueue(Queue q) {
  if(!isEmpty(q)) {
    Queue temp = q->next;
    q->next = temp->next;
    free(temp);
  }
}

int getHead(Queue q) {
  if(isEmpty(q)) {
    printf("queue is empty.\n");
    return -1;
  }
  return q->next->val;
}

AMGraph* createAMGraph() {
  AMGraph *G = (AMGraph*) malloc(sizeof(AMGraph));
  // 顶点数
  G->vexnum = 3;
  // 边数
  G->edgenum = 3;
  // 存入顶点信息
  G->Vex[0] = 'A';
  G->Vex[1] = 'B';
  G->Vex[2] = 'C';
  // 初始化邻接矩阵
  for(int i = 0; i < G->vexnum; i ++) {
    for(int j = 0; j < G->vexnum; j ++) {
      G->Edge[i][j] = 0;
    }
  }
  // 边
  G->Edge[0][1] = G->Edge[1][0] = 1;
  G->Edge[1][2] = G->Edge[2][1] = 1;
  G->Edge[0][2] = G->Edge[2][0] = 1;


  return G;
}

int locatevex(AMGraph* G, VexType x) {
  for(int i = 0; i < G->vexnum; i ++) {
    if(x == G->Vex[i]) return i;
  }
  return -1;
}

void printAMGraph(AMGraph* G) {
  printf("邻接矩阵为：\n");
  /* printf("%d\t", G->vexnum); */
  for(int i = 0; i < G->vexnum; i ++) {
    for(int j = 0; j < G->vexnum; j ++) {
      printf("%d\t", G->Edge[i][j]);
    }
    printf("\n");
  }
}

// 广度优先遍历
void bfsAM(AMGraph* G, int v) {
  Queue Q = initialQueue();
  printf("%c\t", G->Vex[v]);
  visited[v] = 1;
  enQueue(Q, v);
  while(!isEmpty(Q)) {
    int u = getHead(Q);
    deQueue(Q);
    for (int i = 0; i < G->vexnum; i ++) {
      if(G->Edge[u][i] && !visited[i]) {
        printf("%c\t", G->Vex[i]);
        visited[i] = 1;
        enQueue(Q, i);
      }
    }
  }
}

void clearVisited() {
  for (int i = 0; i < MAXVNUM; i ++) {
    visited[i] = 0;
  }
}

int main(int argc, char *argv[])
{
  AMGraph *G = createAMGraph();
  printAMGraph(G);
  printf("\n");

  bfsAM(G, 0);
  printf("\n");
  clearVisited();
  bfsAM(G, 1);
  printf("\n");
  clearVisited();
  bfsAM(G, 2);
  printf("\n");
  clearVisited();
  return 0;
}

基于邻接表的BFS算法

查找顶点$v_i$的邻接点需要$O(d(v_i))$时间，$d(v_i)$为$v_i$的出度（无向图为度），对有向图而言，所有顶点的出度之和等于边数e，对无向图而言，所有顶点的度之和等于2e，因此查找邻接点的时间复杂度为$O(e)$，加上初始化时间$O(n)$，总的时间复杂度为$O(n+e)$，使用了一个辅助队列，最坏的情况下每个顶点入队一次，空间复杂度为$O(n)$。

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
// BFS有向邻接表
#include <stdio.h>
#include <stdlib.h>

// 有向图邻接表

// 顶点最大值
#define MAXVNUM 100

// 访问标志
int visited[MAXVNUM] = {0};

// 顶点数据类型
typedef char VexType;
typedef struct AdjNode {
  // 邻接点下标
  int v;
  // 下一个邻接点
  struct AdjNode *next;
} AdjNode;

typedef struct VexNode {
  // 顶点
  VexType data;
  // 指向第一个邻接点
  AdjNode *first;
} VexNode;

typedef struct ALGraph {
  VexNode *Vex;
  int vexnum, edgenum;
} ALGraph;

// 实现队列
typedef struct Queue {
  int val;
  struct Queue *next;
} *Queue;

// 最顶部不保存数据
Queue initialQueue() {
  Queue q = (Queue) malloc(sizeof(Queue));
  if(!q) return NULL;
  q->next = NULL;
  return q;
}

int isEmpty(Queue q) {
  return q->next == NULL;
}

void enQueue(Queue q, int val) {
  Queue p = q;
  while(p->next) {
    p = p->next;
  }
  Queue elem = (Queue) malloc(sizeof(Queue));
  elem->val = val;
  p->next = elem;
}

void deQueue(Queue q) {
  if(!isEmpty(q)) {
    Queue temp = q->next;
    q->next = temp->next;
    free(temp);
  }
}

int getHead(Queue q) {
  if(isEmpty(q)) {
    printf("queue is empty.\n");
    return -1;
  }
  return q->next->val;
}

// 查找顶点的下标
int locatevex(ALGraph* G, VexType x) {
  for(int i = 0; i < G->vexnum; i ++) {
    if(x == G->Vex[i].data) return i;
  }
  return -1;
}

// 插入一条边
void insertEdge(ALGraph* G, int i, int j) {
  AdjNode *s = (AdjNode*) malloc(sizeof(AdjNode));
  s->v = j;
  s->next = G->Vex[i].first;
  G->Vex[i].first = s;
}

ALGraph* createALGraph() {
  ALGraph *G = (ALGraph*) malloc(sizeof(ALGraph));
  // 顶点和边
  G->vexnum = 3;
  G->edgenum = 3;
  G->Vex = (VexNode*) malloc(G->vexnum * sizeof(VexNode));
  G->Vex[0].data = 'A';
  G->Vex[1].data = 'B';
  G->Vex[2].data = 'C';
  G->Vex[0].first = NULL;
  G->Vex[1].first = NULL;
  G->Vex[2].first = NULL;
  insertEdge(G, locatevex(G, 'A'), locatevex(G, 'B'));
  insertEdge(G, locatevex(G, 'B'), locatevex(G, 'C'));
  insertEdge(G, locatevex(G, 'C'), locatevex(G, 'A'));

  return G;
}

void printALGraph(ALGraph* G) {
  printf("邻接矩阵为：\n");
  /* printf("%d\t", G->vexnum); */
  for(int i = 0; i < G->vexnum; i ++) {
    AdjNode *t = G->Vex[i].first;
    printf("%c: ", G->Vex[i].data);
    while(t != NULL) {
      printf(" [%d] ", t->v);
      t = t->next;
    }
    printf("\n");
  }
}

void bfsAL(ALGraph* G, int v) {
  printf("%c\t", G->Vex[v].data);
  visited[v] = 1;

  Queue Q = initialQueue();
  enQueue(Q, v);
  AdjNode *p;
  while(!isEmpty(Q)) {
    int u = getHead(Q);
    deQueue(Q);
    p = G->Vex[u].first;
    while(p) {
      if(!visited[p->v]) {
        printf("%c\t", G->Vex[p->v].data);
        visited[p->v] = 1;
        enQueue(Q, p->v);
      }
      p = p->next;
    }
  }
}

void clearVisited() {
  for (int i = 0; i < MAXVNUM; i ++) {
    visited[i] = 0;
  }
}

int main(int argc, char *argv[])
{
  ALGraph *G = createALGraph();
  printALGraph(G);
  bfsAL(G, 0);
  printf("\n");
  clearVisited();
  bfsAL(G, 1);
  printf("\n");
  clearVisited();
  bfsAL(G, 2);
  printf("\n");
  clearVisited();
  return 0;
}