算法九:深度优先搜索和广度优先搜索来遍历图
图的遍历,我们用深度优先搜索遍历图和广度优先搜索遍历图。最简单的一种图的遍历-穷举!
如下的图:
点1和点2,3,5有边,点3和点5有边,点2和点4有边。mac画的好累。。没有鼠标。。
输入:第一行是点的总数和边的总数,下面几行都是那几个点有边。
5 5
1 2
1 3
1 5
2 4
3 5
深度优先搜索来遍历图,代码如下:
#include <stdio.h>
int a[101][101];
int book[101];
int m, n, sum=0;
void dfs(int node);
int main(){
int i, j, x, y;
scanf("%d %d", &m, &n);
for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
a[i][j] = 0;
}
}
for(i=0; i<m; i++){
scanf("%d %d", &x, &y);
a[x][y] = 1;
a[y][x] = 1;
}
book[1] = 1;
dfs(1);
}
void dfs(int node){
printf("%d ", node);
sum++;
if(sum == n){
return;
}
int i = 0;
for(i=1; i<=n; i++){
if(book[i] != 0 || a[node][i] != 1) continue;
book[i] = 1;
dfs(i);
}
}
输出:1,2,4,3,5
广度优先搜索来遍历图,代码如下:
输入:第一行是点的总数和边的总数,下面几行都是那几个点有边。
#include <stdio.h>
int a[101][101];
int book[101];
int m, n;
void dfs(int node);
int main(){
int i, j, x, y;
scanf("%d %d", &m, &n);
for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
a[i][j] = 0;
}
}
for(i=0; i<m; i++){
scanf("%d %d", &x, &y);
a[x][y] = 1;
a[y][x] = 1;
}
book[1] = 1;
//广度优先搜索
int head = 0, tail = 0;
int queue[25];
for(i=0; i<25; i++) queue[i] = 0;
queue[tail] = 1;
tail++;
while(head<tail){
printf("%d ", queue[head]);
for(i=1; i<=n; i++){
if(book[i] != 0 || a[queue[head]][i] != 1) continue;
book[i] = 1;
queue[tail] = i;
tail++;
}
head++;
}
}
输出:1,2,3,5,4
学习了,希望博主多多分享。