锐客网

  1. 首页 > it技术 > >

考研|数据结构图基本操作

邻接矩阵：

#include #include #define maxsize 50 //结点定义 typedef struct { int no; char info; }VertexType; //图定义 typedef struct { int edges[maxsize][maxsize]; //表示顶点数和边数 int n,e; //存放结点信息 VertexType vex[maxsize]; }Mgraph;

邻接表：
#include #include #define maxsize 50 //结点定义 typedef struct ArcNode { //该边指向的结点 int adjvex; //指向下一个边的结点 struct ArcNode *nextarc; int info; }ArcNode; //顶点定义 typedef struct { //顶点信息 char data; //顶点指向的第一个边的指针 ArcNode *firstarc; }VNode; typedef struct { //邻接表 VNode adjis[maxsize]; //顶点数和边数 int n,e; }Agraph;

深度优先遍历
#include #include #define maxsize 50 //结点定义 typedef struct ArcNode { //该边指向的结点 int adjvex; //指向下一个边的结点 struct ArcNode *nextarc; int info; }ArcNode; //顶点定义 typedef struct { //顶点信息 char data; //顶点指向的第一个边的指针 ArcNode *firstarc; }VNode; typedef struct { //邻接表 VNode adjis[maxsize]; //顶点数和边数 int n,e; }Agraph; //深度优先搜索 类似二叉树的先序遍历 int visit[maxsize]; void DFS(Agraph *G,int v) { ArcNode *p; visit[v]=1; //visit(v)的意思是输出该结点的信息，下面用printf代替 //Visit(v); printf("%c",G->adjis[v].data); p=G->adjis[v].firstarc; if(p!=NULL) { //当违背标记的点才会进行递归 if(visit[p->adjvex]==0) DFS(G, p->adjvex); p=p->nextarc; } }

广度优先遍历
#include #include #define maxsize 50 //结点定义 typedef struct ArcNode { //该边指向的结点 int adjvex; //指向下一个边的结点 struct ArcNode *nextarc; int info; }ArcNode; //顶点定义 typedef struct { //顶点信息 char data; //顶点指向的第一个边的指针 ArcNode *firstarc; }VNode; typedef struct { //邻接表 VNode adjis[maxsize]; //顶点数和边数 int n,e; }Agraph; //广度优先搜索 类似二叉树的层次遍历 void BFS(Agraph *G,int v,int visit[maxsize]) { //Visit函数未敲，具体可参考深度优先算法中的printf操作 ArcNode *p; int que[maxsize],front,rear; front=rear=0; int j; Visit(v); visit[v]=1; //当前结点进队 rear=(rear+1)%maxsize; que[rear]=v; //开始层次遍历，当队空时即完成了遍历 while(front!=rear) { //顶点出队，第一次循环时即空位置出队 front=(front+1)%maxsize; //j存储当前顶点 j=que[front]; //p指向顶点的第一个结点 p=G->adjis[j].firstarc; //循环的将第一个结点的所有邻接点全部入队 while(p!=NULL) { if(visit[p->adjvex]==0) { //访问该结点信息 Visit(p->adjvex); //标记该结点 visit[p->adjvex]=1; //h该结点入队 rear=(rear+1)%maxsize; que[rear]=p->adjvex; } //p继续指向下一个结点进行访问、标记、入队 p=p->nextarc; } }}

普里姆算法
（该算法主要考察手工模拟，在此就不给出代码了 emmmmm？其实就是有点懒加这个有点麻烦?(? ???ω??? ?)?））
克鲁斯卡尔算法
（该算法主要考察手工模拟，在此就不给出代码了 emmmmm？其实我又懒外加这个也有点麻烦 Σ>―(〃°ω°〃)?→ ）
迪杰斯特拉算法
#include #include #define maxsize 50 #define inf 99999 //结点定义 typedef struct { int no; char info; }VertexType; //图定义 typedef struct { int edges[maxsize][maxsize]; //表示顶点数和边数 int n,e; //存放结点信息 VertexType vex[maxsize]; }MGraph; //迪杰斯特拉算法 void Dijkstra(MGraph g,int v,int dist[],int path[]) { //v为迪杰斯特拉算法的查找原点 //dist为原点到该点的最短距离，不存在路径时为无穷inf //path该原点到该结点的最短路径上的前驱结点（解释一下：a->b->c->d,假设这是最短路径，e则c的前驱结点就是b），-1代表无前驱结点 int set[maxsize]; //用于标记结点是否并入，1为并入，0为未并入 int min,i,j,u; //对数组初始化（根据v并入的情况下，进行初始化） for(i=0; iu+u->x 小于 v->x（->代表前者到后者的最短距离距离，并不是直接相连的意思） for(j=0; j

弗洛伊德算法
#include #include #define maxsize 50 #define inf 99999 //结点定义 typedef struct { int no; char info; }VertexType; //图定义 typedef struct { int edges[maxsize][maxsize]; //表示顶点数和边数 int n,e; //存放结点信息 VertexType vex[maxsize]; }MGraph; //弗洛伊德算法 void Floyd(MGraph g,int path[][maxsize]) { int i,j,k; int A[maxsize][maxsize]; //初始化A和path数组，A数组初始化为i->j的直接路径，path初始全部为-1 //我说的这个直接路径是，两个结点存在一个条路，若仅存在a->b->c，则a->c不存在直接路径，a->b,b->c存在直接路径，并没有直接路径的概念，这里是我自己理解的说法 for(i=0; i
【考研|数据结构图基本操作】对于迪杰斯特拉和弗洛伊德算法不理解的盆友，我这里推荐一个视频，这个视频讲述的很清晰，更关键的是：配合着动图演示模拟这个过程（个人建议可以慢速看看具体过程，更容易理解这个事情），视频链接如下：https://www.bilibili.com/video/av54668527（已获得转载同意）

    推荐阅读


    上一篇：数据分析必须懂的假设检验

    下一篇：2021|2021 GitHub 报告解读（中国开发者数量全球第 2 | JavaScript 最受欢迎）