• 【数据结构】图形结构——图的概念

    图是比线性表和树更为复杂的数据结构。在线性表中，每个数据元素至多只有一个直接前驱和一个直接后继。在树中，各个节点都处在一定的层次上，并且每一层上的结点可以和其下一层中的多个结点相关联。所以可以把图看作是线性表和树的推广，也就是说线性表和树实际上都是一种特殊的图。图结构可以描述各种复杂的数据结构，在计算机科学、信息、控制、运筹学、通信网络、工程等许多领域都有着广泛的应用，如通信线路、交通航线、工序进度计划等。

    目录

    一、图的概念 

    1. 图的定义

    2. 基本术语

    二、图的表示与实现 

    1. 邻接矩阵 

    2. 邻接表 

    三、图的遍历 

    1. 深度优先搜索遍历

    1.1 邻接矩阵

    1.2 邻接表 

    2. 广度优先搜索遍历

    附：系列文章

    一、图的概念 

    1. 图的定义

    ① 图G是由两个集合V和E组成的，记为G=(V,E)。其中，V是图G中数据元素的非空有穷集合，这些数据元素称为顶点；E是图G的V中顶点偶对的有限集合，这些顶点偶对称为边。在图G中，E集可以是为空，若E为空，则图G中只有顶点没有边。

    ② 若图中边是有方向的，称此图为有向图，用尖括号括起来的顶点偶对表示，并称为弧或有向边。若图中的边是无方向的，称此图为无向图，用括号括起的顶点偶对表示，通常称为边。

    2. 基本术语

    ① 通常，在图中用n表示顶点的数目，e表示边或弧的数目。在n个顶点的无向图G中，e的取值范围是0~n(n-1)/2，若图G中有n(n-1)/2条边则称该无向图为无向完全图。在有n个顶点的有向图G中，e的取值范围是0~n(n-1)，若图G中有n(n-1)条边则称该有向图为有向完全图。

    ② 有时图的边或弧附有相关的数值，这种数值称为权。这些权可以表示一个顶点到另一个顶点的距离或时间耗费、开销等。每条边或弧都带权的图称为网。

    ③ 无向图中，若顶点x与y之间有边(x,y)，则x,y互为邻接点，边(x,y)与顶点x和y相关联。无向图中顶点x的度是与x相关联的边的数目，记为TD(x)。有向图中，若是一条弧，则称顶点v邻接到顶点w，顶点w邻接自顶点v。有向图中顶点v的入度是以顶点v为终点的弧的数目，记为ID(v)，顶点v的出度是以顶点v为始点的弧的数目，记为OD(v)，顶点v的度记为TD(v)=ID(v)+OD(v)。

    ④ 路径序列中顶点不重复出现的路径称为简单路径。路径中第一个顶点和最后一个顶点相同的路径称为回路或环。简单路径中第一个顶点和最后一个顶点相同的路径称为简单回路。

    ⑤ 在无向图中，如果顶点x到顶点y有路径，则称x和y是连通的。如果无向图中任意两个顶点都是连通的，则称该无向图为连通图；在有向图中，如果顶点v到顶点w之间存在路径，顶点w到顶点v之间也存在路径，则称v和w是强连通的。如果有向图中任意两个顶点都是强连通的，则称该有向图为强连通图。

    ⑥ 非连通图含有连通分量，即该图中的极大连通子图；非强连通图含有强连通分量，即该图中的极大强连通子图。

    ⑦ 一个连通图的生成树，是含有该连通图全部顶点的一个极小连通子图。若连通图G的顶点个数为n，则G的生成树的顶点个数也为n，边数为n-1，边数多于n-1就不是极小连通子图，少于n-1则不连通了。但是有n个顶点，n-1条边的图并不一定都是生成树。

    ⑧ 设G=(V,E)是一个图，G'=(V',E')也是一个图，如果V'是V的子集，E'是E的子集，且E'中的边仅与V'中的顶点相关联，则称G'为G的子图。

    二、图的表示与实现 

    图的结构比较复杂，表示图的存储结构有多种形式。常用图的存储结构有邻接矩阵、邻接表、十字链表、邻接多重表等方法。在实际应用中，应根据具体的图和需要进行的操作，设计适合的存储结构。

    1. 邻接矩阵 

    （1）邻接矩阵是表示顶点之间相邻关系的矩阵。

    设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是有如下性质的n阶矩阵：

    A[i,j]=1，若(Vi,Vj)或是E(G)中的边

    A[i,j]=0，若(Vi,Vj)或不是E(G)中的边 

    （2）以二维数组表示有n个顶点的图时，需存放n个顶点信息和n^2个边或弧信息的存储量。

    若考虑无向图邻接矩阵的对称性，则可采用压缩存储方式只存入矩阵的下三角（或上三角）元素。显然，邻接矩阵表示法的空间复杂度S(n)=O(n^2)。

    图的邻接矩阵存储结构定义如下：

    1. #define N 20
    2. typedef struct{
    3.     int vexnum,arcnum;    //图的顶点数，边数 
    4.     VexType vexs[N];      //图的顶点 
    5.     int arcs[N][N];       //图的邻接矩阵 
    6. }MGraph;   

    （3）从图的邻接矩阵表示法中，计算每个顶点的度非常方便。

    在无向图中每个顶点的度数就等于邻接矩阵中与该顶点相应行或列中非零元素的个数。在有向图中，顶点的出度是邻接矩阵中与该顶点对应行的非零元素的个数，顶点的入度是邻接矩阵中与该顶点对应列的非零元素的个数。 

    （4）创建一个以邻接矩阵为存储表示的图的基本步骤：

    ① 输入顶点数和边数

    ② 输入顶点信息

    ③ 输入边的信息 

    （5）创建图邻接矩阵的算法

    1. void CreateMGraph(MGraph *g){
    2.     int i,j;
    3.     char v;
    4.     scanf("%d %d",&g->vexnum,&g->arcnum);
    5.     getchar();
    6.     i=0;
    7.     for(i=0;ivexnum;i++){     //输入顶点信息 
    8.         v=getchar();
    9.         g->vexs[i]=v;
    10.     }
    11.     for(i=0;ivexnum;i++){       //邻接矩阵初始化 
    12.         for(j=0;jvexnum;j++){
    13.             g->arcs[i][j]=0;
    14.         }
    15.     }
    16.     for(i=0;iarcnum;i++){      //输入边的信息 
    17.         scanf("%d,%d",&i,&j);
    18.         g->arcs[i][j]=1;
    19.     }
    20. }

    2. 邻接表 

    （1）邻接表是图的一种顺序存储和链式存储相结合的存储结构。

    在邻接表中，对图中的每一个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对于有向图是以顶点Vi为尾的弧）。顶点Vi存储在表头结点中，以顺序存储结构存储所有顶点信息。采用邻接表存储图以便于随机访问任一顶点及其链表。 

    （2）图的邻接表表示法采用两种不同的顶点结构；顶点表结点和链表结点。

    顶点表结点由两个域组成，其中顶点域vertex存储顶点信息；next域指向该顶点的单链表。链表结点由两个域组成，其中邻接点域adjvex存储邻接点在顶点中的序号；next域指向下一个邻接边。 

    （3）在无向图的邻接表中，顶点Vi的度即为第i个链表中的结点数；在有向图中，第i个链表中的结点数为顶点Vi的出度

    为求顶点Vi的入度，必须遍历整个邻接表，即所有链表中其邻接点域的值为i的结点个数是顶点Vi的入度。为了便于确定顶点的入度或以顶点Vi为头的弧，可以建立一个有向图的逆邻接表，即对每个顶点Vi建立一个链表以Vi为弧头的表。 

    （4）对于有向图，也可以在顶点表结点中增加一个入度域in，存储该顶点的入度。

    这样的存储结构对于有向图的邻接表可以方便获得顶点的入度，其缺点是当图中的弧发生变化时，相应的入度也必须修改。 

    （5）图的邻接表存储结构定义：

    1. typedef struct EdgeNode{        //邻接链表结点 
    2.     int adjvex;                 //顶点序号 
    3.     struct EdgeNode * next;     //指向下一个结点 
    4. }EdgeNode;
    5. typedef struct VNode{           //顶点表结点 
    6.     VexType data;               //顶点信息 
    7.     int in;                     //有向图的顶点入度或无向图顶点度 
    8.     struct EdgeNode *link;      //指向邻接链表指针 
    9. }VNode;
    10. typedef struct ALgraph{         //图的邻接表 
    11.     int vexnum,arcnum;          //顶点数，弧数 
    12.     VNode adjlist[N];
    13. }ALGraph; 

    （6）邻接表的建立需要根据输入的边的信息创建邻接链表

    邻接链表的建立和单链表的建立过程基本类似，采用前插法将边的顶点直接插入表结点后。

    下面以有向图为例给出图的邻接链表创建算法：

    1. void CreateALGraph(ALGraph *g){
    2.     int i,j;
    3.     char v;
    4.     EdgeNode *s;
    5.     i=0;
    6.     scanf("%d,%d",&g->vexnum,&g->arcnum);     //输入顶点数和边弧数 
    7.     getchar();                      
    8.     for(i=0;ivexnum;i++){                 
    9.         v=getchar();                          
    10.         g->adjlist[i].data=v;                 //读入顶点信息 
    11.         g->adjlist[i].in=0;                   //初始化入度为0 
    12.         g->adjlist[i].link=NULL;              //初始化指向顶点邻接链表指针为空 
    13.     }
    14.     for(i=0;ivexnum;i++){                
    15.         scanf("%d,%d",&i,&j);
    16.         s=(EdgeNode *)malloc(sizeof(EdgeNode));    //创建邻接链表表结点 
    17.         s->adjvex=j;                     
    18.         s->next=g->adjlist[i].link;             //结点插入i相应单链表 
    19.         g->adjlist[i].link=s;               
    20.         g->adjlist[j].in++;                     //顶点j的入度加1 
    21.     }
    22. } 

    三、图的遍历 

    图的遍历是从某个顶点出发，对图中所有顶点仅访问一次。若给定的图是连通的，则从图的任一顶点出发沿着边可以访问到该图的所有顶点。然而，图的遍历比树的遍历复杂很多，这是因为图中的任一顶点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能沿着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个顶点是否被访问过。

    1. 深度优先搜索遍历

    （1）深度优先搜索遍历类似树的先根遍历。假设给定图G初态是所有顶点均未曾访问过，在图中任选一个顶点Vi为初始出发点，则深度优先搜索可定义为，首先访问出发点Vi，从Vi的每一个未被访问过的邻接点出发，深度优先搜索图G，直至图G中所有与Vi相通的顶点都被访问过，若图中还有未被访问的顶点，选择一个未被访问的顶点作为出发点，继续深度优先搜索。

    （2）图的深度优先搜索是一个递归的过程。对于一个连通的图来说，从任一个顶点出发，执行一次深度优先搜索可以遍历图中所有顶点；而对于非连通的图来说，需要进行多次深度优先搜索才可以遍历图中所有顶点。

    （3）遍历过程中，为了区分顶点是否被访问过，需要设置一个访问标志数组visit[]，若顶点i未被访问，则visit[i]为0，否则visit[i]为1。

    1.1 邻接矩阵

    1. int visit[N];                     //定义辅助数组记录顶点的访问状态 
    2. void DFS(int i,MGraph *g){
    3.     int j;
    4.     printf("%c",g->vexs[i]);
    5.     visit[i]=1;
    6.     for(j=0;jvexnum;j++)
    7.         if((g->arcs[i][j]==1)&&(!visit[j]))
    8.             DFS(j,g);
    9. } 
    10. void TDFS(MGraph *g){            //深度优先遍历整个图算法 
    11.     int i;
    12.     for(i=0;ivexnum;i++)
    13.         if(visit[i]!=1)
    14.             DFS(i,g);
    15. }

    1.2 邻接表 

    1. void DFSL(int i,ALGraph *g){
    2.     int j;
    3.     EdgeNode *p;
    4.     printf("%c",g->adjlist[i].data);
    5.     visit[i]=1;
    6.     p=g->adjlist[i].link;
    7.     while(p){
    8.         j=p->adjvex;
    9.         if((!visit[j])){
    10.             DFSL(j,g);
    11.         }
    12.         p=p->next;
    13.     }
    14. }
    15. void TDFSL(ALGraph *g){
    16.     int i;
    17.     for(i=0;ivexnum;i++){
    18.         if(visit[i]==0){
    19.             DFSL(i,g);
    20.         }
    21.     }
    22. }

    2. 广度优先搜索遍历

    （1）广度优先搜索遍历类似于树的按层次遍历。设图G的初始状态是所有顶点均未访问过，在G中任选一顶点Vi为初始出发点，则广度优先搜索的基本思想是，首先访问出发点Vi，接着依次访问Vi的所有邻接点W1,W2,W3,…,Wt；然后，再依次访问与W1,W2,…,Wt邻接的所有未曾访问的顶点，直至图G中所有与Vi相通的顶点都被访问；若图中还有未被访问的顶点，选择一个未被访问的顶点作为出发点，继续广度优先搜索

    （2）广度搜索过程是一种基于层次遍历的搜索过程，类似于二叉树的层次遍历，以某个顶点为出发点，访问其所有未被访问邻接点，下一步的搜索是以刚刚被访问过的顶点为出发点继续广度搜索，而上一层刚被访问的顶点可能不止一个，需要暂存这些顶点，且下次访问要保证这些顶点的先后访问次序，因此广度优先搜索需要借助队列来暂存那些刚被访问过的顶点。广度优先搜索不需要回溯，不是递归过程。

    广度优先遍历算法如下：

    1. int visited[N];
    2. void BFS(int k,MGraph *g){
    3.     int i,j;
    4.     SqQueue qlist,*q;
    5.     q=&qlist;
    6.     q->rear=0;
    7.     q->front=0;
    8.     printf("%c",g->vexs[k]);
    9.     visited[k]=1;
    10.     q->data[q->rear]=k;
    11.     q->rear=(q->rear+1)%MAX;
    12.     while(q->rear!=q->front){
    13.         i=q->data[q->front];
    14.         q->front=(q->front+1)%MAX;
    15.         for(j=0;jarcnum;j++){
    16.             if((g->arcs[i][j]==1)&&(!visited[j])){
    17.                 printf("%c",g->vexs[j]);
    18.                 visited[j]=1;
    19.                 q->data[q->rear]=j;
    20.                 q->rear=(q->rear+1)%MAX;
    21.             }
    22.         }
    23.     }
    24. } 
    25. void TBFS(MGraph *g){
    26.     int i;
    27.     for(i=0;ivexnum;i++){
    28.         if(visited[i]!=1){
    29.             BFS(i,g);
    30.         }
    31.     }
    32. }

    附：系列文章

    序号文章目录直达链接
    1栈https://want595.blog.csdn.net/article/details/127154749
    2队列https://want595.blog.csdn.net/article/details/127816577
    3串https://want595.blog.csdn.net/article/details/128784134
    4数组https://want595.blog.csdn.net/article/details/127380551
    5广义表https://want595.blog.csdn.net/article/details/127395781
    6树https://want595.blog.csdn.net/article/details/127454209
    7图https://want595.blog.csdn.net/article/details/127901532
    8查找https://want595.blog.csdn.net/article/details/128769694
    9排序https://want595.blog.csdn.net/article/details/128156174

     

  • 相关阅读:
    数据集处理方法之数据增强
    开源视频监控服务器Shinobi
    含文档+PPT+源码等]精品基于SSM的社区疫情防控平台[包运行成功]计算机毕设Java项目源码程序设计
    PostCSS的使用
    一探究竟：为什么需要 JVM？它处在什么位置？
    移动app测试的7个关键点，建议收藏
    Java设计模式
    【科研工具的使用】A
    网课答案公众号零基础怎么制作（内含详细教程）
    包管理器
  • 原文地址：https://blog.csdn.net/m0_68111267/article/details/127901532