数据结构图基本操作

134 阅读 0 评论 89 点赞

我是靠谱客的博主超级鞋垫，这篇文章主要介绍数据结构图基本操作，现在分享给大家，希望可以做个参考。

邻接矩阵：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <stdlib.h>
#define maxsize 50
//结点定义
typedef struct
{
int no;
char info;
}VertexType;
//图定义
typedef struct
{
int edges[maxsize][maxsize];
//表示顶点数和边数
int n,e;
//存放结点信息
VertexType vex[maxsize];
}Mgraph;

邻接表：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <stdlib.h>
#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;

深度优先遍历

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <stdlib.h>
#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;
}
}

广度优先遍历

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <stdlib.h>
#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 <stdio.h>
#include <stdlib.h>
#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;i<g.n;i++)
{
//dist初始化为v点到所有结点的距离（有直接路径时g.edges[v][i]=一个数字；没有直接路径时g.edges[v][i]=inf）
dist[i]=g.edges[v][i];
//set[i]全设置为0
set[i]=0;
//和v有直接路径的，设置该点的前驱结点为v，否则设置没有前驱结点，即-1
if(g.edges[v][i]<inf)
path[i]=v;
else
path[i]=-1;
}
//初始化时其实默认初始结点v已经并入，通过对path的赋值就可以发现，这里把v单独拿出来了处理，其实在循环过程中也可以加判断处理
set[v]=1;path[v]=-1;
//初始化结束
//开始算法关键部分
for(i=0;i<g.n-1;i++)
{
//寻找此时未并入结点中，与初始结点v最近的结点
min=inf;
for(j=0;j<g.n;j++)
{
//未并入+遍历寻找与v最近的结点（与v最近的是dist数组）
if(set[j]==0&&dist[j]<min)
{
//u为记录最近结点
u=j;
min=dist[j];
}
}
set[u]=1;
//新加入结点后，判断新加入结点是否存在 v->u+u->x 小于 v->x（->代表前者到后者的最短距离距离，并不是直接相连的意思）
for(j=0;j<g.n;j++)
{
//如果存在这样的未并入结点，则更新最短距离以及该结点前驱结点
if(set[j]==0&&dist[u]+g.edges[u][j]<dist[j])
{
dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
}
//总结一下：
//第一步，初始化
//第二步，开始算法，具体过程为：查找此时距离原点最近的未并入结点，并入新结点
//第三步，循环遍历判断，加入新结点后是否存在（因为加入新结点而是的原点到达其他结点更加的结点），存在则更新dist和path。
//循环二、三步
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <stdio.h>
#include <stdlib.h>
#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;i<g.n;i++)
{
//dist初始化为v点到所有结点的距离（有直接路径时g.edges[v][i]=一个数字；没有直接路径时g.edges[v][i]=inf）
dist[i]=g.edges[v][i];
//set[i]全设置为0
set[i]=0;
//和v有直接路径的，设置该点的前驱结点为v，否则设置没有前驱结点，即-1
if(g.edges[v][i]<inf)
path[i]=v;
else
path[i]=-1;
}
//初始化时其实默认初始结点v已经并入，通过对path的赋值就可以发现，这里把v单独拿出来了处理，其实在循环过程中也可以加判断处理
set[v]=1;path[v]=-1;
//初始化结束
//开始算法关键部分
for(i=0;i<g.n-1;i++)
{
//寻找此时未并入结点中，与初始结点v最近的结点
min=inf;
for(j=0;j<g.n;j++)
{
//未并入+遍历寻找与v最近的结点（与v最近的是dist数组）
if(set[j]==0&&dist[j]<min)
{
//u为记录最近结点
u=j;
min=dist[j];
}
}
set[u]=1;
//新加入结点后，判断新加入结点是否存在 v->u+u->x 小于 v->x（->代表前者到后者的最短距离距离，并不是直接相连的意思）
for(j=0;j<g.n;j++)
{
//如果存在这样的未并入结点，则更新最短距离以及该结点前驱结点
if(set[j]==0&&dist[u]+g.edges[u][j]<dist[j])
{
dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
}
//总结一下：
//第一步，初始化
//第二步，开始算法，具体过程为：查找此时距离原点最近的未并入结点，并入新结点
//第三步，循环遍历判断，加入新结点后是否存在（因为加入新结点而是的原点到达其他结点更加的结点），存在则更新dist和path。
//循环二、三步
}

弗洛伊德算法

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <stdlib.h>
#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<g.n;i++)
for(j=0;j<g.n;j++)
{
A[i][j]=g.edges[i][j];
path[i][j]=-1;
}
//弗洛伊德的三重循环 核心～
for(k=0;k<g.n;k++)
for(i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
if(A[i][k]+A[k][j]<A[i][j])
{
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
}