陈越《数据结构》第六讲 图(上)

6.1 什么是图


6.1.1 定义


  1. 图示表示“多对多”的关系(树与线性表都可以认为是其特殊形式);
  2. 包含:
    • :通常用 V (Vertex) 表示顶点集合;
    • :通常用 E (Edge) 表示边的集合;
      — 边是顶点对: (v,w)E ,其中 v,wV ;
      — 又向边 <v,w> 表示从 v 指向 w 的边(单行线);
      — 不考虑重边与回路。
      这里写图片描述

6.1.2 抽象数据类型


这里写图片描述

6.1.3 常见术语


  1. :无向图中顶点之间的边无方向性,边 (w,v) (v,w) ;

  2. :有向图中顶点之间的边有方向性,边 <w,v> 不同 <v,w> ;

  3. :图中出现重边,则称之为非简单图;

  4. :如果 (v,w) 是无向图中任意一条边,那么称 v w 互为“邻接点”;如果 <v,w> 是有向图中任意一条边,那么称 v 邻接到终点 w ,也称 w 邻接自终点 v

  5. :一个有向图中,如果任意两顶点之间都有方向互为相反的两条弧相连接,则称“有向完全图”;一个含有 n 个顶点的有向完全图中,共有 n(n1)/2 条边。

  6. :一个图的”稠密度“定义为平均顶点度 2|E|/|V| 稠密图可定量地定义为 |V|

  7. :边上附加一个数值信息我们称之为;边上带权的图称为网图或“网络”。

  8. :顶点 v 是指依附于该顶点的边数。在有向图中,顶点的度分为出度入度

6.1.4 怎么在程序中表示一个图


1.
优势

  • 直观、简单、好理解;
  • 方便检查任意一对顶点间是否存在边;
  • 方便找任一顶点的所有“邻接点”(有边直接相连的顶点);
  • 方便计算任一顶点的“ ”(从该点发出的边数为“出度”,指向该点的边数为“入度”);
    无向图:对应行(或列)非0元素的个数;
    有向图:对应非0 元素的个数是“出度”;对应非0元素的个数是“入度”。

劣势

  • 浪费空间(特别是稀疏图);
  • 浪费时间 (例如:统计稀疏图中一共有多少条边)。

2.
用一个长度为N(N+1)/2 的1 维数组A存储; {G00,G10,G11,,G(n1)0,,G(n1)(n1)} ,则 Gij A 中对应的下标是:
i(i+1)/2+j
对于 ,只要把 G[i][j] 的值定义为边 <vi,vj> 的权重即可。


3.

  • 方便找任一顶点的所有“邻接点”;
  • 节约 的空间;
    – 需要 N 头指针 + 2E 结点(每个结点至少 2 )。
  • 方便计算任一顶点的“ ”?
    – 对无向图:是的;
    – 对有向图:只能计算“出度”;需要构造“逆邻接表”(存指向自己的边)来方便计算“入度”。
  • 方便检查任意一对顶点间是否存在边?( No
  1. 用一维数组G[ ]存储有4个顶点的无向图如下:
    G[]=0,1,0,1,1,0,0,0,1,0 则顶点2和顶点0之间是有边的。(对或错?)
    :对,记得从0开始计数,运用数组的公式 i(i+1)/2+j

  2. 用邻接表表示有 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 图不连通怎么办?

  1. :如果从 V W 存在一条(无向)路径 ,则称V 和W 是连通的
  2. V W 的路径是一系列顶点 {V,v1,v2,,vn,W} 的集合,其中任一对相邻的顶点间都有图中的边。 是路径中的边数(如果带权,则是所有边的权重和)。如果 V W 之间的所有顶点都不同,则称之间的所有顶点都不同,则称
  3. :起点等于终点的路径。
  4. :图中任意两顶点均连通。
  5. 无向图极大 连通子图
    • 极大顶点数:再加1个顶点就不连通了;
    • 极大边数:包含子图中所有顶点相连的所有边。

这里写图片描述

  1. 有向图中顶点 V W 之间存在双向路径,则称 V W 是强连通的。
  2. 有向图任意两顶点均强连通。
  3. 有向图极大强连通子图。

这里写图片描述

打印每个连通图:
这里写图片描述

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, 0, 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,0,sizeof(ans));
        for(i=1; i<=n; i++)
        {
            memset(vis,0,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,0,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;
}
相关文章
相关标签/搜索