数据结构（六）-图

发表于 | 分类于 ，

1. 概述

  • 在图中，数据元素通常称作顶点
  • 有向图中，无箭头一端的顶点通常被称为”初始点”或”弧尾”，箭头直线的顶点被称为”终端点”或”弧头”
  • 对于有向图中的一个顶点 V 来说，箭头指向 V 的弧的数量为 V 的入度（InDegree，记为 ID(V)）；箭头远离 V 的弧的数量为 V 的出度（OutDegree，记为OD(V)）
  • 无论是无向图还是有向图，从一个顶点到另一顶点途径的所有顶点组成的序列（包含这两个顶点），称为一条路径。如果路径中第一个顶点和最后一个顶点相同，则此路径称为”回路”（或”环”）
  • 在某些实际场景中，图中的每条边（或弧）会赋予一个实数来表示一定的含义，这种与边（或弧）相匹配的实数被称为”权”，而带权的图通常称为网
  • 子图：指的是由图中一部分顶点和边构成的图，称为原图的子图
  • 图又可分为完全图，连通图、稀疏图和稠密图
    • 完全图：若图中各个顶点都与除自身外的其他顶点有关系，这样的无向图称为完全图。同时，满足此条件的有向图则称为有向完全图
    • 稀疏图和稠密图：这两种图是相对存在的，即如果图中具有很少的边（或弧），此图就称为”稀疏图”；反之，则称此图为”稠密图”
    • 图中从一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通着的；无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图
      • 有向图中，若任意两个顶点 Vi 和 Vj，满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就是都含有至少一条通路，则称此有向图为强连通图
      • 与此同时，若有向图本身不是强连通图，但其包含的最大连通子图具有强连通图的性质，则称该子图为强连通分量
  • 生成树
    • 对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树
    • 包含连通图中所有的顶点
    • 任意两顶点之间有且仅有一条通路
  • 生成森林
    • 生成树是对应连通图来说，而生成森林是对应非连通图来说的
    • 非连通图可分解为多个连通分量，而每个连通分量又各自对应多个生成树（至少是 1 棵），因此与整个非连通图相对应的，是由多棵生成树组成的生成森林

2. 图的顺序存储结构

  • 使用数组存储图时，需要使用两个数组，一个数组存放图中顶点本身的数据（一维数组），另外一个数组用于存储各顶点之间的关系（二维数组）

  • 代码实现

  • ArrayGraph.hpp

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
//
//  ArrayGraph.hpp
//  Graph
//

#ifndef ArrayGraph_hpp
#define ArrayGraph_hpp

#include <iostream>

#define MAX_VERTEX_NUM 20
#define VRType int
#define InfoType char
#define VertexType int

typedef enum {
    DG,
    DN,
    UDG,
    UDN
} GraphKind;

typedef struct {
    VRType adj;
    InfoType *info;
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {
    VertexType vexs[MAX_VERTEX_NUM];
    AdjMatrix arcs;
    int vexnum, arcnum;
    GraphKind kind;
} MGraph;

class ArrayGraph {
    
public:
    ArrayGraph();
    ~ArrayGraph();
    
    int LocateVex(MGraph *G, VertexType v);
    
    MGraph * CreateDG();
    
    MGraph * CreateDN();
    
private:
    MGraph *G {NULL};
    
};

#endif /* ArrayGraph_hpp */
  • ArrayGraph.cpp
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
//
//  ArrayGraph.cpp
//  Graph
//

#include "ArrayGraph.hpp"

ArrayGraph::ArrayGraph() {
    
}

ArrayGraph::~ArrayGraph() {
    
}

int ArrayGraph::LocateVex(MGraph *G, int v) {
    int i = 0;
    for (; i < G->vexnum; i ++) {
        if (G->vexs[i] == v) {
            break;
        }
    }
    if (i > G->vexnum) {
        printf("No vertex\n");
        return -1;
    }
    
    return i;
}

MGraph * ArrayGraph::CreateDG() {
    scanf("%d, %d", &(G->vexnum), &(G->arcnum));
    for (int i = 0; i < G->vexnum; i ++) {
        scanf("%d", &(G->vexs[i]));
    }
    for (int i = 0; i < G->vexnum; i ++) {
        for (int j = 0; j < G->arcnum; j ++) {
            G->arcs[i][j].adj = 0;
            G->arcs[i][j].info = NULL;
        }
    }
    for (int i = 0; i < G->arcnum; i ++) {
        int v1, v2;
        scanf("%d, %d", &v1, &v2);
        int n = LocateVex(G, v1);
        int m = LocateVex(G, v2);
        if (n == -1 || m == -1) {
            printf("No vertex\n");
            return G;
        }
        G->arcs[n][m].adj = 1;
    }
    return G;
}

MGraph * ArrayGraph::CreateDN() {
    scanf("%d, %d", &(G->vexnum), &(G->arcnum));
    for (int i = 0; i < G->vexnum; i ++) {
        scanf("%d", &(G->vexs[i]));
    }
    for (int i = 0; i < G->vexnum; i ++) {
        for (int j = 0; j < G->arcnum; j ++) {
            G->arcs[i][j].adj = 0;
            G->arcs[i][j].info = NULL;
        }
    }
    for (int i = 0; i < G->arcnum; i ++) {
        int v1, v2;
        scanf("%d, %d", &v1, &v2);
        int n = LocateVex(G, v1);
        int m = LocateVex(G, v2);
        if (n == -1 || m == -1) {
            printf("No vertex\n");
            return G;
        }
        G->arcs[n][m].adj = 1;
        G->arcs[m][n].adj = 1;
    }
    return G;
}