Logo

菜单

Administrator
Administrator
发布于 2024-09-06 / 14 阅读
0
0

第5节：图（Graph）

#c语言

太好了！接下来，我们将进入更复杂的数据结构——图（Graph）。图是一种非常灵活和强大的数据结构，广泛应用于社交网络、网络通信、路线规划、推荐系统等领域。我们将从图的基础知识开始，逐步深入到图的表示、遍历和高级算法。

第5节：图（Graph）

5.1 图的基本概念

图由**顶点（vertex）和边（edge）**组成，是一组顶点通过边连接的结构。根据边的方向性，图可以分为以下几类：

  • 无向图（Undirected Graph）：边没有方向，表示顶点之间的双向关系。
  • 有向图（Directed Graph）：边有方向，表示顶点之间的单向关系。

图的基本术语：

  • 顶点（Vertex）：图中的一个节点。
  • 边（Edge）：连接两个顶点的线。
  • 度（Degree）：连接某个顶点的边的数量。无向图中的度是该顶点的总连接数，而有向图中的入度和出度分别表示进入和离开该顶点的边的数量。

5.2 图的表示方法

图可以用邻接矩阵或邻接表来表示。

1. 邻接矩阵表示法

邻接矩阵是一种二维数组，用来表示图的连接关系。如果顶点i和顶点j之间有边，则矩阵A[i][j] = 1，否则为0。在有向图中，A[i][j] = 1表示有一条从i到j的边。

邻接矩阵的实现：

#include <stdio.h>

#define MAX_VERTICES 5

// 邻接矩阵表示的图
void printAdjacencyMatrix(int graph[MAX_VERTICES][MAX_VERTICES], int vertices) {
    printf("Adjacency Matrix:\n");
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = {0}; // 初始化矩阵为0

    // 添加边 (无向图)
    graph[0][1] = 1;
    graph[1][0] = 1;
    graph[1][2] = 1;
    graph[2][1] = 1;
    graph[2][3] = 1;
    graph[3][2] = 1;
    graph[3][4] = 1;
    graph[4][3] = 1;

    printAdjacencyMatrix(graph, MAX_VERTICES);

    return 0;
}
2. 邻接表表示法

邻接表是一种更节省空间的图表示法，尤其适合稀疏图。每个顶点拥有一个链表，链表中的节点表示该顶点连接的所有顶点。

邻接表的实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 5

// 定义链表节点
struct Node {
    int vertex;
    struct Node* next;
};

// 定义邻接表
struct Graph {
    struct Node* adjLists[MAX_VERTICES];
};

// 创建新节点
struct Node* createNode(int vertex) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}

// 创建图
struct Graph* createGraph() {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    for (int i = 0; i < MAX_VERTICES; i++) {
        graph->adjLists[i] = NULL; // 初始化每个顶点的邻接表为空
    }
    return graph;
}

// 添加边 (无向图)
void addEdge(struct Graph* graph, int src, int dest) {
    // 添加边 src -> dest
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 添加边 dest -> src
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// 打印图
void printGraph(struct Graph* graph) {
    for (int i = 0; i < MAX_VERTICES; i++) {
        struct Node* temp = graph->adjLists[i];
        printf("Vertex %d: ", i);
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    struct Graph* graph = createGraph();

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printGraph(graph);

    return 0;
}

5.3 图的遍历

图的遍历是访问图中所有顶点的过程。常见的遍历方法有两种：

  1. 深度优先搜索（DFS）：沿着图的一个分支尽可能深入，然后回溯到上一个节点继续遍历。
  2. 广度优先搜索（BFS）：从一个节点开始，访问所有直接邻接的节点，再依次访问这些节点的邻接节点。
1. 深度优先搜索（DFS）

DFS可以使用递归或栈来实现。我们从一个顶点开始，将其标记为访问过，递归地访问所有未访问的邻接顶点。

DFS的递归实现：

void DFS(struct Graph* graph, int vertex, int visited[]) {
    visited[vertex] = 1; // 标记当前顶点为已访问
    printf("%d -> ", vertex);

    struct Node* temp = graph->adjLists[vertex];
    while (temp) {
        int connectedVertex = temp->vertex;
        if (!visited[connectedVertex]) {
            DFS(graph, connectedVertex, visited); // 递归访问未访问的邻接顶点
        }
        temp = temp->next;
    }
}

int main() {
    struct Graph* graph = createGraph();

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 3);

    int visited[MAX_VERTICES] = {0}; // 初始化所有顶点为未访问状态

    printf("Depth First Traversal starting from vertex 2:\n");
    DFS(graph, 2, visited);

    return 0;
}
2. 广度优先搜索（BFS）

BFS使用队列实现。我们从一个顶点开始，将其加入队列，依次访问队列中的节点，并将未访问的邻接节点加入队列。

BFS的实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 5

struct Node {
    int vertex;
    struct Node* next;
};

struct Graph {
    struct Node* adjLists[MAX_VERTICES];
    int visited[MAX_VERTICES];
};

struct Queue {
    int items[MAX_VERTICES];
    int front, rear;
};

// 创建队列
struct Queue* createQueue() {
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

// 判断队列是否为空
int isEmpty(struct Queue* q) {
    return q->rear == -1;
}

// 入队操作
void enqueue(struct Queue* q, int value) {
    if (q->rear == MAX_VERTICES - 1) {
        printf("Queue is full\n");
        return;
    }
    if (q->front == -1) {
        q->front = 0;
    }
    q->items[++q->rear] = value;
}

// 出队操作
int dequeue(struct Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = q->items[q->front++];
    if (q->front > q->rear) {
        q->front = q->rear = -1; // 重置队列为空
    }
    return item;
}

// 广度优先搜索（BFS）
void BFS(struct Graph* graph, int startVertex) {
    struct Queue* q = createQueue();
    graph->visited[startVertex] = 1;
    enqueue(q, startVertex);

    while (!isEmpty(q)) {
        int currentVertex = dequeue(q);
        printf("%d -> ", currentVertex);



        struct Node* temp = graph->adjLists[currentVertex];
        while (temp) {
            int adjVertex = temp->vertex;
            if (!graph->visited[adjVertex]) {
                graph->visited[adjVertex] = 1;
                enqueue(q, adjVertex);
            }
            temp = temp->next;
        }
    }
}

int main() {
    struct Graph* graph = createGraph();

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 3);

    printf("Breadth First Traversal starting from vertex 2:\n");
    BFS(graph, 2);

    return 0;
}

5.4 常见图算法

  1. 最短路径算法
    • Dijkstra算法：用于无负权边的图，计算从起点到其他顶点的最短路径。
    • Bellman-Ford算法：用于有负权边的图，计算最短路径。
  2. 最小生成树算法
    • Kruskal算法：使用贪心思想，生成最小生成树。
    • Prim算法：逐步扩展最小生成树。

练习题

  1. 连通性检查：实现一个函数，检查图是否是连通图（即所有顶点是否连通）。
  2. 拓扑排序：在有向无环图中，使用DFS实现拓扑排序。
  3. Dijkstra算法：实现Dijkstra算法，找出图中从一个顶点到所有其他顶点的最短路径。
  4. Kruskal算法：实现Kruskal算法，找出图的最小生成树。
  5. 图的环检测：编写一个程序，检测无向图中是否存在环。

完成这些练习后，你将对图的基本操作和算法有深入理解。

第6节：高级图算法
第4节：树（Tree）

评论