图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问

这篇具有很好参考价值的文章主要介绍了图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.图的定义和术语

:G = (V,E) Graph = (Vertex, Edge)

V:顶点(数据元素)的有穷非空集合;

E:边的有穷集合。

有向图:每条边都是有方向的

图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问 

 无向图:每条边都是无方向的

图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问

 完全图:任意两点之间都有一条边相连

图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问 

 无向完全图:n个顶点,n(n-1)/2条边

无向完全图:n个顶点,n(n-1)条边

稀疏图:有很少边或弧的图(e<nlog n)

稠密图:有较多边或弧的图像

:边或弧带权的图

邻接:有边或弧相连的两个顶点之间的关系。存在(vi, vj),则称vi和vj互为邻接点;存在<vi, vj>,则称vi邻接到vj,vj邻接于vi。

关联(依附):边或弧与顶点之间的关系。存在(vi, vj)或<vi, vj>,则称该边或者弧关联于vi和vj。

顶点的度:与该结点相关联的边的数目,记为TD(v)

在有向图中,顶点的度等于该顶点的入度出度之和

顶点v的入度是以V为终点的有向边的条数,记作ID(v)

图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问 

 路径:接续的边构成的顶点序列

路径长度:路径上边或弧的数目/权值之和。

回路(环):第一个顶点和最后一个顶点相同的路径。

简单路径:除路径起点和终点可以相同外,其余顶点均不相同的路径。

连通图(强连通图):在无(有)向图G=(V,{E})中,若对任何两个顶点v、u都存在从v到u的路径,则称G是连通图(强连通图)。

图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问 

 

 图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问

 权和网

图中边或弧所具有的相关数称为。表明从一个顶点到另一个顶点的距离或耗费。

子图 设有两个图G=(V,{E})、G1=(V1,{E1}),若V1被包含于V,E1被包含于E,则称G1是G的子图。

连通分量(强连通分量)

无向图G的极大连通子图称为G的连通分量。

极大连通子图意思是:该子图是G连通子图,将G的任何不在该子图中的顶点加入,子图不再连通。

图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问 

 极小连通子图:该子图是G的连通子图,在该子图中删除任何一条边,子图不在连通。

生成树:包含无向图G所有定点的极小连通子图。

生成森林:对非连通图,由各个连通分量的生成树的集合。

2.图的类型定义

图的抽象数据类型定义如下:

ADT Graph
{
    数据对象V:具有相同特性的数据元素的集合,称为顶点集;
    数据关系R: R = {VR}
        VR = {<v,w>|<v,w>|v,w∈V ^ p(v,w),
              <v,w>表示从v到w的弧,P(v,w)定义了弧<v,w>的信息
             }
}
​
基本操作P:
Create Graph():图的创建操作。
CreateGraph(&G,V,VR)
{
    初始条件:V是图的顶点集,VR是图中弧的集合。
    操作结果:按V和VR的定义构造图G。
}
​
DFSTraverse(G)
初始条件:图G存在。
操作结果:对图进行深度优先遍历。
​
BFSTraverse(G)
初始条件:图G存在。
操作结果:对图进行广度优先遍历。

3.图的建立

1.邻接矩阵

邻接矩阵的存储表示:用两个数组分别存储顶点表和邻接矩阵

存储形式

#define MVNum 100
typedef char VerTexType;//设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型
​
typedef struct
{
    VerTexType vexs[MVNum];//顶点表
    ArcType arcs[MVNum][MVNum];//邻接矩阵
    int vexnum, arcnum;//图的当前点数和边数
}AMGraph;//Adjacency Matrix Graph

顶点的结点结构

typedef struct VNode
{
    VerTexType data;//顶点信息
    ArcNode * firstarc;//指向第一条依附该顶点的指针
}VNode,AdjList[MVNum];//AdjList表示邻接

说明:例如,AdjList v;相当于:VNode v[MVNum];

图的邻接表存储表示

#define MVNum 100 //最大顶点数
typedef struct ArcNode
{
    //边结点
    int adjvex;//该边所指向的顶点的位置
    struct ArcNode * nextarc;//指向下一条边的指针
    OtherInfo info;//和边有关的信息
}ArcNode;

图的结构定义

typedef struct
{
    AdjList vertices;//vertices--vertex的复数
    int vexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;

图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问 

 2.邻接表

采用邻接表表示法创建无向网

  1. 输入总顶点数和总边数。

  2. 建立顶点表 依次输入点的信息存入顶点表中 使每个表头结点的指针域初始化为NU儿L

  3. 创建邻接表 依次输入每条边依附的两个顶点 确定两个顶点的序号和j,建立边结点 将此边结点分别插入到和V对应的两个边链表的头部

Status CreateUDG(ALGraph &G)
{
    //采用邻接表表示法,创建无向图G
    cin >> G.vexnum >> G.arcnum;//输入总顶点数,总边数
    for(i = 0;i < G.vexnum; ++i)
    {
        cin >> G.vertices[i].data;//输入顶点值
        G.vertices[i].firstarc = NULL;//初始化表头结点的指针域
    }
    for(k = 0;k < G.arcnum; ++k)
    {
        //输入各边,构造邻接表
        cin >> v1 >> v2;//输入一条边依附的两个顶点
        i = LocateVex(G, v1);
        j = LocateVex(G, v1);
        
        p1 = new ArcNode;//生成一个新的边结点*p1
        p1->adjvex = j;//邻接点序号为j
        p1->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p1;//将新结点*p1插入顶点vi的边表头部
        
        p2 = new ArcNode;//生成一个新的边结点*p2
        p2->adjvex = i;//邻接点序号为i
        p2->nextarc = G.vertices[j].firstarc;
        G.vertices[j].firstarc = p2;//将新结点*p2插入顶点vj的边表头部
    }
    return OK;
}

邻接表的特点

  1. 方便找任一顶点的所有“邻接点”

  2. 节约稀疏图的空间:需要N个头指针 + 2E个结点(每个结点至少2个域)

  3. 方便计算任一顶点的“度”, 对无向图:是的 ;对有向图:只能计算”出度”; 需要构造“逆邻接表”(存指向自己的边)来方便计算度

  4. 不方便检查任意一对顶点间是否存在边

3.案例引入——六度空间理论

“六度空间”理论又称作六度分隔(Six Degrees of Separation)理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过六个人你就能够认识任何一个陌生人。”该理论产生于20世纪60年代,由美国心理学家米尔格兰姆提出。

六度空间理论验证

但是米尔格兰姆的理论从来没有得到过严谨的证明,虽然屡屡应验,虽然很多社会学家一直都对其兴趣浓厚,但它只是一种假说。现在,许多科学家对此进行研究,它们都不约而同地使用了网络时代的新型通讯手段对“小世界现象”进行验证。

把六度空间理论中的人际关系网络抽象成一个无向图G。用图G中的一个顶点表示一个人,两个人认识与否用代表这两个人的顶点之间是否有一条边来表示。从任一顶点出发用广度优先方法对图进行遍历,统计所有路径长度不超过7的顶点。

算法实现

  1. 将输入的关系建立成一个二维数组relation[人数] [人数],其中第i行第j列为1则代表i与j有关系

  2. 用一个数组visit[人数]记录第i个人是否已经访问

  3. 用一个数组queue[人数]记录需要遍历其广度的人的队列

  4. 从编号为1的人开始,记录下他的一层所有关系的广度,每遍历到一个人,如果这个人对应的visit数组中为0,则代表这个人还未访问过,将这个遍历到的人入queue数组,再将对应的visit中的数值改为1,如果到了relation数组第n维的最后一个人,用tail记录下这个人的编号,代表着此层的最后一个人。

  5. 遍历queue数组的人的关系,当在queue中遍历到此tail编号的人的广度时,层数加1

  6. 当层数为6时,停止该人的遍历,转到下个编号的人的遍历

C语言代码

#include<stdio.h>
#include<malloc.h>
#define MAX 1001
​
int count(int num, int N, int ** relation)
{
    //对第num个人进行六度空间内有关联的人的计数
    int queue[MAX];//queue数组模拟一个队列,记录需要遍历其关系的人(需要遍历第num个人认识的人)
    int front = -1,rear = -1;//fornt和rear模拟头指针,分别queue的队列头和尾
    int sum = 1;//记录所有在六度内认识的人。
    int level = 0;//记录当前的层数,便于按层遍历,当层数为6,退出
    int levellast = num;//记录每一层最后一个人的编号,当遍历到这个编号时,层次加1
    int visit[MAX] = {0};//记录对每个人是否已经访问过的情况,防止出现重复遍历,初始状态为全部没有遍历
    int last;
    visit[num] = 1;
    queue[++rear] = num;//参数num为queue第一个元素,是第一个需要遍历其关系的人
    while(front < rear)
    {
        //对待遍历队列进行遍历
        int t = queue[++front];//t为第一个需要遍历其关系的人
        for(int i = 1;i <= N; i++)
        {
            //开始遍历该人的关系(即数组的第二维)
            if(!visit[i] && relation[t][i] == 1)
            {
                //如果第num个人和第i个人有关系且i尚未访问
                queue[++rear] = i;//将该第i个人记录进入待访问数组,在下层进行访问
                visit[i] = 1;//将该点记录已经访问
                sum += 1;//认识的总人数+1
                last = i;//记录当下层为最后一个结点
            }
        }
        
        if(t == levellast)
        {
            //如果已经到了一层的最后一个结点
            level += 1;//层数+1
            levellast = last;
        }
        if(level == 6) break;
    }
    return sum;//返回总人数
}
​
int main(void)
{
    int num1, num2;//人数、关系数
    printf("请输入人数:");
    scanf("%d",&num1);//输入人数
    printf("请输入关系数:");
    scanf("%d",&num2);//输入关系数
    int **relation;//二维数组,记录两人之间的关系矩阵
    relation = (int**)malloc(sizeof(int*)*(num1 + 1));//分配空间
    for(int i = 0;i <= num1; i++)
    {
        //分配空间
        *(relation + i) = (int*)malloc(sizeof(int)*(num1 + 1));
    }
    
    for(int i = 0;i <= num2 - 1; i++)
    {
        //记录一个关系的两端结点
        int x,y;
        scanf("%d",&x);
        scanf("%d",&y);
        relation[x][y] = relation[y][x] = 1;//无向图的关系矩阵一定是对称的
    }//关系录入完成
​
    for(int i = 1;i <= num1; i++)
    {
        //循环输出每个人的六度空间内的认识人的比
        printf("%d:%.2f%%\n",i,((float)count(i, num1, relation)/num1)*100);
    }
}

4.遍历定义

从已给的连通图中某一顶点出发,沿着一生边访遍图中所有的顶点,且使每个顶点仅被访问一次,就叫做图的遍历,它是图的基本运算

图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问 

 遍历实质:找每个顶点的邻接点的过程。

图的特点

图中可能存在回路,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。

图常用的遍历

深度优先搜索(Depth_First Search——DFS)

广度优先搜索(Breadth_Frist Search——BFS)

5.深度优先遍历(DFS)

方法

  1. 在访问图中某一起始顶点v后,由y出发,访问它的任一邻接顶点w1

  2. 再从w1出发,访问与w1邻接但还未被访问过的顶点w2

  3. 然后再从w2出发,进行类似的访问,…

  4. 如此进行下去直至到达所有的邻接顶点都被访问过的顶点u为止。

  5. 接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。

  6. 如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;

  7. 如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。

例如

图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问 

 深度优先搜索遍历算法的实现

邻接矩阵表示的无向图深度遍历实现:

图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问 

 通过邻接矩阵进行遍历,然后再通过辅助数组进行记录,如果遍历发现没法往下寻找结点,那么就逐步后退倒上一节点处在进行遍历,直至找到整个图中所有节点。

代码

void DFS(AMGraph G, int v)
{
    //图G为邻接矩阵类型
    cout << v;//访问第v个顶点
    visited[v] = true;//记录该结点
    for(w = 0;w < G.vexnum; w++)
    {
        //依次检查邻接矩阵v所在的行
        if((G.arcs[v][w] != 0)&&(!visited[w]))
            DFS(G,w);
        //w是v的邻接点,如果w未访问,则递归调用DFS
    }
}

DFS算法效率分析

用邻接矩阵来表示图,遍历图中每一个顶点都要从头扫描该顶点所在的行,时间复杂度为O(n^2)

用邻接表来表示图,虽然有2e个表结点,但只需扫描e个结点即可完成遍历,加上访问n个头结点的时间,时间复杂度为O(n+e)。

结论:

稠密图适行在邻接矩阵上进行深度遍历;

稀疏图通于在邻接表上进行深度遍历。

5.广度优先搜索(BFS)

层层遍历,不再是一条路走完的形式。

方法:从图的某一结点出发,首先依次访问该结点的所有邻接点Vi1, Vi2,....,Vin,再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点,重复此过程,直至所有顶点均被访问为止。

图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问 

 通过队列的算法和辅助数组,对图进行广度优先遍历

按广度优先非递归遍历连通图G

void BFS(Graph G, int v)
{
    //按广度优先非递归遍历连通图G
    cout << v;
    visited[v] = true;//访问第v个顶点
    InitQueue(Q);//辅助队列Q初始化,置空
    EnQueue(Q, v);//v进队
    while(!QueueEmpty(Q))
    {
        //队列非空
        DeQueue(Q, u);//队头元素出队并置为u
        for(w = FirstAdjVex(G, u);w >= 0;w = NextAdjVex(G, u, w))
        {
            if(!visited[w])
            {
                //w为u的尚未访问的邻接顶点
                cout << w;
                visited[w] = true;
                EnQueue(Q, w);//w进队
            }
        }
    }
}

BFS算法效率分析

如果使用邻接矩阵,则BFS对于每一个被访问到的顶点,都要循环检测矩阵中的整整一行(n个元素),总的时间代价为O(n^2)。

用邻接表来表示图,虽然有2个表结点,但只需扫描e个结点即可完成遍历,加上访问n个头结点的时间,时间复杂度为O(n+e)。

DFS与BFS算法效率比较

  1. 空间复杂度相同,都是O(n)(借用堆栈或队列)

  2. 时间复杂度只与存储结构,(邻接矩阵或邻接表)有关。文章来源地址https://www.toymoban.com/news/detail-421382.html

到了这里,关于图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——图的基本定义以及图的存储结构,邻接矩阵,邻接表

    目录 图的定义和术语 图的存储结构 顺序存储结构—邻接矩阵 链式存储结构 邻接表 邻接多重表 十字链表 图的遍历 图的连通性问题 有向无环图及其应用 最短路径 图的定义:图是一种非线性的复杂的数据结构,图中的数据元素的关系是多对多的关系 ,在图中我们常常把数

    2024年02月04日
    浏览(58)
  • 【数据结构】图的基本操作

    一、问题描述 分别以邻接矩阵和邻接表作为存储结构,实现以下图的基本操作: 增加一个新结点v,Insert(G,v); 删除顶点v及其相关的边,Delete(G,v); 增加一条边v,w,Insert(G,v,w); 删除一条边v,w,Delete(G,v,w); 二、设计思路 1、邻接矩阵实现:         邻接矩阵实现图的基本

    2024年02月06日
    浏览(50)
  • 数据结构--图的基本操作

    使用的存储模式: 图的基本操作: • Adjacent(G,x,y):判断图G是否存在边x, y或(x, y)。 • Neighbors(G,x):列出图G中与结点x邻接的边。 • InsertVertex(G,x):在图G中插入顶点x。 • DeleteVertex(G,x):从图G中删除顶点x。 • AddEdge(G,x,y):若无向边(x, y)或有向边x, y不存在,则向图G中添加该

    2024年02月16日
    浏览(53)
  • 数据结构入门(C语言版)图的概念和功能函数实现

    图是一种比线性表和树更复杂的数据结构。在线性表中,数据元素之间仅有 线性关系每个元素 只有 一个直接前驱 和 一个直接后继 。在树形结构中,数据元素之间存在明显的层次关系,并且每层的元素可能和下一层的多个元素(即其孩子结点)相邻,但只能和上一层的个元素(即其

    2024年02月06日
    浏览(51)
  • 【数据结构】一、数据结构的基本概念

    数据是 信息的载体 ,是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序 识别 和 处理 的符号的集合。 数据是计算机程序加工的原料。 数据元素 是数据的基本单位。通常作为一个整体进行考虑和处理,用一个 数据元素 描述一个个体。一个数据元素可

    2024年03月10日
    浏览(89)
  • 【数据结构与算法】一、数据结构的基本概念

    抽象数据类型(ADT)定义举例:Circle的定义 如何处理杂乱无章且多样化的数据: 数据元素 :数据中的个体被称为数据元素。 数据对象 :性质相同的数据元素组成的集合。 数据结构 :数据元素加上数据元素之间的关系,就形成了数据结构。 逻辑结构 :数据结构的逻辑模型。

    2023年04月17日
    浏览(99)
  • 数据结构基本概念

    一、数据 数据对象-数据元素-数据项(属性),前者由后者组成 二、数据结构 定义:按某种关系的数据元素的集合 三、数据类型 1、原子类型(例如整型) 2、结构类型(由原子类型组成,例如数组) 3、抽象数据类型(例如Java里面的类)

    2024年02月09日
    浏览(45)
  • 数据结构--队列的基本概念

    队列其实是一种受限制的线性表 队列(Queue):是 只允许在一端进行插入或删除操作 color{red}只允许在一端进行插入或删除操作 只允许在一端进行插入或删除操作 的线性表 重要术语: 队头、队尾、空队列 队列的特点: 先进先出 color{green}先进先出 先进先出 First In First Out ( F l

    2024年02月11日
    浏览(47)
  • 数据结构 - 基本概念和术语

    基础概念之间的关系大致如下: 数据 数据对象 数据元素 数据项 类比数据库,这四个概念代表的含义如下所示: 数据:整个数据库的所有数据 数据对象:这个数据库的一张表,比如学籍表 数据元素:学籍表里的一条记录 数据项:学籍表里的一个字段值 概念:能输入计算机

    2024年02月11日
    浏览(49)
  • 数据结构 -作用及基本概念

    学习数据结构是计算机科学和软件工程领域中非常重要的一门课程。以下是学习数据结构的几个重要原因: 组织和管理数据 :数据结构提供了一种组织和管理数据的方式。通过学习不同的数据结构,你可以了解如何有效地存储和操作数据,以提高程序的运行效率和性能。 解

    2024年02月09日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包