数据结构：图

敖炜 Lv5
  2023-11-21 09:06:09 2023-11-21 09:06:09 创建   2024-04-19 09:30:12 2024-04-19 09:30:12 更新      4.2k 字  20 分钟  

这一篇博客介绍图

图

图是一种非线性数据结构，由顶点和边组成，因此可以将图G抽象表示为一组顶点V和一组边E的集合

将顶点视作节点，边视作连接各个节点的引用(指针)，就可以将图看作是一种从链表扩展而来的数据结构

链表、树、图之间的关系

相较于线性关系(链表)和分治关系(树)，网络关系(图)的自由度更高，因此更复杂

图常见类型与术语

  1. 根据图中的边是否具有方向，可以分为无向图和有向图
  • 无向图中，边表示两顶点之间的双向连接关系，如微信或QQ中的好友关系
  • 有向图中，边具有方向性，即A->B和B->A是两条相互独立的、不同的边，如微博或抖音上的关注与被关注关系

有向图与无向图

  1. 根据所有顶点是否连通，可分为连通图和非连通图
  • 连通图：从某个顶点出发，可以到达其余任意顶点
  • 非连通图：从某个顶点出发，至少有一个顶点无法到达

连通图与非连通图

  1. 为边添加权重，得到有权图

有权图与无权图

  1. 常用术语

    • 邻接：两顶点之间通过边相连时，这两个顶点邻接
    • 从顶点A到顶点B所经过的边构成的序列称为从A到B的路径
    • 度：一个顶点拥有的边数。在有向图中，入度为入边数，出度为出边数

图的表示

图有两种常用表示方式，邻接矩阵和邻接表

  1. 邻接矩阵

对于顶点数为n的图，邻接矩阵用一个$nn$大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵中的元素代表*边

图的邻接矩阵表示

邻接矩阵的特性

  • 顶点不能与自身相连，故邻接矩阵主对角线元素没有意义
  • 对于无向图，两个方向的边等价，故邻接矩阵关于主对角线对称
  • 邻接矩阵中的元素可以表示权重

使用邻接矩阵表示图时，可以直接访问矩阵元素以获取边，因此增删查操作效率很高，时间复杂度均为。然而矩阵的空间复杂度为，内存占用较多

  1. 邻接表

使用n个链表来表示图，链表中的节点表示顶点。第i条链表对应顶点i，其中存储了第i个顶点的所有邻接顶点

图的邻接表表示

邻接表仅存储实际存在的边，而边的总数通常远小于，因此空间效率更高。但是，在邻接表中查找边需要遍历链表，时间效率不如邻接矩阵

邻接表结构与哈希表中的链式地址相似，因此链表过长时，可将链表转化为AVL树或红黑树，将时间复杂度从优化到；也可将链表转换为哈希表，将时间复杂度降低至

常见应用

  • 社交网络
  • 地铁线路
  • 星系建模

图基础操作

图的基础操作分为对边的操作和对顶点的操作。在不同的表示方法下，实现方式有所不同

  1. 基于邻接矩阵的实现
  • 添加或删除边：直接在邻接矩阵中修改指定边即可，时间复杂度为，无向图中需要同时更新两个方向的边
  • 添加顶点：在邻接矩阵尾部添加一行一列，全部填0，时间复杂度为
  • 删除顶点：在邻接矩阵中删除一行一列。最差情况是删除首行首列，个元素向左上移动，时间复杂度为
  • 初始化：传入n个顶点，初始化长度为n的顶点列表vertices，时间复杂度为；初始化n x n大小的邻接矩阵adjMat，时间复杂度为
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
class GraphAdjMat:
    """基于邻接矩阵实现的无向图类"""

    def __init__(self, vertices, edges):
        # 顶点列表，元素代表“顶点值”，索引代表“顶点索引”
        self.vertices = []
        self.adj_mat = []
        for val in vertices:
            self.add_vertex(val)
        for e in edges:
            self.add_edge(e[0], e[1])
        
    def size(self):
        return len(self.vertices)

    def add_vertex(self, val):
        n = self.size()
        self.vertices.append(val)
        new_row = [0] * n
        # 添加一行
        self.adj_mat.append(new_row)
        # 添加一列
        for row in self.adj_mat:
            row.append(0)

    def remove_vertex(self, index):
        if index >= self.size() or index < 0:
            raise IndexError()
        self.vertices.pop(index)
        # 删除行
        self.adj_mat.pop(index)
        # 删除列
        for row in adj_mat:
            row.pop(index)
        
    def add_edge(self, i, j):
        if i < 0 or j < 0 or i >= self.size() or j >= self.size() or i == j:
            raise IndexError()
        self.adj_mat[i][j] = 1
        self.adj_mat[j][i] = 1

    def remove_edge(self, i, j):
        if i < 0 or j < 0 or i >= self.size() or j >= self.size() or i == j:
            raise IndexError()
        self.adj_mat[i][j] = 0
        self.adj_mat[j][i] = 0

    def print(self):
        print("顶点列表 = ", self.vertices)
        print("邻接矩阵 = ")
        print_matrix(self.adj_mat)
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
class GraphAdjMat{
private:
    vector<int> vertices;
    vector<vertor<int>> adjMat;

public:
    GraphAdjMat(const vector<int>& vertices, const vector<vector<int>>& edges){
        for(int val : vertices){
            addVertex(val);
        }
        for (const vector<int>& edge : edges){
            addEdge(edge[0], edge[1]);
        }
    }

    int size() const{
        return vertices.size();
    }

    void addVertex(int val){
        int n = size();
        vertices.push_back(val);
        // 比push_back高效，直接在目标容器末尾构造元素，不需要额外的复制或移动操作
        adjMat.emplace_back(vector<int>(n, 0));
        for (vector<int>& row : adjMat){
            row.push_back(0);
        }
    }

    void removeVertex(int index){
        if (index < 0 || index >= size()){
            throw out_of_range("顶点不存在");
        }
        vertices.erase(vertices.begin() + index);
        adjMat.erase(adjMat.begin() + index);
        for (vector<int>& row : adjMat){
            row.erase(row.begin() + index);
        }
    }

    void addEdge(int i, int j){
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
            throw out_of_range("顶点不存在");
        }
        adjMat[i][j] = 1;
        adjMat[j][i] = 1;
    }

    void removeEdge(int i, int j){
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
            throw out_of_range("顶点不存在");
        }
        adjMat[i][j] = 0;
        adjMat[j][i] = 0;
    }

    void print(){
        cout << "顶点列表 = ";
        printVector(vertices);
        cout << "邻接矩阵 =" << endl;
        printVectorMatrix(adjMat);
    }
};
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
typedef struct{
    int vertices[MAX_SIZE];
    int adjMat[MAX_SIZE][MAX_SIZE];
    int size;
}GraphAdjMat;

GraphAdjMat* newGraphAdjMat(int* vertices, int size, int** edges, int numEdges){
    GraphAdjMat* graph = (GraphAdjMat*)malloc(sizeof(GraphAdjMat));
    graph->size = 0;
    int i;
    for(i = 0; i < size; i++){
        addVertex(graph, vertices[i]);
    }
    for(i = 0; i < numEdges; i++){
        addEdge(graph, edges[i][0], edges[i][1]);
    }
    return graph;
}

void delGraphAdjMat(GraphAdjMat* graph){
    free(graph);
}

int size(GraphAdjMat* graph){
    return graph->size;
}

void addVertex(GraphAdjMat* graph, int val){
    if (graph->size == MAX_SIZE) {
        fprintf(stderr, "图的顶点数量已达最大值\n");
        return;
    }
    int n = graps->size;
    graph->vertices[n] = val;
    for (int i = 0; i <= n; i++){
        graph->adjMat[n][i] = graph->adjMat[i][n] = 0;
    }
    graph->size++;
}

void removeVertex(GraphAdjMat* graph, int index){
    if (index < 0 || index >= graph->size) {
        fprintf(stderr, "顶点索引越界\n");
        return;
    }
    for(int i = 0; i < graph->size; i++){
        graph->vertices[i] = graph->vertices[i + 1];
    }
    // 在邻接矩阵中删除索引index的行
    for(int i = index, i < graph->size - 1; i++){
        for (int j = 0; j < graph->size; j++){
            graph->adjMat[i][j] = graph->AdjMat[i + 1][j];
        }
    }
    // 在邻接矩阵中删除索引index的列
    for(int i = 0; i < graph_size; i++){
        for(int j = index; j < graph->size - 1; j++){
            graph->adjMat[i][j] = graph->adjMat[i][j+1];
        }
    }
    graph->size--;
}

void addEdge(GraphAdjMat* graph, int i, int j){
    if (i < 0 || j < 0 || i >= graph->size || j >= graph->size || i == j) {
        fprintf(stderr, "边索引越界或相等\n");
        return;
    }
    graph->adjMat[i][j] = 1;
    graph->adjMat[j][i] = 1;
}

void removeEdge(GraphAdjMat *graph, int i, int j) {
    if (i < 0 || j < 0 || i >= graph->size || j >= graph->size || i == j) {
        fprintf(stderr, "边索引越界或相等\n");
        return;
    }
    graph->adjMat[i][j] = 0;
    graph->adjMat[j][i] = 0;
}

void printGraphAdjMat(GraphAdjMat *graph) {
    printf("顶点列表 = ");
    printArray(graph->vertices, graph->size);
    printf("邻接矩阵 =\n");
    for (int i = 0; i < graph->size; i++) {
        printArray(graph->adjMat[i], graph->size);
    }
}
  1. 基于邻接表的实现

设无向图顶点总数为n、边总数为m

  • 添加边：在顶点对应链表中添加边，无向图需要同时添加两个方向的边，时间复杂度为
  • 删除边：在顶点对应链表中查找并删除指定边，无向图需要同时删除两个方向的边，时间复杂度为
  • 添加顶点：在邻接表中添加一个链表，将新增顶点作为链表头节点，时间复杂度为
  • 删除顶点：遍历邻接表，删除包含指定顶点的所有边，时间复杂度为
  • 初始化：在邻接表中创建n个顶点和2m条边，时间复杂度为

在代码实现中

  • 为方便添加和删除顶点，使用列表（动态数组）来代替链表
  • 使用哈希表来存储邻接表，key为顶点实例，value为该顶点的邻接顶点列表

在邻接表中使用Vertex类来表示顶点，而不是用列表索引来区分不同顶点，这样的话删除某个顶点就不用对后面的顶点进行移动或其他操作，删除某一顶点之后无需改动其他顶点

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
class GraphAdjList:
    """基于邻接表实现的无向图类"""

    def __init__(self, edges):
        self.adj_lsit = dict[Vertex, list[Vertex]]() # 创建一个空的字典
        for edge in edges:
            self.add_vertex(edge[0])
            self.add_vertex(edge[1])
            self.add_edge(edge[0], edge[1])

    def size(self):
        return len(self.adj_list)

    def add_edge(self, vet1, vet2):
        if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2:
            raise ValueError()
        self.adj_list[vet1].append(vet2)
        self.adj_list[vet2].append(vet1)

    def remove_edge(self, vet1, vet2):
        if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2:
            raise ValueError()
        self.adj_list[vet1].remove(vet2)
        self.adj_list[vet2].remove(vet1)

    def add_vertex(self, vet):
        if vet in self.adj_list:
            return
        self.adj_list[vet] = []

    def remove_vertex(self, vet):
        if vet not in self.adj_list:
            raise ValueError()
        self.adj_list.pop(vet)
        for vertex in self.adj_list:
            if vet in self.adj_list[vetex]:
                self.adj_list[vertex].remove(vet)

    def print(self):
        print("邻接表=")
        for vertex in self.adj_list:
            tmp = [v.val for v in self.adj_list[vertex]]
            print(f"{vertex.val}: {tmp},")
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
class GraphAdjList{
private:
    unordered_map<Vertex*, vector<Vertex*>> adjList;

    // 在vector中删除指定节点
    void remove(vector<Vertex*>& vec, Vertex* vet){
        for (int i = 0; i < vec.size(); i++){
            if(vec[i] == vet){
                vec.earse(vec.begin() + i);
                break
            }
        }
    }

public:
    GraphAdjList(const vector<vector<Vertex*>> edges){
        for(const vector<Vertex* > &edge : edges){
            addVertex(edge[0]);
            addVertex(edge[1]);
            addEdge(edge[0], edge[1]);
        }
    }

    int size(){
        return adjList.size();
    }

    void addEdge(Vertex* vet1, Vertex* vet2){
        if(!adjList.count(vet1) || !adjList.count(vet2) || vet1 == vet2){
            throw invalid_arguement("不存在顶点");
        }
        adjList[vet1].push_back(vet2);
        adjList[vet2].push_back(vet1);
    }

    void removeEdge(Vertex *vet1, Vertex *vet2) {
        if (!adjList.count(vet1) || !adjList.count(vet2) || vet1 == vet2)
            throw invalid_argument("不存在顶点");
        // 删除边 vet1 - vet2
        remove(adjList[vet1], vet2);
        remove(adjList[vet2], vet1);
    }

    void addVertex(Vertex* vet){
        if(adjList.count(vet)){
            return;
        }
        adjList[vet] = vector<Vertex*>();
    }

    void removeVertex(Vertex* vet){
        if(!adjList.count(vet)){
            throw invalid_argument("不存在顶点");
        }
        adjList.erase(vet);
        for(auto &adj : adjList){
            remove(adj.second, vet);
        }
    }

     void print() {
        cout << "邻接表 =" << endl;
        for (auto &adj : adjList) {
            const auto &key = adj.first;
            const auto &vec = adj.second;
            cout << key->val << ": ";
            printVector(vetsToVals(vec));
        }
    }
};
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
typedef struct AdjListNode{
    Vertex* vertex;
    struct AdjListNode *next;
}AdjListNode;

typedef struct{
    AdjListNode* heads[MAX_SIZE];
    int size;
}GraphAdjList;

typedef struct{
    Vertex* vet1;
    Vertex* vet2;
}Edge;

// 查找顶点对应的节点
AdjListNode* findNode(GraphAdjList* graph, Vertex* vet){
    for(int i = 0; i < graph->size; i++){
        if(graph->heads[i]->vertex == vet){
            return graph->heads[i];
        }
    }
    return NULL;
}

void addEdgeHelper(AdjListNode* head, Vertex* vet){
    AdjListNode* node = (AdjListNode*)malloc(sizeof(AdjListNode));
    node->vertex = vet;
    node->next = head->next;
    head->next = node;
}

void removeEdgeHelper(AdjListNode* head, Vertex *vet){
    AdjListNode* pre = head;
    AdjListNode* cur = head->next;
    while(cur != NULL && cur->vertex != vet){
        pre = cur;
        cur = cur->next;
    }
    if(cur == NULL){
        return;
    }
    pre->next = cur->next;
    free(cur);
}

GraphAdjList* newGraphAdjList(Edge* edges, int numEdges){
    GraphAdjList *graph = (GraphAdjList *)malloc(sizeof(GraphAdjList));
    if(!graph){
        return NULL;
    }
    graph->size = 0;

    for(int i = 0; i < numEdges; i++){
        addVertex(graph, edges[i].vet1);
        addVertex(graph, edges[i].vet2);
        addEdge(graph, edges[i].vet1, edges[i].vet2);
    }

    for(int i = numEdges; i < MAX_SIZE; i++){
        graph->heads[i] = NULL;
    }

    return graph;
}

void delGraphAdjList(GraphAdjList* graph){
    for(int i = 0; i < graph->size; i++){
        AdjListNode* cur = graph->heads[i];
        while(cur != NULL){
            AdjListNode* next  = cur->next;
            if(cur != graph->heads[i]){
                free(cur);
            }
            cur = next;
        }
        free(graph->heads[i]->vertex);
        free(graph->heads[i]);
    }
    free(graph);
}

void addEdge(GraphAdjList *graph, Vertex *vet1, Vertex *vet2){
    AdjListNode *head1 = findNode(graph, vet1);
    AdjListNode *head2 = findNode(graph, vet2);
    assert(head1 != NULL && head2 != NULL && head1 != head2);
    addEdgeHelper(head1, vet2);
    addEdgeHelper(head2, vet1);
}

void removeEdge(GraphAdjList *graph, Vertex *vet1, Vertex *vet2) {
    AdjListNode *head1 = findNode(graph, vet1);
    AdjListNode *head2 = findNode(graph, vet2);
    assert(head1 != NULL && head2 != NULL);
    removeEdgeHelper(head1, head2->vertex);
    removeEdgeHelper(head2, head1->vertex);
}

void addVertex(GraphAdjList *graph, Vertex *vet) {
    assert(graph != NULL && graph->size < MAX_SIZE);
    AdjListNode *head = (AdjListNode *)malloc(sizeof(AdjListNode));
    head->vertex = vet;
    head->next = NULL;
    graph->heads[graph->size++] = head;
}

void removeVertex(GraphAdjList *graph, Vertex *vet){
    AdjListNode* node = findNode(graph, vet);
    assert(node != NULL);
    AdjListNode *cur = node, *pre = NULL;
    // 在邻接表中删除顶点 vet 对应的链表
    while(cur){
        pre = cur;
        cur = cur->next;
        free(pre);
    }
    // 遍历其他顶点的链表，删除所有包含 vet 的边
    for(int i = 0; i < graph->size; i++){
        cur = graph->heads[i];
        pre = NULL;
        while (cur) {
            pre = cur;
            cur = cur->next;
            if (cur && cur->vertex == vet) {
                pre->next = cur->next;
                free(cur);
                break;
            }
        }
    }
    // 将该顶点之后的顶点向前移动，以填补空缺
    int i;
    for (i = 0; i < graph->size; i++) {
        if (graph->heads[i] == node)
            break;
    }
    for (int j = i; j < graph->size - 1; j++) {
        graph->heads[j] = graph->heads[j + 1];
    }
    graph->size--;
    free(vet);
}

效率对比

设图中共有n个顶点和m条边

图的遍历

可以把树看作是图的一种特例，因此树的遍历操作也是图的遍历操作的一种特例

图的遍历操作可以分为两种：广度优先遍历(搜索)和深度优先遍历(搜索)

在非连通图中，从某个顶点出发，至少有一个顶点无法到达。遍历非连通图需要设置多个起点，以遍历到图的所有连通分量。

广度优先遍历

是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张

图的广度优先遍历

  1. 算法分析

BFS通常借助队列来实现

  • 将起始顶点startVet加入队列，开始循环
  • 每轮循环迭代中，弹出队首节点并记录访问，将该顶点的所有邻接顶点加入到队列尾部
  • 直到所有顶点被访问完成后结束

为防止重复遍历顶点，用一个哈希表visited记录哪些节点已被访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def graph_bfs(graph: GraphAdjList, strat_vet) -> list[Vertex]:
    """广度优先遍历 BFS"""
    # 使用邻接表来表示图
    res = []
    visited = set[Vertex]([start_vet])
    que = deque[Vertex]([start_vet])
    while len(queue) > 0:
        vet = que.popleft()
        res.append(vet)
        for adj_vet in graph.adj_list[vet]:
            if adj_vet in visited:
                continue
            que.append(adj_vet)
            visited.add(adj_vet)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<Vertex*> graphBFS(GraphAdjList& graph, Vertex* startVet){
    vector<Vertex*> res;
    unordered_set<Vertex*> visited = {startVet};
    queue<Vertex*> que;
    que.push(startVet);
    while(!que.empty()){
        Vertex* vet = que.front();
        que.pop();
        res.push_back(vet);
        for(auto adjVet : graph.adjList[vet]){
            if(visited.count(adjVet)){
                continue;
            }
            que.push(adjVet);
            visited.emplace(adjVet);
        }
    }
    return res;
}
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
typedef struct{
    Vertex* vertices[MAX_SIZE];
    int front, int rear, int size;
}Queue;

Queue* newQueue(){
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = q->size = 0;
    return q;
}

int isEmpty(Queue* q){
    return q->size == 0;
}

void enqueue(Queue* q, Vertex* vet){
    q->vertices[q->rear] = vet;
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->size++;
}

Vertex* dequeue(Queue* q){
    Vertex* vet = q->vertices[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    q->size--;
    return vet;
}

int isVisited(Vertex** visited, int size, Vertex* vet){
    for(int i = 0; i < size; i++){
        if(visited[i] == vet){
            return 1;
        }
    }
    return 0;
}

void graphBFS(GraphAdjList* graph, Vertex* startVet, Vertex** res, int *resSize, Vertex** visited, int* visitedSize){
    Queue* queue = newQueue();
    enqueue(queue, startVet);
    visited[(*visitedSize)++] = startVet;
    while(!isEmpty(queue)){
        Vertex* vet = dequeue(queue);
        res[(*resSize)++] = vet;
        AdjListNode * node = findNode(graph, vet);
        while(node != NULL){
            if(!isVisited(visited, *visitedSize, node->vertex)){
                enqueue(queue, node->vertex);
                visited[(*visitedSize)++] = node->vertex;
            }
            node = node->next;
        }
    }
    free(queue);
}
  1. 复杂度分析

设无向图顶点数为n，边数为m

  • 时间复杂度：所有顶点都会入队并出队一次，使用时间；遍历邻接顶点的过程中，所有边都会会访问2次，使用时间。总时间复杂度为

  • 空间复杂度：res、visted、que中顶点数量最多为n。空间复杂度为

深度优先遍历

深度优先遍历是一种优先走到底，无路可走再回头的遍历方式

图的深度优先遍历

  1. 算法实现

这种走到尽头再返回的算法范式通常基于递归来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def dfs(graph, visited, res, vet):
    """深度优先遍历DFS的辅助函数"""
    res.append(vet)
    visited.add(vet)
    for adjVet in graph.adj_list[vet]:
        if adjVet in visited:
            continue
        dfs(graph, visited, res, adjVet)

def graph_dfs(graph, start_vet):
    res = []
    visited = set()
    dfs(graph, visited, res, start_vet)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(GraphAdjList& graph, unordered_set<Vertex*> &visited, vector<Vertex*>& res, Vertex* vet){
    res.push_back(vet);
    visited.emplace(vet);
    for(Vertex* adjVet : graph.adjList[vet]){
        if(visited.count(adjVet)){
            continue;
        }
        dfs(graph, visited, res, adjVet);
    }
}

vector<Vertex*> graphDFS(GraphAdjList& graph, Vertex* startVet){
    vector<Vertex*> res;
    unordered_set<Vertex*> visited;
    dfs(graph, visited, res, startVer);
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int isVisited(Vertex** visited, int size, Vertex* vet){
    for(int i = 0; i < size; i++){
        if(visited[i] == vet){
            return 1;
        }
    }
    return 0;
}

void dfs(GraphAdjList* graph, Vertex** res, int* resSize, Vertex* vet){
    res[(*resSize)++] = vet;
    AdjListNode* node = findNode(graph, vet);
    while(node != NULL){
        if(!isVisited(res, *resSize, node->vertex)){
            dfs(graph, res, resSize, node->vertex);
        }
        node = node->next;
    }
}

void graphDFS(GraphAdjList* graph, Vertex* startVet, Vertex** res, int* resSize){
    dfs(graph, res, resSize, startVet);
}

广度优先遍历和深度优先遍历的遍历序列顺序均不唯一

  1. 复杂度分析

设无向图顶点数为n，边数为m

  • 时间复杂度：所有顶点访问一次，使用时间；所有边访问两次，使用时间。总时间复杂度为

  • 空间复杂度：res、visited顶点数最多为，递归深度最大为，总空间复杂度为

  • 标题: 数据结构：图
  • 作者: 敖炜
  • 创建于 : 2023-11-21 09:06:09
  • 更新于 : 2024-04-19 09:30:12
  • 链接: https://ao-wei.github.io/2023/11/21/数据结构：图/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
此页目录
数据结构：图
  1. 图
    1. 图常见类型与术语
    2. 图的表示
    3. 常见应用
  2. 图基础操作
    1. 效率对比
  3. 图的遍历
    1. 广度优先遍历
    2. 深度优先遍历