以下是老师作为数据结构课的作业的要求,没有什么实际用处和可以探讨和总结的的地方,所以简单代码直接展示。
宽度优先遍历:
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std; #define _clr(x, y) memset(x, y, sizeof(x))
#define N 1010 int head[N], tot;
struct Edge
{
int v, next;
}edge[N];
int Queue[N];
bool used[N]; void Add(int u, int v)
{
edge[tot].v = v;
edge[tot].next = head[u];
head[u] = tot++;
} void bfs(int s)
{
_clr(Queue, );
_clr(used, );
int front=, rear=;
Queue[rear++] = ;
cout << s <<" ";
used[s] = true;
while(front < rear)
{
int Cur = Queue[front++];
for(int i=head[Cur]; i!=-; i=edge[i].next)
{
int v = edge[i].v;
if(!used[v])
{
used[v] = true;
cout << v << " ";
Queue[rear++] = v;
}
}
}
cout << endl;
}
int main()
{
int n, m, x, y;
cout << "请输入图的顶点数和边数: ";
while(cin >> n >> m && n+m)
{
tot = ;
_clr(head, -);
for(int i=; i<m; i++)
{
scanf("%d%d",&x, &y);
Add(x, y);
}
cout << "广度优先遍历顺序如下:\n";
bfs();
cout<<endl;
cout << "请输入图的顶点数和边数(输入两个0代表结束输入): ";
}
return ;
}
深度优先遍历:
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std; #define _clr(x, y) memset(x, y, sizeof(x))
#define N 1010 int head[N], tot;
struct Edge
{
int v, next;
}edge[N];
int Queue[N];
bool used[N]; void Add(int u, int v)
{
edge[tot].v = v;
edge[tot].next = head[u];
head[u] = tot++;
} void dfs(int s)
{
cout << s << " ";
for(int i=head[s]; i!=-; i=edge[i].next)
{
int v = edge[i].v;
if(!used[v])
{
used[v] = true;
dfs(v);
}
}
}
int main()
{
int n, m, x, y;
cout << "请输入图的顶点数和边数: ";
while(cin >> n >> m && n+m)
{
tot = ;
_clr(head, -);
for(int i=; i<m; i++)
{
scanf("%d%d",&x, &y);
Add(x, y);
}
cout << "深优先遍历顺序如下:\n";
dfs();
cout<<endl;
cout << "请输入图的顶点数和边数(输入两个0代表结束输入): ";
}
return ;
}