七. 图

作者: CoCc | 来源:发表于2023-02-07 10:22 被阅读0次

图七
唐末名家孙位《竹林七贤图》残卷欣赏，不愧是“逸格一人”！
小学生作品点评，题为“爱岗敬业”
守护成长中心第一周导图作业合辑
【古风】小寒三首
萧散漫寂秋雨后，深圳洪湖。
七老only护肤七老透肌,不美颜不P图也能白到一道光的秘诀在这!
俞孚书画系列：家居
感恩日记
设计模式

图的定义

图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V, E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

在图中数据元素称之为顶点。
在图结构中不允许没有顶点，若V是顶点的集合，则强调顶点集合V有穷非空。
在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

各种图定义

无向边：若顶点 v_i 到 v_j 之间的边没有方向，则称这条边，用无序偶对(v_i, v_j)来表示。
G = (V1, {E1}) V1 = {A, B, C, D} E1 = {(A, B), (B, C), (C, D), {D, A}, (A, C)}
有向边：若从顶点 v_i 到 v_j 的边有方向，则称这条边为有向边，也称为弧。用有序偶<v_i, v_j>来表示，v_i为弧尾，v_j为弧头。
G = (V1, {E1}) V1 = {A, B, C, D} E1 = {<A, D>, <B, A>, <C, A>, <B, C>}

若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n × (n - 1) / 2条边。
在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n × (n - 1)条边。
有很少条边或弧称为稀疏图，反之称为稠密图。
有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权。这种带权的图通常称为网。
路径的长度时路径上的边或弧的数目。
第一个顶点到最后一个顶点相同的路径称为回路或环。序列中顶点不重复的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

图的存储结构

邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组存储图中的边或弧的信息。

typedef char VertexType; // 顶点类型可自定义
typedef int EdgeType; // 边上的权值类型可自定义
#define MAXVEX 100 // 最大顶点数

typedef struct {
    VertexType vexs[MAXVEX]; // 顶点表
    EdgeType arc[MAXVEX][MAXVEX]; // 邻接矩阵，可看作边表
    int numVertexes, numEdges; // 图中当前的顶点数和边数
}MGraph;

/**
 建立无向网图的邻接矩阵表示

 @param G 邻接矩阵
 */
void CreateMGraph(MGraph *G) {
    
    int i, j, w;
    printf("输入顶点数和边数:\n");
    scanf("%d, %d", &G->numVertexes, &G->numEdges); //输入顶点数和边数
    for (int i = 0; i < G->numVertexes; i++) { //读入顶点信息，建立顶点表
        scanf("%c", &G->vexs[i]);
    }
    for (int i = 0; i < G->numVertexes; i++) {
        for (int j = 0; j < G->numVertexes; j++) {
            G->arc[i][j] = INFINITY; //邻接矩阵初始化
        }
    }
    for (int k = 0; k < G->numEdges; k++) { //读入numEdges条边，建立邻接矩阵
        printf("输入边(vi, vj)上的下标i，下标j和权w:\n");
        scanf("%d, %d, %d", &i, &j, &w); //输入边(vi, vj)上的权 w
        G->arc[i][j] = w;
        G->arc[j][i] = G->arc[i][j]; //因为是无向图，矩阵对称
    }
}

邻接表

typedef struct EdgeNode { //边表结点
    int adjvex; //邻接点域，存储该结点对应的下标
    EdgeType weight; //用于存储权值，对于非网图可以不需要
    struct EdgeNode *next; //链域，指向下一个邻接点
}EdgeNode;

typedef struct VertexNode { //顶点表结点
    VertexType data; //顶点域，存储顶点信息
    EdgeNode *firstedge; //边表头指针
}VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adhList;
    int numVertexes, numEdges; // 图中当前的顶点数和边数
}GraphAdjList;

/**
 建立图的邻接表结构

 @param G 邻接表
 */
void CreateALGraph(GraphAdjList *G) {
    int i, j, k;
    EdgeNode *e;
    printf("输入顶点数和边数:\n");
    scanf("%d, %d", &G->numVertexes, &G->numEdges);
    for (i = 0; i < G->numVertexes; i++) {
        scanf("%c", &G->adhList[i].data);
        G->adhList[i].firstedge = NULL;
    }
    
    for (k= 0; k < G->numEdges; k++) {
        printf("输入边(vi, vj)上的顶点序号:\n");
        scanf("%d, %d", &i, &j);
        
        e = (EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点
        e->adjvex = j; //邻接序号为j
        e->next = G->adhList[i].firstedge; //将e指针指向当前顶点指向的结点
        G->adhList[i].firstedge = e; //将当前顶点的指针指向e
        
        e = (EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点
        e->adjvex = i; ///邻接序号为i
        e->next = G->adhList[i].firstedge;
        G->adhList[i].firstedge = e;
    }
}

十字链表(有向图)

把邻接表与逆邻接表结合起来
边表结点结构

tailvex	headvex	headlink	tailink

其中tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。

邻接多重表(无向图)

边表结点结构

ivex	ilink	jvex	jlink

其中ivex和jvex是与某条边依附的两个顶点在顶点表中的下标。ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边。这就是邻接多重表结构。

图的遍历

深度优先遍历

也称为深度优先搜索，简称为DFS。
它从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径想通的顶点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

typedef int boolean; //boolean是布尔类型，其值是ture或false
boolean visited[MAXVEX]; //访问标志的数组

/* 邻接矩阵的深度优先递归算法 */
void DFS(MGraph G, int i) {
    visited[i] = true;
    printf("%c", G.vexs[i]);
    for (int j = 0; j < G.numVertexes; j++) {
        DFS(G, j);
    }
}

/* 邻接矩阵的深度遍历操作 */
void DFSTraverse(MGraph G) {
    for (int i = 0; i < G.numVertexes; i++) {
        visited[i] = false; //初始所有顶点状态都是未访问过状态
    }
    for (int i = 0; i < G.numVertexes; i++) {
        if (!visited[i]) { //对未访问的顶点调用DFS，若是连通图，只会执行一次
            DFS(G, i);
        }
    }
}

/* 邻接表的深度优先递归算法 */
void DFS(GraphAdjList GL, int i) {
    EdgeNode *p;
    visited[i] = true;
    printf("%c", GL.adhList[i].data);
    p = GL.adhList[i].firstedge;
    while (p) {
        if (!visited[p->adjvex]) {
            DFS(GL, p->adjvex);
        }
        p = p->next;
    }
}

/* 邻接表的深度遍历操作 */
void DFSTraverse(GraphAdjList GL) {
    for (int i = 0; i < GL.numVertexes; i++) {
        visited[i] = false;
    }
    for (int i = 0; i < GL.numVertexes; i++) {
        if (!visited[i]) {
            DFS(GL, i);
        }
    }
}

广度优先遍历

也称为广度优先搜索，简称BFS。

/* 邻接矩阵的广度遍历算法 */
void BFSTraverse(MGraph G) {
    Queue Q;
    for (int i = 0; i < G.numVertexes; i++) {
        visited[i] = false;
    }
    InitQueue(&Q);
    for (int i = 0; i < G.numVertexes; i++) {
        if (!visited[i]) {
            visited[i] = true;
            printf("%c", G.vexs[i]);
            EnQueue(&Q, i);
            while (!QueueEmpty(Q)) {
                DeQueue(&Q, &i);
                for (int j = 0; j < G.numVertexes; j++) {
                    if (G.arc[i][j] == 1 && !visited[j]) {
                        visited[j] = true;
                        printf("%c", G.vexs[j]);
                        DeQueue(&Q, &j);
                    }
                }
            }
        }
    }
}

/* 邻接表的广度遍历算法 */
void BFSTraverse(GraphAdjList GL) {
    EdgeNode *p;
    Queue Q;
    for (int i = 0; i < GL.numVertexes; i++) {
        visited[i] = false;
    }
    InitQueue(&Q);
    for (int i = 0; i < GL.numVertexes; i++) {
        if (!visited[i]) {
            visited[i] = true;
            printf("%c", GL.adhList[i].data);
            EnQueue(&Q, i);
            while (!QueueEmpty(Q)) {
                DeQueue(&Q, &i);
                p = GL.adhList[i].firstedge;
                while (p) {
                    if (!visited[p->adjvex]) {
                        visited[p->adjvex] = true;
                        printf("%c", GL.adhList[p->adjvex].data);
                        EnQueue(&Q, i);
                    }
                    p = p->next;
                }
            }
        }
    }
}

最小生成树

构造连通网的最小代价生成树称为最小生成树。
经典算法有Prim算法和Kruskal算法。

Prim算法

void MinSpanTree_Prim(MGraph G) {
    int min, i, j, k;
    int adjvex[MAXVEX]; //保存相关顶点下标
    int lowcost[MAXVEX]; //保存相关顶点顶点间边的权值
    lowcost[0] = 0; //初始化第一个权值为0，在这里j就是此下标的顶点已经加入生成树
    adjvex[0] = 0; //初始化第一个顶点下标为0
    for (i = 0; i < G.numVertexes; i++) { //循环除下标为0外的全部顶点
        lowcost[i] = G.arc[0][i]; //将0顶点与之有边的权值存入数组
        adjvex[i] = 0; //初始化
    }
    for (i = 0; i < G.numVertexes; i++) {
        min = INFINITY;
        j = 1;
        k = 0;
        while (j < G.numVertexes) { //循环全部顶点
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j]; //z让当前权值成为最小值
                k = j; //将当前最小值的下标存入k
            }
            j++;
        }
        printf("(%d, %d)", adjvex[k], k);
        lowcost[k] = 0; //将当前顶点的权值设为0，表示此顶点d已经完成任务
        for (i = 0; i < G.numVertexes; i++) { //循环全部顶点
            if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) { //若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值
                lowcost[j] = G.arc[k][j]; //将较小权值存入
                adjvex[j] = k; // //将下标为k的顶点存入
            }
        }
    }
}

时间复杂度为O(n²)

Kruskal算法

/* 查找连线顶点的尾部下标 */
int Find(int *parent, int f) {
    while (parent[f] > 0) {
        f = parent[f];
    }
    return f;
}

void MinSpanTree_Kruskal(MGraph G) {
    int i, begin, end;
    Edge edges[MAXVEX]; //定义边集数组
    int parent[MAXVEX]; //定义一数组用来判断边与边是否形成环路
    for (i = 0; i < G.numVertexes; i++) {
        parent[i] = 0;
    }
    for (i = 0; i < G.numEdges; i++) {
        begin = Find(parent, edges[i].begin);
        end = Find(parent, edges[i].end);
        if (begin != end) { //如果begin与end不等，说明此边没有与现有生成树形成环路
            parent[begin] = end; //将此边的结尾顶点放入下标为起点的parent中，表示此顶点已经咋生成树集合中
            printf("(%d, %d) %d,", edges[i].begin, edges[i].end, edges[i].weight);
        }
    }
}

时间复杂度为O(e㏒e)

Kruskal算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势；而Prim算法对于稠密图，即边数非常多的情况会更好。

最短路径

对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。

Dijkstra算法

#define MAXVEX 9 //最大顶点数
typedef int Patharc[MAXVEX]; //用于存储最短路径下标的数组
typedef int ShortPathTable[MAXVEX]; //用于存储到各点最短路径的权值和

// P[v]的值为前驱顶点下标，D[v]表示v0到v的最短路径长度和
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P) {
    int v, w, k = 0, min = 0;
    int final[MAXVEX];
    ShortPathTable *D = NULL;
    for (v = 0; v < G.numVertexes; v++) { //初始化数据
        final[v] = 0;
        (*D)[v] = G.arc[v0][v];
        (*P)[v] = 0;
    }
    (*D)[v0] = 0;
    final[v0] = 1; //这两句都是v0-v0的路径
    for (v = 1; v < G.numVertexes; v++) {
        min = INFINITY;
        for (w = 0; w < G.numVertexes; w++) {
            if (!final[w] && (*D)[w] < min) {
                k = w;
                min = (*D)[w]; //w顶顶啊离v0顶点更近
            }
        }
        final[k] = 1; //将目前找到的最近的顶点为1
        for (w = 0; w < G.numVertexes; w++) { //修正当前最短路径及距离
            if (!final[w] && (min + G.arc[k][w] < (*D)[w])) { //如果经过v顶点的路径比现在这条路径的路径长度短的话
                (*D)[w] = min + G.arc[k][w]; //修改当前路径长度
                (*P)[w] = k;
            }
        }
    }
}

Floyd算法

如果要求所有顶点至所有顶点的最短路径问题时，可以使用Floyd

typedef int Pathmatirx[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];

void ShortestPath_Floyd(MGraph G, Pathmatirx *P, ShortPathTable *D) {
    int v, w = 0, k;
    for (v = 0; v < G.numVertexes; v++) {
        (*D)[v][w] = G.arc[v][w]; //D[v][w]值即为对应点间的权值
        (*P)[v][w] = w; //初始化P
    }
    for (k = 0; k < G.numVertexes; k++) {
        for (v = 0; v < G.numVertexes; v++) {
            for (w = 0; w < G.numVertexes; w++) {
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) { //如果经过下标为k顶点路径比原两点间l路径更短
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w]; //将当前两点间权值设为更小的一个
                    (*P)[v][w] = (*P)[v][k]; //路径设置经过下标为k的顶点
                }
            }
        }
    }
}

拓扑排序

无环图
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，称为AOV网。
对一个有向图构造拓扑序列的过程。构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环的AOV网了；如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环，不是AOV网。

typedef struct EdgeNode { //边表结点
    int adjvex; //邻接j点域，存储该顶点对应的下标
    int weight; //用于存储权值，对于非网图可以x不需要
    struct EdgeNode *next; //链域，指向下一个邻接点
}EdgeNode;

typedef struct VertexNode { //顶点表结点
    int in; //顶点入度
    int data; //顶点域，存储顶点信息
    EdgeNode *firstedge; //边表头指针
}VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    int numVertexes, numEdges;
}graphAdjList, *GraphAdjList;

Status TopologicalSort(GraphAdjList GL) {
    EdgeNode *e;
    int i, k, gettop;
    int top = 0; //用于栈指针下标
    int count = 0; //用于d统计输出顶点的个数
    int *stact; //建栈存储输入度为0的顶点
    stact = (int*)malloc(GL->numVertexes * sizeof(int));
    for (i = 0; i < GL->numVertexes; i++) {
        if (GL->adjList[i].in == 0) {
            stact[++top] = i; //将入度为0的顶点入栈
        }
    }
    while (top != 0) {
        gettop = stact[--top]; //出栈
        printf("%d ->", GL->adjList[gettop].data);
        count++;
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) { //对此顶点弧表遍历
            k = e->adjvex;
            if (!(--GL->adjList[k].in)) { //将K号顶点邻接i点的入度为1
                stact[++top] = k; //若为0则入栈，以便于下次循环输出
            }
        }
    }
    if (count < GL->numVertexes) { //如果count小于顶点树，说明存在环
        return ERROR;
    } else {
        return OK;
    }
}

关键路径

在一个表示工程的带权有向图中，用顶点表示时间，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，称之为AOE网。
路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫做关键路径，在关键路径上的活动叫关键活动。

int *etv, *ltv; //时间最早发生时间和最迟发生时间数组
int *stack2; //用于存储拓扑序列的栈
int top2; //t用于stack2的指针

Status TopologicalSort(GraphAdjList GL) {
    EdgeNode *e;
    int i, k, gettop;
    int top = 0; //用于栈指针下标
    int count = 0; //用于d统计输出顶点的个数
    int *stact; //建栈存储输入度为0的顶点
    stact = (int*)malloc(GL->numVertexes * sizeof(int));
    for (i = 0; i < GL->numVertexes; i++) {
        if (GL->adjList[i].in == 0) {
            stact[++top] = i; //将入度为0的顶点入栈
        }
    }
    top2 = 0;
    etv = (int*)malloc(GL->numVertexes * sizeof(int));
    for (i = 0; i < GL->numVertexes; i++) {
        etv[i] = 1;
    }
    stack2 = (int*)malloc(GL->numVertexes * sizeof(int));
    while (top != 0) {
        gettop = stact[--top]; //出栈
        printf("%d ->", GL->adjList[gettop].data);
        count++;
        stack2[++top2] = gettop; //将弹出的顶点序号压入拓扑序列的栈
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) { //对此顶点弧表遍历
            k = e->adjvex;
            if (!(--GL->adjList[k].in)) { //将K号顶点邻接i点的入度为1
                stact[++top] = k; //若为0则入栈，以便于下次循环输出
            }
            if (etv[gettop] + e->weight > etv[k]) { //求各顶点时间最早发生时间值
                etv[k] = etv[gettop] + e->weight;
            }
        }
    }
    if (count < GL->numVertexes) { //如果count小于顶点树，说明存在环
        return ERROR;
    } else {
        return OK;
    }
}

void CriticalPath(GraphAdjList GL) {
    EdgeNode *e;
    int i, gettop, k, j;
    int ete, lte;
    TopologicalSort(GL);
    ltv = (int*)malloc(GL->numVertexes * sizeof(int));
    for (i = 0; i < GL->numVertexes; i++) {
        ltv[i] = etv[GL->numVertexes];
    }
    while (top2 != 0) {
        gettop = stack2[top2--]; //将拓扑序列出栈，后进先出
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
            k = e->adjvex;
            if (ltv[k] - e->weight < ltv[gettop]) { //求各顶点事件最晚发生时间
                ltv[gettop] = ltv[k] - e->weight;
            }
        }
    }
    for (j = 0; j < GL->numVertexes; i++) {
        for (e = GL->adjList[i].firstedge; e; e = e->next) {
            k = e->adjvex;
            ete = etv[j]; //活动最早发生时间
            lte = ltv[k] - e->weight; //活动最晚发生时间
            if (ete == lte) { //若相等jj就在关键路径上
                printf("<v%d, v%d> length: %d", GL->adjList[i].data, GL->adjList[k].data, e->weight);
            }
        }
    }
}

图七
针线盒：母亲的艺术，是一针一线里的爱
唐末名家孙位《竹林七贤图》残卷欣赏，不愧是“逸格一人”！
《高逸图》，又名《竹林七贤图》，是唐末书画家孙位（别名孙遇、会稽山人）的作品。顾名思义，《竹林七贤图》应该有七贤，...
小学生作品点评，题为“爱岗敬业”
图一图二图三图四图五图六图七图八图九图十图十一图十二图十三图十四图十五图十六以上这...
守护成长中心第一周导图作业合辑
七副导图幸福的方法代替刻意练习导图
【古风】小寒三首
文/海煦图/网图（一）七绝小寒虚弱无心揽， ...
萧散漫寂秋雨后，深圳洪湖。
拍摄: Alan 每图七字: Alan
七老only护肤七老透肌,不美颜不P图也能白到一道光的秘诀在这!
七老only护肤七老透肌,不美颜不P图也能白到一道光的秘诀在这! 七老only护肤七老透肌,不美颜不P图也能白到一...
俞孚书画系列：家居
客厅效果图一客厅效果图二客厅效果图三客厅效果图四书房效果图五书房效果图六餐厅效果图七卧...
感恩日记
感恩今天首席重新分享的七张图，让我重新有了一个思路，七张图是练习技能，七习惯是培养我的心力，心力加能力等于成功！一...
设计模式
准备篇UML类图UML序列图七大原则开闭原则

七. 图

图的定义

各种图定义

图的存储结构

邻接矩阵

邻接表

十字链表(有向图)

邻接多重表(无向图)

图的遍历

深度优先遍历

广度优先遍历

最小生成树

Prim算法

Kruskal算法

最短路径

Dijkstra算法

Floyd算法

拓扑排序

关键路径

相关文章

图七

唐末名家孙位《竹林七贤图》残卷欣赏，不愧是“逸格一人”！

小学生作品点评，题为“爱岗敬业”

守护成长中心第一周导图作业合辑

【古风】小寒三首

萧散漫寂秋雨后，深圳洪湖。

七老only护肤七老透肌,不美颜不P图也能白到一道光的秘诀在这!

俞孚书画系列：家居

感恩日记

设计模式

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读