【数据结构】图算法

小梁要努力哟

1191人浏览 · 2022-10-31 19:31:38

小梁要努力哟 · 2022-10-31 19:31:38 发布

实验内容

功能
图的邻接表定义及创建
无向图上实现深度优先算法
无向图上实现广度优先遍历算法
有向无环图上实现拓扑排序算法

数据结构定义

在这里插入图片描述

算法思想及算法设计

（1） 图的邻接表表示法创建（以无向图为例）
图的邻接表表示法类似于树的孩子链表表示法。对于图G中的每个顶点vi,该方法把所有邻接于vi的顶点vj链成一个带头节点的单链表，这个单链表就称为顶点vj的邻接表。单链表中的每个结点至少包含两个域，一个为邻接点域,它指示与顶点vi邻接的顶点在图中的位序；另一个为链域，它指示与顶点vi邻接的下一个节点。在每个链表上需附设一个表头结点，在表头结点中，除了设有头指针域(firstedge)指向链表中的第一个结点之外，还设有存储顶点vi的数据域(vertex)或其他有关信息的数据域。
在创建的过程，首先要输入该图所拥有的顶点数和边数，之后依次输入依附于一条边的顶点，因为为无向图，所以只输入一次即可，找到两个顶点在顶点数组中的下标，之后创建新节点，利用头插法将其插入到分别以两个顶点为头的链表上。

（2）深度优先遍历
用深度优先搜索策略遍历一个图类似于树的前序遍历，对于一个图G=(V,E)，首先将图中的每一个顶点都标记为未访问，然后选取一个源点v，将其标为已访问，再递归地用深度优先搜索方法，依次搜索该点的所有邻接点w。若w未曾访问，则以w为源点继续进行深度优先遍历，如果从v出发的所有路的顶点都已被访问过，则从v的搜索过程结束。此时如果图中还有未被访问的顶点（该图有多个连通分量或强连通分量），则再任选一个未被访问过的顶点，从这个顶点开始新的搜索，直到V中所有顶点都已被访问过为止。

首先，先将代表是否访问过该顶点的标志数组visited进行初始化，然后随便选取一个顶点作为第一个访问的顶点，调用DFS_UDG函数，并在visited数组进行标记，之后找到它的下一个未曾访问过的邻接点，进行递归调用DFS_UDG函数。

（3）广度优先遍历
广度优先搜索策略遍历一个图类似于树的层次遍历，对于一个图G=(V,E)，从图中的某个源点v出发，在访问了顶点v之后，接着就尽可能横向搜索v的所有邻接点。在依次访问v的各个未被访问过的邻接点w1、w2 … wk之后，分别从这些邻接点出发依次访问与w1、w2 …
wk邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问过为止，此时从v开始的搜索过程结束。若G是连通图，则遍历完成；否则，在G中另选一个尚未访问过的顶点作为新的源点继续上述搜索过程，直至G中所有顶点均被访问完为止。

首先，先将代表是否访问过该顶点的标志数组visited进行初始化，然后随便选取一个顶点作为第一个访问的顶点，调用BFS_UDG函数，并在visited数组中进行标记。设置一个队列，用来存储已经访问过的顶点。输出第一个顶点值，并将其进队。找到队头元素，顺势将其出队，并找到它的邻接点，输出未曾访问过的邻接点，并将其进队，进行该循环，直到队空时停止循环。

（4）拓扑排序
首先设置一个存放顶点入度的数组InDegree，通过调用函数FindInDegree将其初始化。另外设置一个栈，用来暂存所有入度为零的顶点。当栈不为空时，进行以下循环：取栈顶并输出，顺势将其出栈，同时count++用于对输出结点进行计数。之后探索其邻接点，并将其入度减一，然后判断此时该顶点入度是否为零，若为一，则进栈。最后判断count与顶点总数的关系，判断该图是否为有向有环图。

实验代码

头文件及数据定义

#include<iostream>
#include<string.h>
#include<queue>
#include<stack>
using namespace std;
#define MAX_VNODE_NUM 100
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OK 1
typedef int Status;
typedef int VRType;       //顶点关系类型
typedef char VertexType;
typedef char InfoType;  
enum GraphKind{UDG,UDN,DG,DN};

typedef struct ArcNode          //边结点
{
    int adj;                    //该边所指向顶点的位置
    int weight=0;
    struct ArcNode* nextarc;    //指向下一条边的指针
    InfoType *info;
}ArcNode;

typedef struct VNode
{
    VertexType data;            //顶点信息
    ArcNode *firstarc;          //指向第一条依附该顶点的的边的指针
}VNode,Adjlist[MAX_VNODE_NUM];

typedef struct              //邻接表
{
    Adjlist vertices;
    int vexnum,arcnum;
    GraphKind kind;
}ALGraph;
int visited[MAX_VNODE_NUM];
int indegree[MAX_VNODE_NUM];

图的邻接表表示法的创建

Status CreateUDG(ALGraph &G)
{
    int i,j,k;
    VertexType va,vb;
    cout << "请在下列输入无向图的顶点数，边数"<<endl;
    cout << "请输入顶点数： "<<endl;
    cin >> G.vexnum;
    cout << "请输入边数： " << endl;
    cin >> G.arcnum;
    cout << "开始构造无向图：" << endl << "逐一输入顶点向量" << endl;
    for(i=0;i<G.vexnum;++i)         //输入顶点
    {
        cout<<"请输入第"<<i+1<<"个顶点的向量:";
        cin>>G.vertices[i].data;
        G.vertices[i].firstarc=NULL;
    }
    for(k=0;k<G.arcnum;++k)         //输入边信息
    {
        cout << "请输入第" << k + 1 << "条边的第一个顶点：" << endl;
	    cin >> va ;
	    cout << "请输入第" << k + 1 << "条边的第二个顶点：" << endl;
	    cin >> vb;
        i=LocateVex(G,va);
        j=LocateVex(G,vb);

        ArcNode*p1=new ArcNode;
        ArcNode*p2=new ArcNode;

        //头插法
        p1->adj=j;
        p1->nextarc=G.vertices[i].firstarc;
        G.vertices[i].firstarc=p1;

        p2->adj=i;
        p2->nextarc=G.vertices[j].firstarc;
        G.vertices[j].firstarc=p2;
    }
    return OK;
}
int main()
{
    ALGraph G;
    CreateGraph(G);
    if(G.kind==0||G.kind==2)
    	Display_G(G);
    else
    	Display_N(G);
    return 0;
}

深度优先遍历

void DFS_UDG(ALGraph &G,VertexType v)
{
    cout<<G.vertices[v].data<<' ';
    visited[v]=1;
    ArcNode*p=new ArcNode;
    int a;
    p=G.vertices[v].firstarc;
    while(p)
    {
        a=p->adj;
        if(!visited[a])
            DFS_UDG(G,a);
        p=p->nextarc;
    }
}

void DFS_UDG_Traverse(ALGraph &G)
{
    memset(visited,0,sizeof(visited));
    for(int i=0;i<G.vexnum;++i)
    {
        if(!visited[i])
            DFS_UDG(G,i);
    }
}

int main()
{
    ALGraph G;
    CreateGraph(G);
    cout<<"深度优先遍历：";
    DFS_UDG_Traverse(G);
    return 0;
}

广度优先遍历

void BFS_UDG(ALGraph &G,VertexType v)
{
    int i,u,a;
    ArcNode*p=new ArcNode;
    queue<VertexType> q;
    //此时vertextype的类型是int，v代表顶点类型的下标值，不能误以为是顶点值
    cout<<G.vertices[v].data<<' ';
    i=LocateVex(G,G.vertices[v].data);
    visited[i]=1;
    q.push(G.vertices[v].data);
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        i=LocateVex(G,u);
        
        for(p=G.vertices[i].firstarc;p;p=p->nextarc)
        {
            a=p->adj;
            if(!visited[a])
            {
                cout<<G.vertices[a].data<<' ';
                visited[a]=1;
                q.push(G.vertices[a].data);
            }
        }
    }
}

void BFS_UDG_Traverse(ALGraph &G)
{
    memset(visited,0,sizeof(visited));
    for(int i=0;i<G.vexnum;++i)
    {
        if(!visited[i])
            BFS_UDG(G,i);
    }
}

int main()
{
    ALGraph G;
    CreateGraph(G);
    cout<<"广度优先遍历：";
    BFS_UDG_Traverse(G);
    return 0;
}

拓扑排序

Status CreateDN(ALGraph &G)
{
    int i,j,k,w;
    VertexType va,vb;
    cout << "请在下列输入有向网的顶点数，边数和权值"<<endl;
    cout << "请输入顶点数： "<<endl;
    cin >> G.vexnum;
    cout << "请输入边数： " << endl;
    cin >> G.arcnum;
    cout << "开始构造有向网：" << endl << "逐一输入顶点向量" << endl;
    for(i=0;i<G.vexnum;++i)         //输入顶点
    {
        cout<<"请输入第"<<i+1<<"个顶点的向量:";
        cin>>G.vertices[i].data;
        G.vertices[i].firstarc=NULL;
    }
    for(k=0;k<G.arcnum;++k)         //输入边信息
    {
        cout << "请输入第" << k + 1 << "条边的第一个顶点：" << endl;
	    cin >> va ;
	    cout << "请输入第" << k + 1 << "条边的第二个顶点：" << endl;
	    cin >> vb;
        cout << "请输入该边的权值： " << endl;
        cin>>w;
        i=LocateVex(G,va);
        j=LocateVex(G,vb);

        ArcNode*p1=new ArcNode;

        //头插法
        p1->adj=j;
        p1->weight=w;
        p1->nextarc=G.vertices[i].firstarc;
        G.vertices[i].firstarc=p1;
    }
    return OK;
}

void FindInDegree(ALGraph &G)
{
    ArcNode*p;
    memset(indegree,0,sizeof(indegree));
    for(int i=0;i<G.vexnum;++i)
    {
        p=G.vertices[i].firstarc;
        while(p)
        {
            indegree[p->adj]++;
            p=p->nextarc;
        }
    }
}

void TopologicalSort(ALGraph &G)
{
    FindInDegree(G);
    stack<int>s;
    ArcNode*p;
    int i;
    for(i=0;i<G.vexnum;++i)
    {
        if(!indegree[i])
            s.push(i);
    }
    cout<<"拓扑排序如下："<<endl;
    int count=0;
    while(!s.empty())
    {
        i=s.top();
        s.pop();
        cout<<G.vertices[i].data<<' ';
        count++;
        for(p=G.vertices[i].firstarc;p;p=p->nextarc)
        {
            int k=p->adj;
            if(!(--indegree[k]))
                s.push(k);
        }
        if(!s.empty())
            cout<<"-->";
    }
    if(count<G.vexnum)
        cout<<"该图是有向有环图"<<endl;
}
int main()
{
    ALGraph G;
    CreateGraph(G);
    if(G.kind==0||G.kind==2)
    	Display_G(G);
    else
    	Display_N(G);
    TopologicalSort(G);
    return 0;
}

测试案例

无向图实现深度、广度优先遍历

有向图实现拓扑排序

分析与总结

图的邻接表表示创建
要依次输入n个顶点，并且由于输入的顶点的信息即为顶点信息，故时间复杂度为O(n+e)。
优点：容易找到任一顶点的第一个邻接点和下一个邻接点。
缺点：当判定任意两个顶点之间是否有边或弧时，需搜索第i个或第j个链表。
深度优先遍历
当以邻接表作图的存储结构时，找到邻接点所需时间为O(e)，其中e为无向图中的边，又因为要遍历n个顶点，故深度优先遍历图的时间复杂度为O(n+e)。
广度优先遍历
由于广度优先搜索遍历仅对顶点访问的顺序与深度优先搜索不同，所以广度优先遍历图的时间复杂度与深度优先相同，也为O(n+e)。
拓扑排序
对于有n个顶点和e条弧的有向图来说，建立求各顶点入度的时间复杂度为O(n)；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈，出一次栈，入度减一的操作在while语句中共执行e次，所以总的时间复杂度为O(n+e)。
优点：可以判断一个工程是否可行，并且得知其先决条件。

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能

天工造物局

Plate 编辑器降级契约（Degradation Contract）：为虚拟化与 Shell 模式划定原生行为底线

本文围绕 Plate 仓库 `.agents/skills/performance/rules/degradation-contract.md` 中的核心规则展开，说明在编辑器引入虚拟化渲染、Shell 岛屿（shell islands）、模型驱动选择（model-backed selection）或分阶段挂载（staged mounting）等激进性能手段时，如何为每一种降级模式登记完整的行为契

天工造物局

Dozzle 在 Kubernetes 中的部署与配置：实时查看 Pod 日志的完整指南

Dozzle 是一个面向容器的实时日志查看器，原生支持 Docker、Swarm 与 Kubernetes 三种运行环境。本文围绕官方 Kubernetes 支持文档展开，讲解如何通过 `DOZZLE_MODE=k8s` 在集群内以最小权限 RBAC 部署 Dozzle、如何安装并依赖 Kubernetes Metrics API 展示资源用量，以及如何用 `DOZZLE_NAMESPACE` 与