数据结构复习笔记（图）

图的存储

邻接矩阵法

存储空间：顶点信息O(n)，加上边信息（邻接矩阵）O(n^2)，即O(n^2)。

#define MaxVertexNum 100    // 顶点数目的最大值
typedef char VertexType;    // 顶点的数据类型
typedef int EdgeType;        // 带权图中边上权值的数据类型

typedef struct {
    VertexType Vex[MaxVertexNum];                // 顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];    // 邻接矩阵
    int vexnum;        // 顶点数
    int arcnum;        // 弧数
}Graph;

邻接表法

存储空间：存储顶点表，加上边表。无向图为O(|V|+2|E|)，有向图为O(|V|+|E|)。

#define MaxVertexNum 100    // 顶点数目的最大值
typedef char VertexType;    // 顶点的数据类型

// 边表
typedef struct ArcNode {
    int adjvex;                // 该弧所指向的顶点的位置
    struct ArcNode* next;    // 指向下一条弧的指针
    //InfoType info;        // 网的边权值
}ArcNode;

// 顶点表
typedef struct VNode {
    VertexType data;    // 顶点信息
    ArcNode* first;        // 指向第一条依附该顶点的弧的指针
}VNode, AdjList[MaxVertexNum];

// 邻接表
typedef struct {
    AdjList vertices;    // 图的顶点数组
    int vexnum;            // 顶点数
    int arcnum;            // 弧数
}LGraph;

图的遍历

基本操作

求图G中顶点v的第一个邻接顶点（基于邻接矩阵）。

// 返回顶点v的第一个邻接顶点的索引，失败返回-1
int FirstNeighbor(Graph G, int v)
{
    int i;
    if (v < 0 || v >(G.vexnum - 1))
        return -1;
    for (i = 0; i < G.vexnum; i++)
    {
        if (G.Edge[v][i] == 1)
            return i;
    }
    return -1;
}

求图G中顶点v基于w的下一个邻接顶点（基于邻接矩阵）。

// 返回顶点v相对于w的下一个邻接顶点的索引，失败返回-1
int NextNeighbor(Graph G, int v, int w)
{
    int i;
    if (v < 0 || v >(G.vexnum - 1) || w < 0 || w >(G.vexnum - 1))
        return -1;
    for (i = w + 1; i < G.vexnum; i++)
    {
        if (G.Edge[v][i] == 1)
            return i;
    }
    return -1;
}

广度优先搜索

空间复杂度：O(|V|)，借助辅助队列。

时间复杂度：邻接矩阵O(|V|+|E|)，邻接表O(|V|^2)。

基于邻接矩阵的广度优先遍历算法如下。

int visited[MaxVertexNum];    // 辅助标记数组
int queue[MaxVertexNum];    // 辅助队列
int rear, head;                // 辅助队列头尾指针

// 从顶点v出来，广度优先遍历图G
void BFS(Graph G, int v)
{
    visited[v] = 1;        // 标记v已访问
    printf("%c ", G.Vex[v]);
    queue[rear++] = v;    // 入队列
    int j, w;
    while (head != rear)
    {
        j = queue[head++];    // 出队列
        for (w = FirstNeighbor(G, j); w >= 0; w = NextNeighbor(G, j, w))
        {
            if (!visited[w])
            {
                // 访问顶点w，并将w入队列
                visited[w] = 1;
                printf("%c ", G.Vex[w]);
                queue[rear++] = w;
            }
        }
    }
}

void BFSTraverse(Graph G)
{
    // 访问标记数组初始化
    for (int i = 0; i < G.vexnum; i++)
    {
        visited[i] = 0;
    }
    // 从0号顶点开始遍历，对每一个连通分量调用一次BFS
    for (int i = 0; i < G.vexnum; i++)
    {
        if (!visited[i])
        {
            BFS(G, i);
        }
    }
}

void main()
{
    Graph* pG;
    pG = create_example_graph();    // 创建图
    BFSTraverse(*pG);               // 广度优先遍历
}

深度优先搜索

空间复杂度：O(|V|)，借助递归工作栈。

时间复杂度：邻接矩阵O(|V|+|E|)，邻接表O(|V|^2)。

基于邻接矩阵的深度优先遍历算法如下。

int visited[MaxVertexNum];    // 辅助标记数组

// 从顶点v出发，深度优先遍历图G
void DFS(Graph G, int v)
{
    visited[v] = 1;
    printf("%c ", G.Vex[v]);
    for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
    {
        if (!visited[w])
            DFS(G, w);
    }
}

void DFSTraverse(Graph G)
{
    // 访问标记数组初始化
    for (int i = 0; i < G.vexnum; i++)
    {
        visited[i] = 0;
    }
    for (int i = 0; i < G.vexnum; i++)
    {
        if (!visited[i])
        {
            DFS(G, i);
        }
    }
}

void main()
{
    Graph* pG;
    pG = create_example_graph();
    DFSTraverse(*pG);               // 深度优先遍历
}

图的应用

最小生成树

求最小生成树基于贪心策略的两个方法：

Prim（普里姆）算法
Kruskal（克鲁斯卡尔）算法

Prim

要点：每次选取一个距离最短的顶点，执行过程类似于Dijkstra算法。

时间复杂度：不依赖边，适合求解边稠密的图的最小生成树。总的时间复杂度为O(|V|^2)。

Kruskal

要点：将所有边按权值由小到大排序，每次选取权值最小的一条边，直至将每个顶点都连通。

时间复杂度：每次选取最小权值的边（使用并查集）需要O(log2|E|)。总的时间复杂度为O(|E|log2|E|)。

最短路径

单源最短路径：BFS、Dijkstra。

每对顶点之间的最短路径：Floyd。

BFS算法（无权图）

与BFS遍历算法差不多。不同之处是，在BFS中访问一个顶点时，修改路径长度dist数组，并在path数组记录前驱顶点。

Dijkstra算法（带权，无权）

要点：

集合S记录已经确定最短路径的顶点，初始把源点放入S中。
dist数组记录从源点到其他顶点当前的最短路径长度。
path数组记录从源点到其他顶点的最短路径的前驱顶点。

时间复杂度：O(|V|^2)

每轮遍历顶点，找到还未确定的最短路径，且dist最小的顶点，需要o(|V|)。
每轮检查所有邻接自vi的顶点，更新dist，需要O(|V|)。
共n-1轮。需要O(|V|-1)。

注意：

Dijkstra算法也可以求每对顶点之间的最短路径。
边上带有负权值时，Dijkstra算法不适用。

Floyd（带权，无权）

要点：依次画出A(k-1)的方阵，k=0，1，2，…，n代表每次允许中转的顶点，并依次更新path(k-1)，获得各顶点之间的最短路径。

空间复杂度：O(|V|^2)

时间复杂度：O(|V|^3)，三个for循环

注意：Floyd算法允许图中带负权值的边，但不允许有包含带负权值的边组成的回路。

有向无环图（DAG图）

解题方法：

把各个操作数不重复地排成一排
标出各个运算符的生效顺序
按顺序加入运算符，注意分层
自底向上，逐层检查同层的运算符，是否可以合体

拓扑排序

AOV网：顶点表示活动的网络，V代表顶点。

常用方法：

从AOV网中选择一个没有前驱的顶点并输出。
从网中删除该顶点和所有以它为起点的有向边。
重复步骤1和2，直到当前的AOV网为空，或当前网中不存在无前驱的顶点为止（存在环）。

时间复杂度：邻接表为O(|V|+|E|)，邻接矩阵为O(|V|^2)。

基于邻接表存储的有向图的拓扑排序算法如下。

// 创建邻接表对应的有向图
LGraph* create_example_lgraph()
{
    char c1, c2;
    char vexs[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
    char edges[][2] = {
        { 'A', 'G' },
        { 'B', 'A' },
        { 'B', 'D' },
        { 'C', 'F' },
        { 'C', 'G' },
        { 'D', 'E' },
        { 'D', 'F' }
    };
    int vlen = LENGTH(vexs);
    int elen = LENGTH(edges);

    int i, p1, p2;
    ENode* node1, * node2;
    LGraph* pG;

    if ((pG = (LGraph*)malloc(sizeof(LGraph))) == NULL)
        assert(pG != NULL);
    memset(pG, 0, sizeof(LGraph));

    // 初始化顶点数和边数
    pG->vexnum = vlen;
    pG->edgnum = elen;
    pG->vexs = (VNode*)malloc(pG->vexnum * sizeof(VNode));
    assert(pG->vexs != NULL);

    // 初始化邻接表的顶点
    for (i = 0; i < pG->vexnum; i++)
    {
        pG->vexs[i].data = vexs[i];
        pG->vexs[i].first_edge = NULL;
    }

    // 初始化邻接表的边
    for (i = 0; i < pG->edgnum; i++)
    {
        c1 = edges[i][0];
        c2 = edges[i][1];
        p1 = get_position(*pG, c1);
        p2 = get_position(*pG, c2);

        // 初始化node1
        node1 = (ENode*)malloc(sizeof(ENode));
        node1->ivex = p2;
        node1->next_edge = NULL;    // 一定要加这个，不然link_last里面会报错
        // 将node1链接到p1所在链表的末尾
        if (pG->vexs[p1].first_edge == NULL)
            pG->vexs[p1].first_edge = node1;
        else
            link_last(pG->vexs[p1].first_edge, node1);
    }

    return pG;
}

/// <summary>
/// 拓扑排序算法
/// </summary>
/// <param name="G">邻接表有向图</param>
/// <returns>
/// -1 -- 失败，由于内存不足等原因导致
///  0 -- 成功排序，并输出结果
///  1 -- 失败，存在回路
/// </returns>
int topological_sort(LGraph G)
{
    int i, j;
    int index = 0;    // 计算排序数组的顶点数
    int head = 0;    // 辅助队列的头
    int rear = 0;    // 辅助队列的尾
    int* queue;        // 辅助队列
    int* ins;        // 入度数组
    char* tops;        // 拓扑排序结果数组，记录每个结点排序后的序号
    int num = G.vexnum;
    ENode* node;

    ins = (int*)malloc(num * sizeof(int));        // 入度数组
    tops = (char*)malloc(num * sizeof(char));    // 拓扑排序结果数组
    queue = (int*)malloc(num * sizeof(int));    // 辅助队列
    assert(ins != NULL && tops != NULL && queue != NULL);
    memset(ins, 0, num * sizeof(int));
    memset(tops, 0, num * sizeof(char));
    memset(queue, 0, num * sizeof(int));

    // 统计每个顶点的入度数
    for (i = 0; i < G.vexnum; i++)
    {
        node = G.vexs[i].first_edge;
        while (node != NULL)        // 遍历每个顶点的出边顶点
        {
            ins[node->ivex]++;        // 增加该出边顶点的入度
            node = node->next_edge;
        }
    }

    // 将所有入度为0的顶点入队列
    for (i = 0; i < num; i++)
    {
        if (ins[i] == 0)
            queue[rear++] = i;
    }

    while (rear != head)
    {
        j = queue[head++];                // 出队列
        tops[index++] = G.vexs[j].data;    // 将该顶点添加到排序数组中
        node = G.vexs[j].first_edge;    // 获取以该顶点为起始顶点的出边队列

        // 将与出队顶点关联的所有出边顶点的入度-1
        // 若-1之后，该顶点的入度为0，则将该顶点入队
        while (node != NULL)
        {
            ins[node->ivex]--;            // 将出队顶点的出边顶点的入度-1
            if (ins[node->ivex] == 0)    // 若-1后入度为0，则入队
                queue[rear++] = node->ivex;
            node = node->next_edge;        // 继续寻找下一条出边顶点
        }
    }

    if (index < G.vexnum)
    {
        printf("拓扑排序失败，存在回路");
        free(queue);
        free(ins);
        free(tops);
        return 1;
    }

    // 打印拓扑排序结果
    printf("拓扑排序结果：");
    for (i = 0; i < num; i++)
    {
        printf("%c ", tops[i]);
    }
    printf("\n");

    free(queue);
    free(ins);
    free(tops);
    return 0;
}

void main()
{
    LGraph* pG;
    pG = create_example_lgraph();
    topological_sort(*pG);  // 拓扑排序
}

利用DFS实现基于邻接表的有向无环图的拓扑排序。

void DFS(LGraph G, int  i, int* visited, int* time, int* finishTime)
{
    int w;
    ENode* node;

    visited[i] = 1;
    printf("%c ", G.vexs[i].data);
    node = G.vexs[i].first_edge;
    while (node != NULL)
    {
        if (!visited[node->ivex])
            DFS(G, node->ivex, visited, time, finishTime);
        node = node->next_edge;
    }
    (*time)++;
    finishTime[i] = (*time);    // 记录完成时间，时间大的一定先执行
}

topological_dfs(LGraph G)
{
    int i;
    int visited[MaxVertexNum];        // 顶点访问标记
    int time = 0;
    int finishTime[MaxVertexNum];    // 记录每个顶点DFS的完成时间

    // 初始化所有顶点都没有被访问
    for (i = 0; i < G.vexnum; i++)
    {
        visited[i] = 0;
        finishTime[i] = -1;        // 初始化finishTime数组
    }

    printf("DFS遍历:");
    for (i = 0; i < G.vexnum; i++)
    {
        if (!visited[i])
            DFS(G, i, visited, &time, finishTime);
    }
    printf("\n");

    printf("DFS实现的拓扑排序:");
    for (i = G.vexnum; i > 0; i--)    // 按结束时间从大到小，可以得到一个拓扑排序
    {
        for (int j = 0; j < G.vexnum; j++)
        {
            if (i == finishTime[j])
            {
                printf("%c ", G.vexs[j].data);
                break;
            }
        }
    }
}

void main()
{
    LGraph* pG;
    pG = create_example_lgraph();
    topological_dfs(*pG);    // DFS实现拓扑排序
}

注意：DFS遍历中，若在顶点退栈前输出顶点，可以得到逆拓扑排序序列。

关键路径

AOE网：用边表示活动的网络，E代表边。

AOE网和AOV网都是有向无环图，但是AOE网的边有权值，AOV网的边没有权值。

从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动。完成整个工程最短时间就是关键路径的长度。

求关键路径步骤

事件最早发生时间：每个顶点的最早发生时间，从前往后推。
事件最迟发生时间：从后往前推。
活动最早开始时间：等于该弧的起点表示的事件的最早发生时间。
活动最迟开始时间：等于该弧的终点表示的事件的最迟发生时间减去该弧的持续时间。
时间余量：等于活动最迟开始时间减去活动最早开始时间，若结果为0，则活动为关键活动。

关键路径特点：

可以通过加快关键活动来缩短整个工程的工期。
但不能任意缩短关键活动，一旦缩短到一定的程度，该关键活动就可能变成非关键活动。
只有加快那些包括在所有关键路径上的关键活动，才能达到缩短工期的目的。

图的存储
1. 邻接矩阵法
2. 邻接表法
图的遍历
图的应用