Wx::

  • 分类:
    • 无向图 UDG
    • 无向网 UDN(即顶点之间的弧带有权值的无向图)
    • 有向图 DG (弧带有方向)
    • 有向网 DN (即顶点之间的弧带有权值的有向图)

存储结构

详细:-brev-

分为如下两种:

数组表示法

即采用一维数组存储图中顶点,采用矩阵存储点与点之间的弧关系

#define MAX_VERTEX_NUM 20 // 最大顶点数为 20
typedef struct ArcCell {
    VRType adj; // 顶点关系类型,对无权图,该类型为 int,值为 0 or 1
    InfoType *info; // 该弧相关信息的指针(算法简单时可不用)
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
    VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量(数组)
    AdjMatrix arcs; // 邻接矩阵
    int vexnum, arcnum;
    GraphKind kind; // 图的种类
}MGraph;

例:

顶点:[v1, v2, v3, v4, v5]
弧:

$G.arcs = \begin{bmatrix}0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&1&0&0\\0&0&1&0&0\\\end{bmatrix}$

此时:v1 与 v2,v2 与 v3,等顶点之间存在弧


邻接表表示法

即采用一维数组,数组元素为头结点:拥有两个成员(顶点值、指向以该顶点为尾端的第一条弧的指针),以表节点存储弧,其成员为:该弧的头部顶点的序号、指向下一条与此弧同尾端的弧的指针、其他信息(如权值)

typedef char VertexType; // 此处顶点值设为字符型

#define MAX_VERTEX_NUM 20

typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
    int info; // 每条弧的权值
}ArcNode; // 表节点(即弧节点)

typedef struct VNode {
    VertexType data;
    ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM]; // 头结点(存储顶点信息)

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
    int kind; // 分为 DG - 1, DN - 2, UDG - 3, UDN - 4,此处建立有向网结构,kind 值为 2
}ALGraph; // 整个邻接表

其他表示法

  • 十字链表
  • 邻接多重表

以下代码如无特殊说明则以邻接表表示法的有向网演示算法。

over

遍历

  • 分类:
    • 深度优先搜 DFS
    • 广度优先搜 BFS

深度优先搜索

  • 优先向下(更深处)进行遍历
  • 可检测是否为连通图(见代码中注释)
Status DFSTraverse_DN(ALGraph *G, Status(*visitFunc)(VertexType e)) {
    // 需要借助 visited 数组来确定某定点是否遍历过,FALSE 表示该顶点未被遍历
    Status *visited = (Status*)malloc(G->vexnum * sizeof(int));
    for (int i = 0; i < G->vexnum; i++) { // 初始化 visited 数组
    	visited[i] = FALSE;
    }
    visit = visitFunc; // visit 为全局函数指针变量,可通过对其赋值以在递归调用中使用不同的访问函数,并非必需
    for (int i = 0; i < G->vexnum; i++) {
    	if (!visited[i]) {
            // 每次进入该判断时可通过增加一个变量来计数以检测是否为连通图
    	    DFS_DN(G, i, visited); // 调用 DFS_DN,以第 i 个顶点为起点开始深搜
    	}
    }
    return OK;
}

Status DFS_DN(ALGraph *G, int v, Status *visited) {
    visited[v] = TRUE;
    visit(G->vertices[v].data); // 访问该顶点数据
    for (ArcNode *w = G->vertices[v].firstarc; w != NULL; w = w->nextarc) {
        // 开始遍历该顶点后的表节点,并以第一个未被遍历过的表节点顶点继续深搜
    	if (!visited[w->adjvex]) {
    	    DFS_DN(G, w->adjvex, visited);
    	}
    }
    return OK;
}


广度优先搜索

  • 优先遍历同层级的顶点
  • 时间复杂度与深搜相同
  • 可用来求出非加权图中任两点的最短路径(未作演示)
Status BFSTraverse_DN(ALGraph *G, Status(*visit)(VertexType e)) {
    // 广度优先遍历有向网:
    // (用到了队列概念)
    Status *visited = (Status*)malloc(G->vexnum * sizeof(int));
    for (int i = 0; i < G->vexnum; i++) {
    	visited[i] = FALSE;
    }
    int temp; // 暂存 DeQueue 出的顶点的序号
    ArcNode *tempP; // 暂存邻接表中 ArcNode 指针
    SqQueue Q;
    InitQueue(&Q);

    // 开始遍历:
    // 原理:每次对未被访问过的节点进行访问并将其对应的 visited 数组中值置为 TRUE,并将期入队,
    //       当队列不为空时,每出队一个元素,对其邻接点进行访问并入队,
    for (int i = 0; i < G->vexnum; i++) {
    	if (!visited[i]) {
    	    visited[i] = TRUE;
    	    visit(G->vertices[i].data);
    	    EnQueue(&Q, i); // 将访问过的顶点入队列
    	    while (!QueueEmpty) {
    	    	DeQueue(&Q, &temp); // 将最前端顶点出队列以入其邻接的下一层顶点
    	    	tempP = G->vertices[temp].firstarc;
    	    	while (tempP) {
    	    	    visited[tempP->adjvex] = TRUE;
    	    	    visit(G->vertices[tempP->adjvex].data);
    	    	    EnQueue(&Q, tempP->adjvex);
    	    	    tempP = tempP->nextarc;
    	    	}
    	    }
    	}
    }
    return OK;
}

生成树

  • 分类:
    • 深度优先生成树(略)
    • 广度优先生成树(略)
    • 最小生成树

最小生成树

MST 性质:设 G = (V,E)是一个连通网,U 是顶点集 V 的一个非空真子集。若 (u,v) 是一条 “一个端点在 U 中(例如:u ∈ U),另一个端点不在 U 中(例如:v ∈ V - U)” 的边,且 (u,v) 具有最小权值,则一定存在 G 的一棵最小生成树包括此边 (u,v)。

利用此性质,有如下两算法

Prim(普里姆)算法

  • 思想 :以某定点(如 v1)开始,设 v1 处于顶点集 V 的一个非空子集 U 中,找到从 v1 到 V-U 中某顶点的弧,该弧权值最小,将此弧计入最小生成树,将此顶点并入 U,继续寻找从 U 中某定点到 V-U 中某定点的弧,该弧权值最小,直到全部顶点并入 U,此时生成最小生成树。

  • 实现 :设初始数据记录在邻接数组中,某顶点到自身的权值为 0,到不可达到的顶点权值为无穷大,借助辅助数组 closedge(元素为成员为 顶点adjvex 和 弧长lowcost 的结构体),以某顶点(如 v1)和其到各顶点的弧长(权值)初始化该数组,找出其中最小的弧长,将该弧计入最小生成树,将该弧的头顶点 v' 计入 U,注意更改邻接数组中至 v' 的所有弧权值为 0,以 v' 开始遍历到 V-U 中顶点的所有弧,若弧长小于现在 closedge 数组中到该顶点的弧长,则替换,然后继续寻找 closedge 中弧长最小但不为 0 的顶点,以此顶点继续遍历...

  • 除初始化,共查找 v-1 次,v 为总顶点数。

int G[M][N]; // 存图

void MiniSpanTree_PRIM(int u){
    // 传入参数 G 为该网(带权图)的邻接矩阵(u*u),共有顶点 u 个,默认从第 0 个顶点开始生成
    // 需要辅助数组 closedge 来存当前的最短的到达各点的路权值和起止点

    typedef struct {
        int adjvex; // 起点
        int lowcost; // 权值
    }Closedge;

    Closedge *closedge = (Closedge*)malloc(sizeof(Closedge) * u);

    for(int i = 0; i < u; i++){
        closedge[i].adjvex = 0;
        closedge[i].lowcost = G[0][i]; // 相当于 G[0][i]
    }

    for(int i = 1; i < u; i++){
        int minV = 0; // 记录当前最短的路径的头顶点以便下一次遍历
        int min = 99999; // 当前最短路径的权值
        for(int j = 0; j<u;j++){
            if(closedge[j].lowcost < min && closedge[j].lowcost != 0){
                minV = j;
                min = closedge[j].lowcost;
            }
        }
        printf("road %d: v%d - v%d, weight: %d\n",i, closedge[minV].adjvex+1, minV+1, closedge[minV].lowcost);
        closedge[minV].lowcost = 0; // 将 minV 点并入最小生成树的点

        for(int j = 0; j < u; j++){
            if(G[minV][j] < closedge[j].lowcost && G[minV][j] != 0){
                closedge[j].adjvex = minV;
                closedge[j].lowcost = G[minV][j];
            }
        }
    }
}


Kruskal(克鲁斯卡尔)算法


三项应用

  • 拓扑排序
  • 关键路径
  • 最短路径
    • 定源点最短路径
    • 各顶点之间最短路径

拓扑排序

判断图中是否存在环
涉及 栈的应用,此处直接调用 c++ 的 <stack>

  • 思想:
    • 找出没有前驱的顶点并输出
    • 删除该顶点及以它为尾的弧
    • 重复上述过程,直至全部顶点输出(此时无环)或当前不存在无前驱的顶点(此时存在环)
int TopologicalSort(int *G, int n) {
    // 传入用邻接矩阵(暂用一维数组存)存储的有 n 个顶点的图 G,顶点编号为 0 - n-1
    // 邻接矩阵中,存在弧的两顶点间权值为 1,否则为 0
    stack <int>stk; // 初始化栈
    int *indegree = (int *)malloc(sizeof(int)*n); // 记录每个顶点的入度

    // 找出每个顶点的入度,并将入度为 0 的顶点入栈以存储:
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < n; j++) {
            sum += *(G + j*n + i); // 将第 i 列的值(G[0][i] - G[n-1][i])相加
        }
        if (sum == 0) {
            indegree[i] = 0;
            stk.push(i);
        }
        else {
            indegree[i] = sum;
        }
    }

    int temp = 0; // 记录刚刚出栈的顶点(入度为 0)以删除以其为尾的弧
    while (!stk.empty()) {
        temp = stk.top();
        stk.pop();
        cout << temp << endl; // 按序一次输出拓扑排序的顶点
        for (int i = 0; i < n; i++) {
            if (*(G + n*temp + i)) { // 如果顶点 temp 到 i 有弧(G[temp][i]不为 0)
                if (!(--indegree[i])) { // i 的入度减 1,且判断其入度是否变为 0
                    stk.push(i);
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (indegree[i]) {
            cout << "存在环" << endl;
            return 0;
        }
    }
    cout << "不存在环" << endl;
    return 1;
}

关键路径

  • 待填

最短路径

  • 待填
368

评论(0

评论 取消
验证码:
搜索