6.1 什么是图
6.1.1 定义
- 图示表示“多对多”的关系（树与线性表都可以认为是其特殊形式）；
- 图包含：
一组顶点 ：通常用V (Vertex) 表示顶点集合；一组边 ：通常用E (Edge) 表示边的集合;
— 边是顶点对：(v,w)∈E ，其中v,w∈V ;
— 又向边<v,w> 表示从v 指向w 的边（单行线）；
— 不考虑重边与回路。
6.1.2 抽象数据类型
6.1.3 常见术语
无向图 ：无向图中顶点之间的边无方向性，边(w,v) 同(v,w) ;
有向图 ：有向图中顶点之间的边有方向性，边<w,v> 不同<v,w> ;
简单图 ：图中出现重边，则称之为非简单图；
邻接点 ：如果(v,w) 是无向图中任意一条边，那么称v 和w 互为“邻接点”；如果<v,w> 是有向图中任意一条边，那么称v 邻接到终点w ，也称w 邻接自终点v 。
有向完全图 ：一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称“有向完全图”；一个含有n 个顶点的有向完全图中，共有n(n−1)/2 条边。
稠密图、稀疏图 ：一个图的”稠密度“定义为平均顶点度2|E|/|V| ；稠密图可定量地定义为“平均顶点度与顶点数量|V|成正比的图” 。
权、网络 ：边上附加一个数值信息我们称之为权；边上带权的图称为网图或“网络”。顶点的度、入度、出度 ：顶点v 的度是指依附于该顶点的边数。在有向图中，顶点的度分为出度和入度。
6.1.4 怎么在程序中表示一个图
1.
邻接矩阵
优势：
- 直观、简单、好理解；
- 方便检查任意一对顶点间是否存在边；
- 方便找任一顶点的所有“邻接点”（有边直接相连的顶点）；
- 方便计算任一顶点的“
度 ”（从该点发出的边数为“出度”，指向该点的边数为“入度”）；
– 无向图：对应行（或列）非0元素的个数；
– 有向图：对应行非0 元素的个数是“出度”；对应列非0元素的个数是“入度”。劣势：
- 浪费空间（特别是稀疏图）；
- 浪费时间 （例如：统计稀疏图中一共有多少条边）。
2.
数组
用一个长度为N(N+1)/2 的1 维数组A存储；{G00,G10,G11,……,G(n−1)0,…,G(n−1)(n−1)} ，则Gij 在A 中对应的下标是：
i∗(i+1)/2+j
对于网络 ，只要把G[i][j] 的值定义为边<vi,vj> 的权重即可。3.
邻接表
- 方便找任一顶点的所有“邻接点”;
- 节约
稀疏图 的空间；
– 需要N 个头指针 +2E 个结点（每个结点至少2 个域）。- 方便计算任一顶点的“
度 ”？
– 对无向图：是的；
– 对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”。- 方便检查任意一对顶点间是否存在边？（
No ）
用一维数组G[ ]存储有4个顶点的无向图如下：
G[]=0,1,0,1,1,0,0,0,1,0 则顶点2和顶点0之间是有边的。(对或错？)
答：对，记得从0开始计数，运用数组的公式i∗(i+1)/2+j 。用邻接表表示有
N 个顶点、E 条边的图，则遍历图中所有边的时间复杂度为：O(N+E) 。
6.2 图的遍历
6.2.1 深度优先搜索（Depth First Search，DFS）
若有
N 个顶点、E 条边，时间复杂度 是：
- 用邻接表存储图，有O(N+E) ;
- 用邻接矩阵存储图，有O(N2) ;
6.2.2 广度优先搜索 (Breadth First Search,BFS)
若有
N 个顶点、E 条边，时间复杂度 是：
- 用邻接表存储图，有O(N+E) ;
- 用邻接矩阵存储图，有O(N2) 。
6.2.3 DFS和BFS的优点和缺点
BFS :一种基于队列这种数据结构的搜索方式，它的特点是由每一个状态可以扩展出许多状态，然后再以此扩展，直到找到目标状态或者队列中头尾指针相遇，即队列中所有状态都已处遍历完毕。
- 优点：对于解决最短或最少问题特别有效，而且寻找深度小;
- 缺点：内存耗费量大，需要开辟大量的数组单元用来存储状态。
DFS ：基于递归的搜索方式，它的特点是由一个状态扩展到另外一个状态，然后不停地扩展，直到找到目标或者无法继续到另一个状态。
- 优点：占内存少，对于解决连通性性问题比较有效，能找到最优解（一定条件下），但能很快找到接近解；
- 缺点：可能不必遍历所有分枝（也就是速度快），在深度很大的情况下效率不高。
6.2.4 图不连通怎么办？
连通 ：如果从V 到W 存在一条（无向）路径 ，则称V 和W 是连通的。路径 ：V 到W 的路径是一系列顶点{V,v1,v2,…,vn,W} 的集合，其中任一对相邻的顶点间都有图中的边。路径的长度 是路径中的边数（如果带权，则是所有边的权重和）。如果V 到W 之间的所有顶点都不同，则称之间的所有顶点都不同，则称简单路径 。回路 ：起点等于终点的路径。连通图 ：图中任意两顶点均连通。连通分量 ：无向图的 极大 连通子图
- 极大顶点数：再加1个顶点就不连通了；
- 极大边数：包含子图中所有顶点相连的所有边。
强连通 ：有向图中顶点V 和W 之间存在双向路径，则称V 和W 是强连通的。强连通图 ：有向图中任意两顶点均强连通。强连通分量 ：有向图的极大强连通子图。
打印每个连通图：
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 %.2f\n",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("1\n");
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("0\n");
else
{
printf("%d\n",cnt+1);
for(i=0; i<cnt; i++)
{
printf("%.0f %.0f\n",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;
}