Sillywa's Blog
0%

图的结构及遍历

发表于 更新于 分类于

图的基本概念

在树型结构中，结点间具有分支层次关系，每一层上的结点只能和上一层中的至多一个结点相关，但可能和下一层的多个节点相关。树的关系也叫一对多的关系，而在图状结构中，任意两个结点之间都可能相关，即结点的邻接关系可以是任意的。图的结构是任意两个数据对象之间都可能存在某种特定关系的数据结构，是一种多对多的关系。

图的定义和术语

图（Graph）是由两个集合构成，一个是非空但有限的顶点集合 V，另一个是描述顶点之间关系——边的集合 E（可以是空集）。因此图可以表示为 G=(V,E)。每条边是一顶点对 (v,w) 且 v,w∈V。通常用 |V| 表示定点数量 |E| 表示边的数量。

关于图的定义，与以前的线性表和树比较，还有几点需要注意：

  • 在线性表中，一般叫数据对象为元素；在树中，将数据对象成为结点；而在图中，我们把数据对象称为顶点（Vertex）。

  • 线性表中可以没有数据对象，此时叫空表；没有数据对象的树称为空树；而在图中，我们至少要求有一个顶点，但边集可以是空。

图的抽象数据类型

类型名称：图（Graph）。

数据对象集：一个非空顶点集合 Vertex 和一个边集合 Edge，每条边用对应的一对顶点表示。

操作集：对于任意的图 G∈Graph，顶点 V∈Vertex，边 E∈Edge，以及任一访问顶点的函数 Visit()，我们主要关心下列操作：

1.Graph CreateGraph(int VertexNum)：构造一个有 VertexNum 个顶点但没有边的图；

2.void InsertEdge(Graph G, Edge E)：在 G 中增加新边 E；

3.void DeleteEdge(Graph G, Edge E)：从 G 中删除边 E；

4.bool IsEmpty(Graph G)：判断图是否为空；

5.void DFS(Graph G, Vertex V, (*Visit)(Vertex))：在图 G 中，从顶点 V 出发进行深度优先遍历；

6.void BFS(Graph G, Vertex V, (*Visit)(Vertex))：在图 G 中，从顶点 V 出发进行广度优先遍历。

图的存储结构

邻接矩阵

所谓邻接矩阵的存储结构，就是用矩阵表示图中各顶点之间的邻接关系和权值。以下是一个无向图的临界矩阵表示：

从图的邻接矩阵存储方法容易看出这种表示具有以下特点:

1.无向图的邻接矩阵一定是个对称矩阵。因此在具体存放邻接矩阵时只需要存放上三角或者下三角的元素即可。所需要存储的元素个数是：|V|*(|V|-1)/2。

2.对于无向图，邻接矩阵的第 i 行（或第 i 列）非 0 元素的个数正好是第 i 个顶点的度（Degree）。

3.对于有向图，邻接矩阵第 i 行（或第 i 列）非 0 元素的个数正好是第 i 个顶点的出度（或入度）。

4.用临界矩阵方法存储图，很容易确定图中任意两点之间是否有边相连，只需要考察邻接矩阵对应的元素即可；确定一个顶点的所有邻接点，也只需要邻接矩阵对应的一行（或一列）；但是要确定图中有多少边，则必须按行（或按列）对每个元素进行检测，所花费的时间代价是 O(|V|^2)。这是用邻接矩阵来存储图的局限性。

以下是邻接矩阵的 C 语言描述：

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
#define MaxVertexNum 100    /* 最大顶点数 */
#define INFINITY 65535      /* 初始值设为双字节无符号整数的最大值 */
typedef int Vertex;         /* 用顶点下标表示顶点，为整形 */
typedef int WeightType;     /* 边的权值 */
typedef char DataType;            /* 顶点存储的数据类型设为字符型 */


/* 图的定义 */
struct GNode {
    int Nv;     /* 顶点数 */
    int Ne;     /* 边数 */
    WeightType G[MaxVertexNum][MaxVertexNum];   /* 邻接矩阵 */
    DataType Data[MaxVertexNum];                /* 每个顶点的数据 */
};
typedef struct GNode* PtrToGNode;
typedef PtrToGNode MGraph;


/* 边的定义 */
struct ENode {
    Vertex V1, V2;      /* 有向边<V1,V2> */
    WeightType Weight;  /* 权重 */
};
typedef struct ENode* PtrToENode;
typedef PtrToENode Edge;

有了图的结构和类型定义之后，先创建一个包含全部顶点但是没有边的图，再逐条插入边，从而创建一个无向网图的数据结构。

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
51
52
53
54
55
56
57
58
59
MGraph CreateGraph(int VertexNum) {
    MGraph Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;

    /* 初始化邻接矩阵 */
    /* 注意顶点默认从 0 编号 到 Graph->Nv - 1 */
    for(int i = 0;i < Graph->Nv;i++) {
        for(int j = 0;j < Graph->Nv;j++) {
            Graph->G[i][j] = INFINITY;
        }
    }

    return Graph;

}
void InsertEdeg(MGraph Graph, Edge E) {

    /* 插入边<V1,V2> */
    Graph->G[E->V1][E->V2] = E->Weight;

    /* 如果是无向图,还需要插入边<V2,V1> */
    Graph->G[E->V2][E->V1] = E->Weight;

}
MGraph BuildGraph() {
    MGraph Graph;
    int VertexNum;

    /* 读入顶点数 */
    scanf("%d", &VertexNum);

    Graph = CreateGraph(VertexNum);

    /* 读入边数 */
    scanf("%d", &Graph->Ne);

    if(Graph->Ne != 0) {

        Edge E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */

        /*依次读入每一条边的数据 */
        for(int i = 0; i < Graph->Ne;i++) {

            scanf("%d %d %d",&E->V1, &E->V2, &E->Weight);

            /* 将该边插入图中 */
            InsertEdeg(Graph, E);

        }
    }
    /* 如果顶点有数据，读入顶点数据 */
    for(int i = 0;i < Graph->Nv;i++) {
        scanf("%c",&Graph->Data[i]);
    }

    return Graph;

}

邻接矩阵是一种表示各类图的简洁的数据结构。但是我们发现，不论图中边的数量或多或少，我们都花费了 O(|V|^2) 的存储空间，这对于稠密图来说是一种高效的存储方法。但是如果面对的是一个稀疏图，则邻接矩阵中的大多数项为 0 或 无穷，形成了所谓的稀疏矩阵，就会浪费很多空间。因此对于稀疏图，我们考虑另一种存储方法。

邻接表

邻接表是一种图的顺序存储与链式存储相结合的存储方法。

图的邻接表存储具有以下特点：

1.方便查找任一顶点的所有邻接点。

2.节约稀疏图的空间。需要 N 个头指针 + 2E 个结点（每个结点至少两个域）。

3.对于无向图来说方便计算任一顶点的度，对于有向图来说只能计算出度。

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

以下是图的邻接表存储的代码实现：

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#define MaxVertexNum 100    /* 最大顶点数设为100 */
typedef int Vertex;         /* 用顶点下标表示顶点，为整形 */
typedef int WeightType;     /* 边的权值设为整形 */
typedef char DataType;      /* 顶点存储的数据类型设为字符型 */

/* 边的定义 */
struct ENode {
    Vertex V1,V2;       /* 有向边<V1,V2> */
    WeightType Weight;  /* 权重 */
};
typedef struct ENode* Edge;

/* 邻接点的定义 */
typedef struct AdjVNode* PtrToAdjVNode;
struct AdjVNode {
    Vertex AdjV;            /* 邻接点的下标 */
    WeightType Weight;      /* 邻接点边的权重 */
    PtrToAdjVNode Next;     /* 下一个邻接点 */
};


/* 顶点表头节点的定义 */
typedef struct Vnode {
    PtrToAdjVNode FirstEdge;    /* 边表头节点指针 */
    DataType Data;              /* 头结点的值 */
    /* 很多情况下顶点无数据，此时Data不用出现 */
} AdjVList[MaxVertexNum];       /* AdjVList是邻接表的类型 */

/* 图的定义 */
typedef struct GNode* PtrToGNode;
struct GNode {
    int Nv;         /* 顶点数 */
    int Ne;         /* 边数 */
    AdjVList G;     /* 邻接表 */
};
typedef PtrToGNode LGraph;

/* 初始化一个有 VertexNum个顶点，但是没有边的图 */
LGraph CreateGraph(int VertexNum);

/* 将边<V1,V2>插入图中 */
void InsertEdge(LGraph Graph, Edge E);

/* 根据输入构建图 */
LGraph BuildGraph();

LGraph CreateGraph(int VertexNum) {
    LGraph Graph = (LGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;

    /* 初始化邻接表的表头指针 */
    /* 注意这里默认定点编号从 0 开始到 (Graph->Nv - 1) 结束 */
    for(int i = 0;i < Graph->Nv;i++) {
        Graph->G[i].FirstEdge = NULL;
    }

    return Graph;

}
void InsertEdge(LGraph Graph, Edge E) {
    /* 插入有向边 <V1,V2> */
    PtrToAdjVNode NewNode;

    /* 构建一个邻接点，并将该邻接点插入链表头部 */
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V2;
    NewNode->Weight = E->Weight;

    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;

    /* 如果是无向图还要插入<V2,V1> */
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V1;
    NewNode->Weight = E->Weight;

    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}
LGraph BuildGraph() {
    LGraph Graph;
    int VertexNum;

    /* 输入顶点数 */
    scanf("%d", &VertexNum);
    Graph = CreateGraph(VertexNum);

    /* 读入边数 */
    scanf("%d", &Graph->Ne);

    if(Graph->Ne != 0) {
        /* 构建边并读入 */
        Edge E = (Edge)malloc(sizeof(struct ENode));
        for(int i = 0;i < Graph->Ne;i++) {
            scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
            InsertEdge(Graph, E);
        }
    }

    /* 如果顶点有数据，读入数据 */
    for(int i = 0;i < Graph->Nv;i++)
        scanf("%c", &(Graph->G[i].Data));

    return Graph;
}

图的遍历

图的遍历就是从图中任一顶点出发，对图中所有顶点访问一次且仅访问一次的次序序列。

深度优先搜索（Depth First Search,DFS）

深度优先搜索类似于树的先序遍历，是树的先序遍历的推广。假设初始状态所有顶点都没被访问过，则深度优先搜索从图中的任一顶点出发，设为v0 ，访问此顶点，然后从v0的邻接点中的一个出发递归地进行同样的深度优先搜索，直至图中所有节点都被访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 邻接矩阵存储的图 */
void Visit(Vertex V) {
    printf("正在访问顶点 %d", V);
}
/* Visited[]已经为全局变量，且初始化为false */
void DFS(LGraph Graph, Vertex V, void (*Visit)(Vertex)) {

    Visit(V);           /* 访问第V个顶点 */
    Visited[V] = true;  /* 将V标记为已访问 */

    PtrToAdjVNode W;
    for(W = Graph->G[V].FirstEdge;W;W = W->Next) {  /* 对V的每个邻接点W */
        if(! Visited[W->AdjV]) {                    /* 如果W未被访问 */
            DFS(Graph, W->AdjV, Visit);             /* 则递归访问之 */
        }
    }
}

广度优先搜索（Breadth First Search,BFS）

广度优先搜索类似于树的层次遍历。从顶点v0出发，在访问了v0之后，依次访问v0各个未被访问的邻接点，然后分别从这些邻接点出发，访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。直至图中所有已被访问的顶点的邻接点都被访问到。

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
/* 邻接矩阵存储的图 */
void Visit(Vertex V) {
    printf("正在访问顶点 %d", V);
}
/* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边，即W是否V的邻接点。  */
/* 此函数根据图的不同类型要做不同的实现，关键取决于对不存在的边的表示方法。*/
/* 例如对有权图, 如果不存在的边被初始化为INFINITY, 则函数实现如下:         */
bool IsEdge(MGraph Graph, Vertex V, Vertex W) {
    return Graph->G[V][W] < INFINITY ? true : false;
}
/* Visited[]已经为全局变量，且初始化为false */
void BFS(MGraph Graph, Vertex S, void(* Visit)(Vertex)) {
    /* 以S为出发点对邻接矩阵存储的图进行BFS搜索 */
    Vertex V,W;

    /* 访问 S 顶点 */
    Visit(S);
    Visited[S] = true;

    Queue Q;
    Q = CreateQueue(MaxSize);           /* 创建一个空队列 */

    AddQ(Q, S);         /* 将S入队 */

    while(!IsEmpty(Q)) {
        V = DeleteQ(Q);  /* 弹出V */
        for(W = 0;W < Graph->Nv;W++) {              /* 对图中的每一个顶点 W */
            /* 如果W没有访问过且是V的邻接点 */
            if(!Visited[W] && IsEdge(Graph, V, W))
                /* 访问 W 顶点 */
                Visit(W);
                Visited[W] = true;  /* 将 W 标记为已访问 */
                AddQ(Q, W);         /* 将 W 入队列 */
        }
    }

}

若有 N 个顶点、E 条边，DFS 和 BFS 的时间复杂度为：

  • 用邻接表存储图，为 O(N+E);

  • 用邻接矩阵存储图，为 O(N^2)。