数据结构——图详解

数据结构——图详解 | 极客日志

void DFSGraph(MGraph* graph, int v) {
    visitMGraphNode(&graph->vex[v]);
    MGraphVisited[v] = 1;
    for (int i = 0; i < graph->nodeNum; i++) {
        if (isEdge(graph->edges[v][i]) && MGraphVisited[i] == 0) {
            DFSGraph(graph, i);
        }
    }
}

void DFSAGraph(const AGraph* graph, int v) {
    ArcEdge* p;
    graph->visited[v] = 1;
    visitAGraphNode(&graph->nodes[v]);
    p = graph->nodes[v].firstEdge;
    while (p) {
        if (graph->visited[p->no] == 0) {
            DFSAGraph(graph, p->no);
        }
        p = p->next;
    }
}

void BFSGraph(MGraph* graph, int v) {
    int queue[MaxNodeNum];
    int rear = 0, front = 0;
    int cur;
    rear = (rear + 1) % MaxNodeNum;
    queue[rear] = v;
    MGraphVisited[v] = 1;
    while (front != rear) {
        front = (front + 1) % MaxNodeNum;
        cur = queue[front];
        visitMGraphNode(&graph->vex[cur]);
        for (int i = 0; i < graph->nodeNum; i++) {
            if (isEdge(graph->edges[cur][i]) && !MGraphVisited[i]) // 两点右边且没 vis 过
            {
                rear = (rear + 1) % MaxNodeNum;
                queue[rear] = i;
                MGraphVisited[i] = 1;
            }
        }
    }
}

void BFSAGraph(const AGraph* graph, int v) {
    int* que = malloc(sizeof(int) * graph->nodeNum);
    int front = 0, rear = 0;
    ArcEdge* p;
    int cur;
    rear = (rear + 1) % graph->nodeNum;
    que[rear] = v;
    graph->visited[v] = 1;
    while (front != rear) {
        front = (front + 1) % graph->nodeNum;
        cur = que[front];
        visitAGraphNode(&graph->nodes[cur]);
        p = graph->nodes[cur].firstEdge;
        while (p) {
            if (graph->visited[p->no] == 0) {
                rear = (rear + 1) % graph->nodeNum;
                que[rear] = p->no;
                graph->visited[p->no] = 1;
            }
            p = p->next;
        }
    }
    free(que);
}

void initEdgeSet(MGraph* graph, EdgeSet* edges) // 将邻接矩阵交给 edge 统计
{
    int k = 0;
    for (int i = 0; i < graph->nodeNum; i++) // 遍历每个顶点
    {
        for (int j = i + 1; j < graph->nodeNum; j++) // 遍历上三角
        {
            if (graph->edges[i][j] > 0)
            {
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].w = graph->edges[i][j];
                k++;
            }
        }
    }
}

void sortEdgeSet(EdgeSet* edges, int num) // 排序
{
    EdgeSet tmp;
    for (int i = 0; i < num; i++) // 遍历每个顶点
    {
        for (int j = i + 1; j < num; j++) // 遍历上三角
        {
            if (edges[j].w < edges[i].w)
            {
                memcpy(&tmp, &edges[i], sizeof(EdgeSet));
                memcpy(&edges[i], &edges[j], sizeof(EdgeSet));
                memcpy(&edges[j], &tmp, sizeof(EdgeSet));
            }
        }
    }
}

static int getRoot(const int* uSet, int a)
{
    while (uSet[a] != a)
    {
        a = uSet[a];
    }
    return a;
}

int KruskalMGraph(const EdgeSet* edge, int num, int node_num, EdgeSet* res)
{
    int* uSet;
    int cnt = 0;
    int sum = 0;
    // 1.初始化并查集
    uSet = malloc(sizeof(int) * node_num);
    if (uSet == NULL)
    {
        return -1;
    }
    for (int i = 0; i < node_num; i++)
    {
        uSet[i] = i;
    }
    // 2、从已经排序好的边集中，找到最小的边，且不构成环
    for (int i = 0; i < num; i++)
    {
        int a = getRoot(uSet, edge[i].begin);
        int b = getRoot(uSet, edge[i].end);
        if (a != b)
        {
            // 不构成环
            uSet[a] = b;
            res[cnt].begin = edge[i].begin;
            res[cnt].end = edge[i].end;
            res[cnt].w = edge[i].w;
            sum += edge[i].w;
            cnt++;
            if (cnt == node_num - 1)
            {
                break;
            }
        }
    }
    free(uSet);
    return sum;
}

int PrimMGraph(const MGraph* graph, int start, EdgeSet* res)
{
    int* cost = malloc(sizeof(int) * graph->nodeNum); // 图中各顶点的权值数组
    int* mark = malloc(sizeof(int) * graph->nodeNum); // 图中顶点激活的状态
    int* visited = malloc(sizeof(int) * graph->nodeNum); // 从哪个顶点开始访问，-1 表示没有被访问
    int sum = 0;
    int mini;
    // 1.更新第一个结点激活的状态
    for (int i = 0; i < graph->nodeNum; i++)
    {
        cost[i] = graph->edges[start][i];
        mark[i] = 0;
        //1.1 更新 visited 数组，是从哪个结点访问的
        if (cost[i] < INF)
        {
            visited[i] = start;
        }
        else
        {
            visited[i] = -1;
        }
    }
    mark[start] = 1;
    int k = 0;
    // 2、动态激活结点，找最小值
    for (int i = 0; i < graph->nodeNum;++i)
    {
        int min = INF;
        k = 0;
        for (int j = 0; j < graph->nodeNum; j++)
        {
            if (mark[j] == 0 && cost[j] < min)
            {
                min = cost[j];
                k = j;
            }
        }
        mark[k] = 1;
        res[i].begin = visited[k];
        res[i].end = k;
        res[i].w = min;
        sum += min;
        // 每激活一个顶点，需要更新 cost 数组
        for (int j = 0; j < graph->nodeNum; j++)
        {
            if (mark[j] == 0 && graph->edges[k][j] < cost[j])
            {
                cost[j] = graph->edges[k][j];
                visited[j] = k;
            }
        }
    }
    free(cost);
    free(mark);
    free(visited);
    return sum;
}

  **Dijkstra 算法是求单源点到其他结点的最短路径的方法，故其他任何节点，都是依赖于源点出发的。**

  这样，肯定是先找源点能到节点的最短路径，在这个基础上，通过确定的最短点再次发散到其他节点，继续找最小，以此类推，直到找完所有点。

  找的过程，记得要标记已经找到过的结点，这样能避免环路出现。

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

void DijkstraMGraph(const MGraph* graph, int start, int dist[], int path[])
{
    int* mark; // 节点的访问记录
    mark = malloc(sizeof(int) * graph->nodeNum);
    // 1、激活 start 后，节点距离表 dist 更新、paths 数组的初始化，根节点对应 -1
    for (int i = 0; i < graph->nodeNum; i++)
    {
        dist[i] = graph->edges[start][i];
        mark[i] = 0;
        if (dist[i] < INF)
        {
            path[i] = start;
        }
        else
        {
            path[i] = -1;
        }
    }
    mark[start] = 1;
    path[start] = -1;
    dist[start] = 0;
    // 2、从 dist 里找最小值
    int mini;
    int tmpIndex = 0;
    for (int i = 0; i < graph->nodeNum - 1; i++)
    {
        mini = INF;
        // 从未激活的节点中，找到一个源点的最短路径
        for (int j = 0; j < graph->nodeNum; ++j)
        {
            if (mark[j] == 0 && dist[j] < mini)
            {
                mini = dist[j];
                tmpIndex = j;
            }
        }
        mark[tmpIndex] = 1;
        // 以刚激活的节点，更新源点到其他结点的路径
        for (int j = 0; j < graph->nodeNum; j++)
        {
            if (mark[j] == 0 && dist[tmpIndex] + graph->edges[tmpIndex][j] < dist[j])
            {
                dist[j] = dist[tmpIndex] + graph->edges[tmpIndex][j];
                path[j] = tmpIndex;
            }
        }
    }
    free(mark);
}

// 满递增栈
void showShortPath(int path[], int num, int pos)
{
    int* stack;
    int top = -1;
    stack = malloc(num * sizeof(int));
    if (stack == NULL)
    {
        return;
    }
    // 1、将上一个状态压入栈
    while (path[pos] != -1)
    {
        stack[++top] = pos;
        pos = path[pos];
    }
    stack[++top] = pos;
    //2、弹栈打印 pos 到源点路径
    while (top != -1)
    {
        printf("\t%d", stack[top--]);
    }
    printf("\n");
    free(stack);
}

  **其本质思想为：两点之间的中转点有可能会使这两个点更短，其实我们 Dijkstra 的本质思想是不是也是这个？**也就是不断的进行一种**松弛（relax）**操作，而我们 Dijkstra 不过是在松弛的基础上又加上了贪心，那么我们就来看看我们的代码吧

#include"MatrixGraph.h"
#include<stdio.h>
#define Max_Size 10

static int dist[Max_Size][Max_Size];
static int path[Max_Size][Max_Size];

void initMatG(MGraph* graph)
{
    char* nodenames[] = { "V0", "V1", "V2", "V3" };
    initMGraph(graph, nodenames, sizeof(nodenames) / sizeof(nodenames[0]), 1, INF);
    for (int i = 0; i < graph->nodeNum; i++)
    {
        graph->edges[i][i] = 0;
    }
    addMGraphEdge(graph, 0, 1, 1);
    addMGraphEdge(graph, 0, 3, 4);
    addMGraphEdge(graph, 1, 2, 9);
    addMGraphEdge(graph, 1, 3, 2);
    addMGraphEdge(graph, 2, 0, 3);
    addMGraphEdge(graph, 2, 1, 5);
    addMGraphEdge(graph, 2, 3, 8);
    addMGraphEdge(graph, 3, 2, 6);
}

void shortPathFloyd(const MGraph* graph)
{
    // 初始化
    for (int i = 0; i < graph->nodeNum; i++)
    {
        for (int j = 0; j < graph->nodeNum; ++j)
        {
            dist[i][j] = graph->edges[i][j];
            if (dist[i][j] < INF && i != j)
            {
                path[i][j] = i;
            }
            else
            {
                path[i][j] = -1;
            }
        }
    }
    // floyd
    for (int k = 0; k < graph->nodeNum; k++)
    {
        for (int i = 0; i < graph->nodeNum; i++)
        {
            for (int j = 0; j < graph->nodeNum; j++)
            {
                if (dist[i][k] < INF && dist[k][j] < INF && dist[i][j] > dist[i][k] + dist[k][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = path[k][j];
                }
            }
        }
    }
}

void printPath(int i, int j)
{
    if (i == j)
    {
        printf("%d ", i);
        return;
    }
    int k = path[i][j];
    printPath(i, k);
    printf("%d ", j);
}

int main()
{
    MGraph graph;
    initMatG(&graph);
    shortPathFloyd(&graph);
    for (int i = 0; i < graph.nodeNum; i++)
    {
        for (int j = 0; j < graph.nodeNum; j++)
        {
            printf("%2d ", dist[i][j]);
        }
        printf("\n");
    }
    printf("========================\n");
    for (int i = 0; i < graph.nodeNum; i++)
    {
        for (int j = 0; j < graph.nodeNum; j++)
        {
            printf("%2d ", path[i][j]);
        }
        printf("\n");
    }
    printf("========================\n");
    printPath(1, 0);
    return 0;
}

#include "TopoSort.h"
#include<stdlib.h>
#include<string.h>

int TopologicSortAGraph(AGraph* graph)
{
    int cnt = 0;
    // 定义一个入度记录表，便于发现入度为 0 时，放入缓存区
    int* inDegree;
    inDegree = malloc(sizeof(int) * graph->nodeNum);
    if (inDegree == NULL)
    {
        return -1;
    }
    memset(inDegree, 0, sizeof(int) * graph->nodeNum);
    // 初始化入度记录表
    for (int i = 0; i < graph->nodeNum; i++)
    {
        if (graph->nodes[i].firstEdge)
        {
            // 说明 i 结点开始有边
            ArcEdge* edge = graph->nodes[i].firstEdge;
            while (edge)
            {
                // 此处回顾一下之前的邻接表的边的定义
                // inDegree 记录的是后一个结点的入度情况，那么我们此时就用 edge->no 刚好对应着后续的入度
                ++inDegree[edge->no];
                edge = edge->next;
            }
        }
    }
    // 查找入度记录表，度为 0 的点，设计一个链式栈的缓存区，更新入度记录表时，发现 0 就立刻放入栈
    int* stack = malloc(sizeof(int) * graph->nodeNum);
    if (stack == NULL)
    {
        return -1;
    }
    int top = -1;
    for (int i = 0; i < graph->nodeNum; i++)
    {
        if (inDegree[i] == 0)
        {
            stack[++top] = i;
        }
    }
    // 根据任务栈里的数据，弹出第一个任务，将这个任务对应的节点相关的入边个数删除
    // 更细入度记录表，如果在更新过程中，发现入度为 0，直接入栈
    int index;
    while (top != -1)
    {
        index = stack[top--];
        cnt++;
        visitAGraphNode(&graph->nodes[index]);
        // 更新入度信息
        ArcEdge* edge = graph->nodes[index].firstEdge;
        while (edge)
        {
            --inDegree[edge->no];
            if (inDegree[edge->no] == 0)
            {
                stack[++top] = edge->no;
            }
            edge = edge->next;
        }
    }
    free(inDegree);
    free(stack);
    // 判断是否有环
    if (cnt == graph->nodeNum)
        return 0;
    else
        return 1;
}

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

static int topologicalOrder(const AGraph* graph, int* ETV, int* LTV)
{
    int* inDegree = malloc(sizeof(int) * graph->nodeNum);
    memset(inDegree, 0, sizeof(int) * graph->nodeNum);
    //1、初始化图中所有顶点的入度记录表
    for (int i = 0; i < graph->nodeNum; i++)
    {
        if (graph->nodes[i].firstEdge)
        {
            ArcEdge* edge = graph->nodes[i].firstEdge;
            while (edge)
            {
                ++inDegree[edge->no];
                edge = edge->next;
            }
        }
    }
    // 2、将入度为 0 的节点入栈，出栈的时候
    int top = -1;
    int* stack = malloc(sizeof(int) * graph->nodeNum);
    if (stack == NULL)
    {
        free(inDegree);
        return -1;
    }
    int* topOut = malloc(sizeof(int) * graph->nodeNum);
    if (stack == NULL)
    {
        free(stack);
        free(inDegree);
        return -1;
    }
    // 2.1、将初始化的入度为 0 的顶点编号压入栈，此点就是源点
    for (int i = 0; i < graph->nodeNum; i++)
    {
        if (inDegree[i] == 0)
        {
            stack[++top] = i;
            break; // 关键路径默认只有一个源点
        }
    }
    // 2.2、不断弹栈，不断更新入度记录表
    int tmp = 0; // 从栈上弹出的顶点编号
    int index = 0; // 记录排序结果的情况
    while (top != -1)
    {
        tmp = stack[top--];
        topOut[index++] = tmp;
        ArcEdge* edge = graph->nodes[tmp].firstEdge; // 取节点
        while (edge)
        {
            // 遍历出度
            --inDegree[edge->no];
            if (inDegree[edge->no] == 0)
            {
                // 若删除前一个节点后，后一个节点的入度为 0，那就入栈
                stack[++top] = edge->no;
            }
            // 此处为什么是大于，因为一个节点的前面的入度可能不一样，但因为此时记录的是最早时间，故我们需要等前面所有人都到才能开始行动。
            if (ETV[tmp] + edge->w > ETV[edge->no])
            {
                // 更新 ETV，看该结点的出度结点权值与原结点的 ETV 值相
                ETV[edge->no] = ETV[tmp] + edge->w;
            }
            edge = edge->next;
        }
    }
    free(inDegree);
    free(stack);
    if (index < graph->nodeNum)
    {
        // 有环
        free(topOut);
        return -1;
    }
    tmp = topOut[--index];
    // 3、更新 LTV
    for (int i = 0; i < graph->nodeNum; i++)
    {
        LTV[i] = ETV[tmp];
    }
    while (index)
    {
        int getTopNo = topOut[--index];
        ArcEdge* edge = graph->nodes[getTopNo].firstEdge;
        while (edge)
        {
            // 后一个节点的最早时间减该边的权值，就为该节点的最晚时间
            // 至于为什么是小于，是因为一定要保证前一个结点对于所有出度的情况均满足
            // 比如 0 到 2 的权值为 4，而到 2 的最晚时间却为 6，此时我们就会有 2 小时的闲鱼时间，也就是 0 的最晚开始时间是 2
            // But, 我们 0 到 1 的权值是 6 小时，而到 1 的最晚时间也是 6 小时，此时如果再将 0 从 2 小时开始，那么我们就会发现明显不能满足 1 的最晚时间
            // 故，我们需要考虑到每种情况，所以我们这边是小于。同上，大于也是此理
            if (LTV[edge->no] - edge->w < LTV[getTopNo])
            {
                LTV[getTopNo] = LTV[edge->no] - edge->w;
            }
            edge = edge->next;
        }
    }
    free(topOut);
}

static void showTable(int* table, int n, const char* name)
{
    printf("%s", name);
    for (int i = 0; i < n; i++)
    {
        printf(" %d", table[i]);
    }
    printf("\n");
}

void KeyPath(const AGraph* graph)
{
    // 1、计算顶点的 ETV 和 LTV
    int* ETV = malloc(sizeof(int) * graph->nodeNum);
    int* LTV = malloc(sizeof(int) * graph->nodeNum);
    memset(ETV, 0, sizeof(int) * graph->nodeNum);
    memset(LTV, 0, sizeof(int) * graph->nodeNum);
    topologicalOrder(graph, ETV, LTV);
    showTable(ETV, graph->nodeNum, "ETV: ");
    showTable(LTV, graph->nodeNum, "LTV: ");
    // 2、计算边的 ETE 和 LTE，直接输出关键路径
    for (int i = 0; i < graph->nodeNum; i++)
    {
        ArcEdge* edge = graph->nodes[i].firstEdge;
        while (edge)
        {
            // 每个边最早发生时间就是边的弧尾的 ETV
            // 每个边的最晚发生时间就是边的弧头的 LTV 减去当前的边权值
            if (ETV[i] == LTV[edge->no] - edge->w)
            {
                printf("<%s>---%d---<%s>\n", graph->nodes[i].show, edge->w, graph->nodes[edge->no].show);
            }
            edge = edge->next;
        }
    }
    free(ETV);
    free(LTV);
}

数据结构——图详解

图的概述

一、图的定义

二、图的相关概念

1、简单图

2、无向图

3、有向图

4、完全图

5、端点和邻接点

6、顶点的度、入度和出度

7、子图

8、路径和路径长度

9、回路或环

10、连通、连通图和连通分量

11、强连通图和强连通分量

12、稠密图、稀疏图

13、权和网

14、连通图的生成树

图的存储结构

一、邻接矩阵

无向图邻接矩阵：

有向图邻接矩阵：

带权图的邻接矩阵：

二、邻接表

无向邻接表：

有向邻接表：

带权网络的邻接表：

三、十字链表

四、邻接多重表

五、边集数组

图的遍历

一、DFS（深度优先算法）

1、邻接矩阵的 DFS

2、邻接表的 DFS

二、BFS（广度优先算法）

1、邻接矩阵的 BFS

2、邻接表的 BFS

最小生成树

一、Kruskal（克鲁斯卡尔）算法

二、Prim（普里姆）算法

最短路径

一、Dijkstra（迪杰斯特拉）算法

二、Floyd（弗洛伊德）算法

拓扑排序

一、定义

1、什么是 AOV 网

2、什么是拓扑序列

3、什么是拓扑排序

二、算法实现

关键路径

一、定义

1、什么是 AOE 网

2、关键路径

3、什么是 ETV

4、什么是 LTV

5、什么是 ETE

6、什么是 LTE

二、算法实现

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具