利用宽度优先搜索 和 深度优先搜索来遍历图
矩阵存储bfs
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
queue <int> qu, qq;
int map[100][100], m, n, judge[100], path[100];
void bfs(){//和导论上的染色的方法差不多，judge[0] == 0 时候代表白色节点 在队列里面的节点是灰色的 出队列的是黑色的。
int w, s,t,i, j;
while(true){
s = qu.size();
if(!s)return;
while(s--){
t = qu.front();
for(i = 0; i < n; i++){
if(map[t][i] && !judge[i]){
judge[i] = true;
qu.push(i);
path[i] = t;//记录宽度优先搜索树中的当前节点的父亲
//printf("path[%d] = %d\n", i, t);
}
}
qu.pop();
}
}
}
void printpath(int n){ //递归的输出路径
if(path[n] == -1)printf("%d ", n);
else{
printpath(path[n]);
printf("%d ", n);
}
}
int main(){
freopen("bfs.in", "r", stdin);
freopen("bfs.out", "w", stdout);
int i, j, u, v;
while(scanf("%d%d", &n, &m) != -1){
memset(judge, 0, sizeof(judge));
for(i = 0; i < m; i++){
scanf("%d%d", &u, &v);
map[u][v] = map[v][u] = 1;
}
judge[0] = true;qu = qq;
qu.push(0);memset(path, -1, sizeof(path));
bfs();
for(i = 1; i < n; i++){
printf("from 0 to %d : ", i);
printpath(i);puts("");
}
}
return 0;
}
链表存储bfs
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
queue<int> qu, qq;
struct e{
int v;
e* next;
};
e* edge[100];int m, n, judge[100], path[100];
void bfs(){
int w, i, j, t, s;e* l;
while(true){
s = qu.size();
if(!s)return;
while(s--){
w = qu.front();
l = edge[w];
while(l){
t = l->v;
if(!judge[t]){
judge[t] = true;
qu.push(t);
path[t] = w;
}
l = l->next;
}
qu.pop();
}
}
}
void printpath(int x){
if(path[x] == -1)printf("%d ", x);
else{
printpath(path[x]);
printf(" %d", x);
}
}
int main(){ //个人不推荐动态开辟存储空间，建议静态。
freopen("bfs_link.in", "r", stdin);
freopen("bfs_link.out", "w", stdout);
int u, v, i, j;e* node;
while(scanf("%d%d", &n, &m) != -1){
memset(judge, 0, sizeof(judge));
memset(path, -1, sizeof(path));
for(i = 0; i < m; i++){
scanf("%d%d", &u, &v);
node = new e;
node->v = v;
node->next = edge[u];
edge[u] = node;
node = new e;
node->v = u;
node->next = edge[v];
edge[v] = node;
}
judge[0] = true;qu = qq;qu.push(0);
bfs();
for(i = 1; i < n; i++){
printf("path from 0 to %d : ", i);
printpath(i);puts("");
}
}
return 0;
}
矩阵存储dfs
#include <stdio.h>
#include <string.h>
int map[100][100], m, n, d[100], f[100], time, path[100];
bool judge[100];
void dfs(int v){
int i;judge[v] = true;
time++;d[v] = time;//开始时间
for(i = 0; i < n; i++){
if(map[v][i] && !judge[i]){
path[i] = v;//记录深度优先搜索树中的父亲节点
dfs(i);
}
}
time++;f[v] = time;//结束时间
}
void printpath(int v){
if(path[v] == -1)printf("%d ", v);
else{
printpath(path[v]);
printf(" %d", v);
}
}
int main(){
freopen("dfs_m.in", "r", stdin);
freopen("dfs_m.out", "w", stdout);
int i, j, u, v;
while(scanf("%d%d", &n, &m) != -1){
memset(map, 0, sizeof(map));
memset(judge, 0, sizeof(judge));
memset(path, -1, sizeof(path));
for(i = 0; i < m; i++){
scanf("%d%d", &u, &v);
map[u][v] = map[v][u] = true;
}
time = 0;dfs(0);
for(i = 0; i < n; i++){
printf("d[%d] = %d f[%d] = %d\n", i, d[i], i, f[i]);
}
for(i = 1; i < n; i++){
printf("path from 0 to %d : ");
printpath(i);puts("");
}
}
return 0;
}
链表存储dfs
#include <stdio.h>
#include <string.h>
struct e{
int v;
e* next;
};
e* link[100];e edge[10000];//静态的
int m, n, el, judge[100], d[100], f[100], time, path[100];
void dfs(int v){
int i, t;e* l;
judge[v] = true;
time++;d[v] = time;
l = link[v];
while(l){
t = l->v;
if(!judge[t]){
judge[t] = true;
path[t] = v;
dfs(t);
}
l = l->next;
}
time++;f[v] = time;
}
void printpath(int v){
if(path[v] == -1)printf("%d", v);
else{
printpath(path[v]);
printf(" %d", v);
}
}
int main(){
freopen("dfs_link.in", "r", stdin);
freopen("dfs_link.out", "w", stdout);
int i, j, u, v;
while(scanf("%d%d", &n, &m) != -1){
memset(judge, 0, sizeof(judge));
memset(link, 0, sizeof(edge));
memset(path, -1, sizeof(path));
for(i = 0, el = 0; i < m; i++){
scanf("%d%d", &u, &v);
edge[el].v = v;
edge[el].next = link[u];
link[u] = &edge[el++];
edge[el].v = u;
edge[el].next = link[v];
link[v] = &edge[el++];
}time = 0;
for(i = 0; i < n; i++){
if(!judge[i])dfs(i);
}
for(i = 0; i < n; i++){
printf("d[%d] = %d f[%d] = %d\n", i, d[i], i, f[i]);
}
for(i = 1; i < n; i++){
printf("path form 0 to %d : ", i);
printpath(i);puts("");
}
}
return 0;
}