DSA之图（2）：图的存储结构

0 图的结构

多对多的结构，不能跟以前一样确定多少个数据域和指针域来进行表示。主要介绍邻接矩阵和邻接表。

在这里插入图片描述

1 邻接矩阵

在这里插入图片描述
尖括号表示有序的，有向图；圆括号表示无序的，无向图。有边的记作1，没有边的记为0。

1.1 无向图的邻接矩阵

在这里插入图片描述
特点：

对角线都是0，因为自身对自身没有边
无向图的邻接矩阵是对称的，两个顶点的边是相互的；但是并不能说有向图的邻接矩阵一定是不对称
度是与顶点相关联的边的个数，反映到图上来说，就是找1的个数，即：顶点 $i$ 的度 = 第 $i$ 行（列）中1的个数，即行（列）元素之和
完全图的邻接矩阵，对角线的元素为0，其余为1

1.2 有向图的邻接矩阵

有向图的邻接矩阵不一定是对称的，因为两个相连的顶点可能不是双向的。
在这里插入图片描述

第 $i$ 行，表示从 $v_i$ 个节点发出的弧，称之为出度。
第 $i$ 列，表示从 $v_i$ 个节点接收的弧，称之为入度。
顶点的出度=第 $i$ 行元素之和
顶点的入度=第 $i$ 列元素之和
顶点的度=第 $i$ 行元素之和+第 $i$ 列元素之和

1.3 网（有权图）的邻接矩阵表示法

在这里插入图片描述
相当于就是把权值代替成了普通的边。

以上就是网的邻接矩阵。

1.4 邻接矩阵的建立

#define MaxInt 32767 //表示无穷大
#define MVNum 100
typedef char VerTexType;//设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整型

typedef struct
{
    VerTextType vex[MVNum];//顶点表
    ArcType arcs[MVNum][MVNum];//邻接矩阵
    int vexnum, arcnum; //图的当前点数和边数
}AMGraph;
1
2
3
4
5
6
7
8
9
10
11

1.4.1 采用邻接矩阵建立无向网

在这里插入图片描述

#define MaxInt 32767 //表示无穷大
#define MVNum 100
typedef char VerTexType;//设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整型

typedef struct
{
    VerTextType vex[MVNum];//顶点表
    ArcType arcs[MVNum][MVNum];//邻接矩阵
    int vexnum, arcnum; //图的当前点数和边数
}AMGraph;//邻接矩阵表示的图

int LocateVex(AMGraph G, VertexType u)//查找顶点所在的位置
{
    int i;
    for (i = 0; i < G.vexnum; ++i)
    {
        if (u == G.vex[i])
        {
            return i;//找到元素在图当中的下标
        } 
    }
    return -1;
}

//构建无向网
Status CreateUDN(AMGraph &G)//G有四个成员，顶点表，边表，点数和边数
{
    cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
    for (i = 0; i < G.vexnum; ++i)
    {
        cin >> G.vex[i];//依次输入点的信息
    }
    for (i = 0; i < G.vexnum; ++i) //初始化邻接矩阵
    {
        for (j = 0; i < G.vexnum; ++j)
        {
            G.arcs[i][j] = MaxInt;//边的权值均初始化为最大值
        }
    }
    for (k = 0; k < G.arcnum; ++k)//构造邻接矩阵
    {
        cin >> v1 >> v2 >> w;//输入一条边所依附的顶点以及边的权值
        i = LocateVex(G, v1);//确定v1和v2在G中的位置
        j = LocateVex(G, v2);
        G.arcs[i][j] = w;//边的权值置为w
        G.arcs[j][i] = G.arcs[i][j];
    }//for
    return OK;
}//CreateUDN
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

1.4.2 采用邻接矩阵建立有向网

在这里插入图片描述
无需向邻接矩阵双向赋值，只需要赋值单边的就行。

1.5 邻接矩阵的优缺点

1.5.1 优点

在这里插入图片描述

1.5.2 缺点

在这里插入图片描述
时间复杂度只与顶点有关，与边数无关，时间复杂度为 $O(n^2)$ 。

2 邻接表

表示方法：

顶点：按编号顺序将顶点数据存储在一维数组中；
关联同一顶点的边（以顶点为尾的弧）：用线性链表存储

在这里插入图片描述

Tips：对于邻接表的表示方法，举个例子， $v_1$ 之后的是3，这个3对应的是表中的下标，也就是 $v_4$ ，不要直接认为3就是 $v_3$ 。

2.1 无向图的邻接表

在这里插入图片描述

边得双倍。怎么计算度？看到有几个表节点（紫色的点），就是有几个与其关联的边。所以，无向图中顶点 $v_i$ 的度为第 $i$ 个单链表中的结点数。

2.2 有向图的邻接表

在这里插入图片描述
特点：

顶点 $v_i$ 的出度为第 $i$ 个单链表中的结点个数。
顶点 $v_i$ 的入度为整个单链表中邻接点域值是 $i - 1$ 的结点个数。

综上，找出度容易，入度难。

在这里插入图片描述
还有一个逆邻接表表示，这样就是找入度容易，找出度难。

练习：已知某网的邻接(出边)表，请画出该网络。
在这里插入图片描述
当邻接表的存储结构形成后，图便唯一确定。

2.3 邻接表的建立

在这里插入图片描述

#define MVNum 100 //最大顶点数
typedef struct VNode
{
    VerTexType data; //顶点信息
    ArcNode * firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum]; //AdjList为邻接表

typedef struct ArcNode //边结点
{
    int adjvex; //该边所指向的顶点的位置
    struct ArcNode * nextarc; //指向下一条边的指针
    OtherInfo info; //和边相关的信息
}ArcNode;

typedef struct //图结构的定义
{
    AdjList vertices;//vertices -- vertex的复数
    int vexnum, arcnum; //图的当前顶点数与弧数
}ALGraph;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在这里插入图片描述
构建图G后，直接用成员变量进行赋值。

2.3.1 采用邻接表建立无向网

在这里插入图片描述

#define MVNum 100 //最大顶点数
typedef struct VNode
{
    VerTexType data; //顶点信息
    ArcNode * firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum]; //AdjList为邻接表

typedef struct ArcNode //边结点
{
    int adjvex; //该边所指向的顶点的位置
    struct ArcNode * nextarc; //指向下一条边的指针
    OtherInfo info; //和边相关的信息
}ArcNode;

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

//

Status CreateUDG(ALGraph &G) //采用邻接表表示法，创建无向图G
{
    cin >> G.vexnum >> G.arcnum; //输入总项点数，总边数
    for (i = 0; i < G.vexnum; ++i)//输入各点，构造表头结点表
    {
        cin >> G.vertices[i].data; //输入顶点值
        G.ertices[i].firstarc = NULL; //初始化表头结点的指针域
    }
    for (k = 0; k < G.arcnum; ++k) //输入各边，构造邻接表
    {
        cin >> v1 >> v2;    //输入一条边依附的两个顶点
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47