数据结构——图论基础

标签：Node 图论 struct int 基础连通 newNode 顶点数据结构

文章目录

1.图的基本概念
- 1.1图的定义
- 1.2 图的基本术语
2.图的存储结构与基本运算算法
3.图的遍历
- 3.1深度优先遍历(DFS)
- 3.2广度优先遍历(DFS)
4.生成树与最小生成树
- 4.1生成树的概念
- 4.2非连通图与生成树
5.最短路径
- 5.1Dijkstra算法
- 5.2Floyd-Warshall算法
6.拓扑排序

1.图的基本概念

1.1图的定义

在数学和计算机科学中，图（Graph）是一种数据结构，用于表示对象与对象之间的关系。图由两部分组成：

顶点（Vertex或Node）： 图中的基本单位，表示对象或元素。
边（Edge）：连接顶点的线段，表示顶点之间的关系或连接。
图可以用符号G=(V,E)表示，其中：

V是一个顶点集合。
E是一个边集合，每条边连接一个或多个顶点。

1.2 图的基本术语

无向图（undirected graph）：
如果一个图结构中，所有的边都没有方向性，那么这种图便称为无向图。
有向图（Digraph）：
在有向图中，图的边是有方向的。每条边都有一个方向，从一个顶点指向另一个顶点，表示一种单向的关系。
端点与邻接点：
- 无向图中，若存在一条边(i，j)，则顶点i和顶点j为端点，它们互为邻接点。
- 有向图中，若存在一条边<i, j> → 顶点i为起始端点（简称为起点），顶点j为终止端点（简称为终点），它们互为邻接点。
顶点的度、入度与出度：
- 无向图中，以顶点i为端点的边数称为该顶点的度。
- 有向图中，以顶点i为终点的入边的数目，称为该顶点的入度；以顶点i为始点的出边的数目，称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。
完全图：
- 无向图中，每两个顶点之间都存在着一条边，称为完全无向图，包含有 n(n-1)/2 条边。
- 有向图中，每两个顶点之间都存在着方向相反的两条边，称为完全有向图，包含有 n(n-1) 条边。
子图：
设有两个图 G = (V, E) 和 G' = (V', E')，若 V' 是 V 的子集，且 E' 是 E 的子集，则称 G' 是 G 的子图。
路径和路径长度：
- 在一个图 G = (V, E) 中，从顶点 i 到顶点 j 的一条路径为 (i, i2, i3, ..., im, j)，其中所有的 (ix, iy) 属于 E(G) 或 <ix, im> 属于 E(G)。
- 路径长度是指一条路径上经过的边的数目。
- 若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。
回路或环：
- 若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回路或环。
- 开始点与结束点相同的简单路径被称为简单回路或简单环。
连通、连通图和连通分量（无向图中）：
- 若从顶点 i 到顶点 j 有路径，则称顶点 i 和 j 是连通的。
- 若图中任意两个顶点都连通，则称为 连通图，否则称为 非连通图。
- 无向图 G 中的极大连通子图称为 G 的 连通分量。显然，任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。
强连通图和强连通分量：
- 若从顶点 i 到顶点 i 有路径，则称从顶点 i 到 j 是连通的。
- 若图 G 中的任意两个顶点 i 和 j 都连通，即从顶点 i 到 j 和从顶点 j 到 i 都存在路径，则称图 G 是 强连通图。
- 有向图G中的极大强连通子图称为G的强连通分量。
- 强连通图只有一个强连通分量，即本身。非强连通图有多个强连通分量。
权和网
- 图中每一条边都可以附带有一个对应的数值，这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。
- 边上带有权的图称为带权图，也称作网。

2.图的存储结构与基本运算算法

2.1邻接矩阵

若G是无向图：

adjMat[i][j] = adjMat[j][i] = 1//i和j之间存在边
adjMMat[i][j] = 0//i和j之间不存在边

若G是有向图

adjMat[i][j] = 1//<i,j>
adjMMat[i][j] = 0//i和j之间不存在边

若G是带权无向图

adjMat[i][j] = adjMat[j][i] = 权重//带权边
adjMMat[i][j] = 无穷大//i和j之间不存在边

若G是带权有向图

adjMat[i][j] == 权重//带权边<i,j>
adjMMat[i][j] = 无穷大//i和j之间不存在边

邻接矩阵结构体表示

// This is the implementation of a graph data structure in C.  
#define Max_Size 255  
typedef struct{  
    int vertices[Max_Size];  
    int adjMat[Max_Size][Max_Size];  
    int size;  
}GraphAdjMat;

2.2邻接表

使用邻接表表示图是一种常见的图数据结构，它使用数组和链表来存储图中的顶点和边。每个顶点都有一个链表，链表中存储着与该顶点相邻的所有顶点的信息。对于带权无向图，链表中的每个节点还会存储边的权重。

// 定义邻接表中的节点
struct EdgeNode {
    int adjvex;         // 邻接点的索引
    int weight;         // 边的权重
    struct EdgeNode *next; // 指向下一个邻接点的指针
};

// 定义图的结构
struct Graph {
    int numVertices;    // 图的顶点数
    struct EdgeNode **adjList; // 邻接表数组
};

2.3十字链表

在图的表示方法中，十字链表（也称为边链表）是一种用于表示图的边和顶点信息的数据结构。十字链表由边表和顶点表组成，其中边表中的每个边记录了与该边相连的两个顶点的信息，而顶点表中的每个顶点记录了与该顶点相连的所有边的信息。

#define MAXV 20 // 最大顶点数

// 定义边表节点
typedef struct ArcNode {
    int adjvex; // 该边所指向的顶点的位置
    struct VNode *v; // 指向顶点表中相应顶点的指针
    struct ArcNode *next; // 指向下一条边的指针
} ArcNode;

// 定义顶点表节点
typedef struct VNode {
    int data; // 顶点信息
    ArcNode *first; // 指向第一条依附该顶点的边
} VNode, AdjList[MAXV]; // 顶点表

// 定义图的结构
typedef struct {
    AdjList vertices; // 指向顶点表的指针
    int vexnum, arcnum; // 图的当前顶点数和弧数
} CrossGraph;

3.图的遍历

3.1深度优先遍历(DFS)

深度优先遍历过程:

从图中某个初始顶点v出发，首先访问初始顶点v。
选择一个与顶点v相邻且没被访问过的顶点w，再从w出发进行深度优先搜索，直到图中与当前顶点v邻接的所有顶点都被访问过为止。

无向图 ( G = (V, E) )，其中
V = {a, b, c, d, e, f}
E = {(a, b), (a, e), (a, c), (b, e), (c, f), (f, d), (e, d)}
对该图进行深度优先排序，得到的顶点序列正确的是（）。
A. a, b, e, c, d, f
B. a, c, f, e, b, d
C. a, e, b, c, f, d
D. a, e, d, f, c, b

在这里插入图片描述

深度优先搜索得到：a,b,e,d,f,c

// 定义图的节点
typedef struct Node {
    char data;
    struct Node* next;
} Node;

// 定义栈的节点
typedef struct StackNode {
    Node* ptr;
    struct StackNode* next;
} StackNode;

// 定义栈
typedef struct Stack {
    StackNode* top;
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s->top = NULL;
}

// 检查栈是否为空
int isEmpty(Stack* s) {
    return s->top == NULL;
}

// 入栈
void push(Stack* s, Node* n) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    newNode->ptr = n;
    newNode->next = s->top;
    s->top = newNode;
}

// 出栈
Node* pop(Stack* s) {
    if (isEmpty(s)) return NULL;
    StackNode* temp = s->top;
    Node* node = temp->ptr;
    s->top = s->top->next;
    free(temp);
    return node;
}

// 创建图的节点
Node* createNode(char data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 添加边
void addEdge(Node** head, char src, char dest) {
    Node* newNode = createNode(dest);
    newNode->next = *head;
    *head = newNode;
}

// 深度优先遍历
void dfs(Node* head) {
    Stack s;
    initStack(&s);
    Node* current = head;
    while (current != NULL || !isEmpty(&s)) {
        while (current != NULL) {
            printf("%c ", current->data);
            push(&s, current);
            current = current->next;
        }
        if (!isEmpty(&s)) {
            current = pop(&s);
            current = current->next;
        }
    }
}

3.2广度优先遍历(DFS)

广度优先遍历的过程:

访问初始点v，接着访问v的所有未被访问过的邻接点V，V’…，v.
按照V，V’…，v,的次序，访问每一个顶点的所有未被访问过的邻接点,
依次类推，直到图中所有和初始点v有路径相通的顶点都被访问过为止。

广度优先搜索得到：a,b,e,c,d,f

// 定义图的节点
typedef struct Node {
    char data;
    struct Node* next;
} Node;

// 定义队列的节点
typedef struct QueueNode {
    char data;
    struct QueueNode* next;
} QueueNode;

// 定义队列
typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    q->front = q->rear = NULL;
}

// 检查队列是否为空
int isEmpty(Queue* q) {
    return q->front == NULL;
}

// 入队
void enqueue(Queue* q, char data) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->data = data;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 出队
char dequeue(Queue* q) {
    if (isEmpty(q)) return '\0';
    QueueNode* temp = q->front;
    char data = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return data;
}

// 创建图的节点
Node* createNode(char data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 添加边（这里我们使用邻接表表示图）
void addEdge(Node** adjList[], char src, char dest) {
    Node* newNode = createNode(dest);
    newNode->next = adjList[src];
    adjList[src] = newNode;
}

// 广度优先遍历
void bfs(Node* adjList[], char startVertex) {
    Queue q;
    initQueue(&q);
    enqueue(&q, startVertex);
    int visited[256] = {0}; // 假设图中的顶点数据不会超过256个不同的字符
    visited[startVertex] = 1;

    while (!isEmpty(&q)) {
        char currentVertex = dequeue(&q);
        printf("%c ", currentVertex);

        Node* temp = adjList[currentVertex];
        while (temp) {
            char adjVertex = temp->data;
            if (!visited[adjVertex]) {
                visited[adjVertex] = 1;
                enqueue(&q, adjVertex);
            }
            temp = temp->next;
        }
    }
}

4.生成树与最小生成树

4.1生成树的概念

生成树是图的一个子图，它满足以下条件：

连接性：生成树必须包含图中的所有顶点，且这些顶点之间是连通的。
无环性：生成树中不能包含任何环（cycle），即它是一个树结构。
最小边数：生成树的边数恰好是顶点数减一，即n−1n−1 条边，其中nn 是顶点数。

生成树的一个重要性质是，对于一个有nn 个顶点的图，它的生成树有n−1n−1 条边，且这些边连接了图中的所有顶点。

下面是关于DFS（深度优先搜索）生成树和BFS（广度优先搜索）生成树的对比

特征	DFS生成树	BFS生成树
搜索策略	深度优先	广度优先
起始点	任意顶点	任意顶点
遍历顺序	尽可能深地搜索树的分支	一层一层地搜索树的分支
栈的使用	使用栈（递归实现）	使用队列
路径选择	总是选择未访问的邻接顶点中深度最大的顶点	总是选择未访问的邻接顶点中深度最小的顶点
生成树结构	可能包含后继节点	可能包含前驱节点
时间复杂度	(O(V+E))	(O(V+E))
空间复杂度	(O(V))	(O(V))
适用场景	适合解决需要深入探索的问题，如寻找路径	适合解决需要逐层遍历的问题，如最短路径
实现方式	递归或栈	队列

4.2非连通图与生成树

对于连通图:仅需调用遍历过程(DFS或BFS)一次，从图中任一顶点出发，便可以遍历图中的各个顶点，产生相应的生成树。
对于非连通图:需多次调用遍历过程。每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树。所有连通分量的生成树组成非连通图的生成森林。
重点：求带权连通图的最小生成树
在带权连通图中求最小生成树（Minimum Spanning Tree, MST）是一个经典的问题，可以通过几种不同的算法来解决。最常用的算法包括：
Kruskal 算法：通过选择权重最小的边来构建树，同时确保不会形成环。
Prim 算法：从一个顶点开始，逐步添加权重最小的边，直到所有顶点都被包含在树中。

Kruskal 算法的基本步骤如下：

将图中的所有边按照权重从小到大排序。
初始化一个空的森林（每个顶点都是一个单独的树）。
遍历排序后的边列表，对于每条边：
- 如果这条边连接的两个顶点属于不同的树，则将这条边加入到最小生成树中，并将这两个顶点所在的树合并。
- 如果这条边连接的两个顶点属于同一棵树，则忽略这条边，以避免形成环。
重复步骤3，直到最小生成树包含所有顶点。

Prim 算法的基本步骤如下：

从任意一个顶点开始，将其作为最小生成树的起始点。
选择一个权重最小的边，该边的一个顶点在当前的最小生成树中，另一个顶点不在。
将这个顶点加入到最小生成树中。
重复步骤2和3，直到所有顶点都被包含在最小生成树中。

5.最短路径

图的最短路径是指在图中从一个顶点（起点）到另一个顶点（终点）之间的一条路径，使得这条路径上的边的权重之和最小。最短路径问题在许多实际应用中非常重要，例如在交通网络、通信网络等领域。

5.1Dijkstra算法

Dijkstra算法是一种用于寻找图中单源最短路径的算法，由荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra）于1956年提出。该算法适用于带有非负权重的图。

算法步骤：

初始化：将所有顶点的距离设为无穷大（除了起始顶点，设为0），并创建一个未访问顶点集合。
选择：从未访问顶点集合中选择距离最小的顶点，标记为已访问。
更新：对于该顶点的所有邻接点，计算通过当前顶点到邻接点的距离，如果这个距离小于邻接点当前记录的距离，则更新邻接点的距离。
重复：重复步骤2和3，直到所有顶点都被访问或者目标顶点被访问。

算法特点：

效率：使用优先队列可以提高效率，尤其是在顶点数较多的图中。
适用性：适用于边权重非负的图。
局限性：不适用于包含负权重边的图。

5.2Floyd-Warshall算法

Floyd-Warshall算法是一种用于寻找图中所有顶点对之间最短路径的算法。该算法由Robert Floyd于1962年提出。