数据结构——图——图的定义

你的名字 2022-04-15 07:14 216阅读 0赞

### 1.图的定义 ###

图由顶点集V(G)和边集E(G)组成，记为G=(V,E)。其中E(G)是边的有限集合，边是顶点的**无序对**（无向图）或**有序对**（有向图）。

对有向图来说，E(G)是有向边（也称弧(Arc)）的有限集合，弧是顶点的有序对，记为<v,w>，v、w是顶点，**v为弧尾（箭头根部），w为弧头（箭头处）。**

对无向图来说，E(G)是边的有限集合，边是顶点的无序对，记为(v, w)或者(w, v)，并且(v, w)=(w,v)。

### 2.基本术语 ###

顶点(Vertex)：图中的数据元素。线性表中我们把数据元素叫元素，树中将数据元素叫结点。

顶点v的度：与v相关联的边的数目；

顶点v的出度：以v为**起点**有向边数；

顶点v的入度：以v为**终点**有向边数。

边：顶点之间的逻辑关系用边来表示，边集可以是空的。

无向边(Edge)：若顶点V1到V2之间的边没有方向，则称这条边为无向边。

无向图(Undirected graphs)：图中任意两个顶点之间的边都是无向边。（A,D）=（D,A）

有向边：若从顶点V1到V2的边有方向，则称这条边为有向边，也称弧(Arc)。用<V1,V2>表示，V1为狐尾(Tail)，V2为弧头(Head)。（V1，V2）≠（V2，V1）。

有向图(Directed graphs)：图中任意两个顶点之间的边都是有向边。

注意：无向边用“（）”，而有向边用“< >”表示。

简单图：图中不存在顶点到其自身的边，且同一条边不重复出现。

无向完全图：无向图中，任意两个顶点之间都存在边。

有向完全图：有向图中，任意两个顶点之间都存在方向互为相反的两条弧。

稀疏图：有很少条边。

稠密图：有很多条边。

权（Weight）：与图的边或弧相关的数。

网（Network）：带权的图。

子图（Subgraph）：假设G=（V,\{E\}）和G‘=（V',\{E'\}），如果V'包含于V且E'包含于E，则称G'为G的子图。

度（Degree）：无向图中，与顶点V相关联的边的数目。有向图中，入度表示指向自己的边的数目，出度表示指向其他边的数目，该顶点的度等于入度与出度的和。

**简单路径**：序列中顶点不重复出现的路径

**简单回路**：序列中第一个顶点和最后一个顶点相同的路径

路径的长度：一条路径上边或弧的数量。

连通图：图中任意两个顶点都是连通的。

极大连通子图：该子图是G连通子图，将G的任何不在该子图的顶点加入，子图将不再连通。

极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图都将不再连通。

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

有向图D的极大强连通子图称为D的强连通分量。

包含无向图G的所有顶点的极小连通子图称为G的生成树。

若T是G的生成树当且仅当T满足：T是G的连通子图、T包含G的所有顶点、T中无回路。

### 3.**图的存储结构** ###

**邻接矩阵：**

![20181122231921939.png][]

无向图的创建：

#define maxvexs 100
    #define infinity 10010
    typedef struct
    {
        char vexs[maxvexs];
        int arc[maxvexs][maxvexs];
        int vertexes,edges;
    }mgraph;
     
    void creatgraph(mgraph *g)
    {
        int i,j,k,w;
        printf("输入顶点数和边数:\n");
        scanf("%d,%d",&g->vertexes,&g->edges);
        for(i=0;i<g->vertexes;i++)//读入顶点信息，建立顶点表
            scanf("%c",&g->vexs[i]);
        for(i=0;i<g->vertexes;i++)
            for(j=0;j<g->vertexes;j++)
                g->arc[i][j]=infinity;//初始化邻接矩阵
        for(k=0;k<g->vertexes;k++)//读入edges条边，建立邻接矩阵
        {
            printf("输入边(Vi,vj)上的下标i，下标j,和权w:\n");
            scanf("%d%d%d",&i,&j,&w);
            g->arc[i][j]=w;
            g->arc[j][i]=w;//无向图，矩阵对称
        }
    }

邻接矩阵的好处：

直观、简单、好理解

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

方便找任一顶点的所有“邻接点”（有边直接相连的顶点）

方便计算任一顶点的“度”（从该点发出的边数为“出 度”，指向该点的边数为“入度”）

无向图：对应行（或列）非0元素的个数

有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”

邻接矩阵的缺点：

浪费空间——存稀疏图（点很多而边很少）有大量无效元素  
（对稠密图（特别是完全图）还是很合算的）

浪费时间——统计稀疏图中一共有多少条边

**邻接表：**数组与链表相结合的存储方法。

邻接表：数组 + 链表  
（1）用的数组存储每个节点  
（2）数组中的每个节点的所有邻接点组成一个链表(因为邻接点的个数不确定)。这个邻接表就是顶点的出度表  
（3）邻接表的图形表示

![2018112223304512.png][]

（4）邻接表关心了出度，但是查找入度就需要遍历整个图

![20181122233556735.png][]

结点定义

typedef struct EdgeNode
    {
        int adjvex; //邻接点域，存储该顶点对应的下标
        int weight; //用于存储权值，对于非网图可以不需要
        struct EdgeNode *next;  //链域，指向下一个邻接点
    }EdgeNode;//边表结点
     
    typedef struct VertexNode //顶点表结点
    {
        char data; //顶点域，存储顶点信息
        EdgeNode *firstedge; //边表头指针
    }VertexNode,AdjList[MAXVEX];
     
    typedef struct
    {
        AdjList adjList;
        int numVertexes,numEdges;//图中当前顶点数和边数
    }GraphAdjList;

应用：

[邻接矩阵存储图的深度优先遍历 ][Link 1]

[邻接表存储图的广度优先遍历 ][Link 2]

[20181122231921939.png]: /images/20220415/eb005c443e0c430ab2761308eb9d6ba4.png
[2018112223304512.png]: /images/20220415/f956e6a5ed3247fd9f49cf94bb51f7f7.png
[20181122233556735.png]: /images/20220415/fb641fbf1bb24fd8b8ed37c9164356c5.png
[Link 1]: https://blog.csdn.net/qq_42623428/article/details/83998955
[Link 2]: https://blog.csdn.net/qq_42623428/article/details/83999756