Question

c语言实验：图的建立和深度遍历程序

谁能帮个忙，帮忙贴下图的建立和深度遍历的源程序？最近看到数据结构的图和树总是稀里糊涂的，书上全是算法，看了一点感觉没有。。。。

Answer 1

#include "stdio.h"
#include "string.h"
#define MAX 21

int legal(int x, int y);
void dfs(int i, int j);

char map[MAX][MAX];
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int w, h;
int ans;

int main(void)
{
while (scanf("%d%d", &w, &h) && (w + h))
{
int i, j;
int si, sj;
ans = 0;

memset(map, 0, sizeof(map));

for (i=0; i<h; i++)
{
scanf("%s", map[i]);

for (j=0; j<w; j++)
{
if (map[i][j] == '@')
{
si = i;
sj = j;
}
}
}

dfs(si, sj);

printf("%d\n", ans);
}

return 0;
}

int legal(int x, int y)
{
if (x < 0 || x > h || y < 0 || y > w)
{
return 0;
}

return 1;
}

void dfs(int i, int j)
{
int k;
int x, y;

++ans;
map[i][j] = '#';

for (k=0; k<4; k++)
{
x = i + dir[k][0];
y = j + dir[k][1];

if (legal(x, y) && map[x][y] == '.')
{
dfs(x, y);
}
}
}

这是一个简单的 深搜的例子！

Answer 2

#include <stdio.h>

int m,n;
bool w[100][100],visited[100];

void dfs(int i){
visited[i] = true;
printf("%d ",i);
for(int j = 0;j<n;j++)
if(w[i][j] && !visited[j])
dfs(j);
}

int main(){
scanf("%d%d",&m,&n);
int a,b;
for(int i = 0;i<m;i++){
scanf("%d%d,&a,&b);
w[a][b] = w[b][a] = true;
}
for(int i = 0;i<n;i++)
if(!visited[i])
dfs(i);
return 0;
}
你的串号我已经记下，采纳后我会帮你制作

Answer 3

#include <stdio.h>

int m,n;
bool w[100][100],visited[100];

void dfs(int i){
visited[i] = true;
printf("%d ",i);
for(int j = 0;j<n;j++)
if(w[i][j] && !visited[j])
dfs(j);
}

int main(){
scanf("%d%d",&m,&n);
int a,b;
for(int i = 0;i<m;i++){
scanf("%d%d,&a,&b);
w[a][b] = w[b][a] = true;
}
for(int i = 0;i<n;i++)
if(!visited[i])
dfs(i);
return 0;
}