陈越《数据结构》第六讲 图(上)
6.1 什么是图6.1.1 定义
6.1.2 抽象数据类型6.1.3 常见术语
6.1.4 怎么在程序中表示一个图
6.2 图的遍历6.2.1 深度优先搜索(Depth First Search,DFS)
6.2.2 广度优先搜索 (Breadth First Search,BFS)
6.2.3 DFS和BFS的优点和缺点
6.2.4 图不连通怎么办?
打印每个连通图: 6.3/* queue 模板类的定义在<queue>头文件中。 与stack 模板类很相似,queue 模板类也需要两个模板参数,一个是元素类型,一个容器类 型,元素类型是必要的,容器类型是可选的,默认为deque 类型。 定义queue 对象的示例代码如下: queue<int> q1; queue<double> q2; queue 的基本操作有: 入队,如例:q.push(x); 将x 接到队列的末端。 出队,如例:q.pop(); 弹出队列的第一个元素,注意,并不会返回被弹出元素的值。 访问队首元素,如例:q.front(),即最早被压入队列的元素。 访问队尾元素,如例:q.back(),即最后被压入队列的元素。 判断队列空,如例:q.empty(),当队列空时,返回true。 */
#include<iostream>
#include<string.h>
#include "queue"
using namespace std;
int M[10][10]; //存储图的矩阵;
bool visited[10]; //看图中的每个节点是否访问过;
int result[10]; //存放结果的矩阵;
int vertex,ridge; //顶点和边
int k; //计每一个邻接表存储的结果
void DFS(int x)
{
/*深度搜索*/
int i;
result[k++] = x;
visited[x] = true;
for(i = 0;i < vertex; i++)
{
if(M[x][i] == 1 && !visited[i])
/*是否有边;是否访问过*/
DFS(i);
}
}
void BFS(int x)
{
int i;
queue<int> q;
q.push(x);
visited[x] = 1;
result[k++] = x;
while (!q.empty()) {
int l = q.front();
q.pop();
for ( i = 0; i < vertex; i++)
{
if (M[l][i] == 1 && !visited[i])
{
/*是否有边;是否访问过*/
visited[i] = 1;
result[k++] = i;
q.push(i);
}
}
}
}
int main()
{
int i,j,m,n;
cin>>vertex>>ridge;
/*初始化*/
memset(visited,0,sizeof(visited)); //visited数列全部为0
for(i = 0;i < vertex;i++)
{
for(j = 0; j < ridge; j++)
{
M[i][j] = 0;
}
}
while(ridge--)
{
cin>>m>>n;
M[m][n] = 1;
M[n][m] = 1;
}
/*开始进行深度搜索*/
for(i = 0;i < vertex;i++ )
{
k = 0;
if(!visited[i])
{
DFS(i);
cout<<"{ ";
for(j = 0;j < k;j++)
cout<<result[j]<<" ";
cout<<"}"<<endl;
}
}
/*开始进行广度搜索*/
memset(visited,sizeof(visited));
for ( i = 0; i < vertex; i++)
{
k = 0;
if (!visited[i]) {
BFS(i);
cout << "{ ";
for ( j = 0; j < k; j++)
cout << result[j] << " ";
cout << "}" << endl;
}
}
//system("pause");
return 0;
}
6.4#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
/*邦德*/
using namespace std;
const int inf=1<<30;
struct node
{
double x,y;
} a[100+5];
int n,vis[100+5],b[100+5],ans[100+5],cnt;
double d,ansfirst,nowfirst;
int dis(node d1,node d2)
{
if(d*d<(d1.x-d2.x)*(d1.x-d2.x)+(d1.y-d2.y)*(d1.y-d2.y)) return 0;
return 1;
}
int first(int d1)
{
if(sqrt(a[d1].x*a[d1].x+a[d1].y*a[d1].y)>d+7.5) return 0;
else return 1;
}
double first1(int d1)
{
return sqrt(a[d1].x*a[d1].x+a[d1].y*a[d1].y)-7.5;
}
int safe(node d1)
{
if(d1.x>=50-d) return 1;
if(d1.y>=50-d) return 1;
if(d1.x<=-50+d) return 1;
if(d1.y<=-50+d) return 1;
return 0;
}
void dfs(int d1,int now)
{
int i;
if(safe(a[d1]))
{
//printf("%d %.2fn",now,nowfirst);
if(now<cnt)
{
for(i=0; i<now; i++)
ans[i]=b[i];
cnt=now;
ansfirst=nowfirst;
}
else if(now==cnt&&ansfirst>nowfirst)
{
for(i=0; i<now; i++)
ans[i]=b[i];
cnt=now;
ansfirst=nowfirst;
}
return ;
}
else
{
for(i=1; i<=n; i++)
{
if(!vis[i]&&dis(a[d1],a[i]))
{
vis[i]=1;
b[now]=i;
dfs(i,now+1);
vis[i]=0;
}
}
}
return;
}
int main()
{
int i;
while(~scanf("%d%lf",&n,&d))
{
a[0].x=a[0].y=0;
for(i=1; i<=n; i++)
{
scanf("%lf%lf",&a[i].x,&a[i].y);
}
if(d+7.5>=50)
{
printf("1n");
return 0;
}
ansfirst=(double)inf;
cnt=inf;
memset(ans,sizeof(ans));
for(i=1; i<=n; i++)
{
memset(vis,sizeof(vis));
if(!vis[i]&&first(i))
{
nowfirst=first1(i);
if(safe(a[i]))
{
if(ansfirst>nowfirst)
{
ans[0]=i;
cnt=1;
ansfirst=nowfirst;
}
}
vis[i]=1;
memset(b,sizeof(b));
b[0]=i;
dfs(i,1);
}
}
if(cnt==inf) printf("0n");
else
{
printf("%dn",cnt+1);
for(i=0; i<cnt; i++)
{
printf("%.0f %.0fn",a[ans[i]].x,a[ans[i]].y);
}
}
}
return 0;
}
6.5/* 题意: 找到一个图中每个节点通过最多5条边 能找到的所有节点 然后输出百分比 思路:广搜 记录层数为6以内的所有节点 本题的关键在于 如何记录节点当前的层数 1. 引入2个变量 last tail 分别指向 当前层数的最后一个元素 和 下一层的最后一个 元素 2. 若当前出队的元素与last相等 则说明即将进入下一层 将last更新为tail 更新tail 重复~~知道level = 6 或者队列空 */
/*6度空间*/
#include "iostream"
#include "stdio.h"
#include "queue"
using namespace std;
bool map[10001][10001] = {false};
int n,m;
int Count;
void bfs(int x) {
bool visited[10001] = { false };
queue<int>q;
q.push(x);
visited[x] = true;
int level = 0; /* 记录层数 */
int last = x; /* 记录当前层数的最后一个元素 */
int tail; /* 指向下一层最后一个元素 */
while (!q.empty()) {
x = q.front();
q.pop();
for (int i = 1; i <= n; i++) {
if (!visited[i] && map[x][i] == 1) {
q.push(i); /* 进队 */
Count++;
visited[i] = true;
tail = i;
}
}
if (last == x) {
level++;
last = tail;
}
if (level == 6)
break;
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int k,l;
cin >> k >> l;
map[k][l] = 1;
map[l][k] = 1;
}
for (int i = 1; i <=n; i++) { /* 对于所有节点 做bfs() */
Count = 1;
bfs(i);
cout << i << ": ";
float answer = (float)Count / n * 100;
printf("%.2f%%n",answer);
}
return 0;
} (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |