-
极资源官方
- 热度7463℃
图的遍历，我们用深度优先搜索遍历图和广度优先搜索遍历图。最简单的一种图的遍历-穷举！
如下的图：
点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
友情提示：垃圾评论一律封号...