前言:接下来就不给大家上概念性知识了,虽然基础知识不能忽视,但是我打字也慢,概念性的东西比较浪费时间,直接就上核心内容了(我认为的核心).要是需要了解基础概念的大家自行查阅.因为我目前在准备考试,所有内容的侧重点就是考试大纲.，接下来我们就来聊聊关于7种数据结构图?以下内容大家不妨参考一二希望能帮到您!
7种数据结构图
前言:
接下来就不给大家上概念性知识了,虽然基础知识不能忽视,但是我打字也慢,概念性的东西比较浪费时间,直接就上核心内容了(我认为的核心).要是需要了解基础概念的大家自行查阅.因为我目前在准备考试,所有内容的侧重点就是考试大纲.
邻接矩阵法
#define MaxVertexNum 100 //顶点数目最大值
typedef char VerterTypy; //顶点的数据类型
typedef int EdgeType;//带权图边上权值的数据类型
typedef strcut
{
VerterTypy Ver[MaxVertexNum];//顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum];//领接矩阵,边表
int vexnum, arcnum;//图的当前顶点和弧数
}MGraph;
临接表法
#define MaxVertexNum 100 //顶点数目最大值
typedef strcut ArcNode//边表结点
{
int adjvex;
struct ArcNode *next;
}ArcNode;
typedef strcut VNode//顶点表结点
{
VertexType data;
ArcNode *first;
}VNode,AdjList[MaxVertexNum];
typedef strcut
{
AdjList vertices;//临接表
int vexnum, arcnum;////图的当前顶点和弧数
}ALGraph;
广度优先遍历伪代码(先访问顶点, 算法复杂度为O(|V|的平方 层次遍历 )
bool visited[MAX_VERTEX_NUM];//访问标记数组
void BFSTraverse(Graph G)
{
for (i = 0; i < G; i)
visited[i] = FALSE;//初始化标记数组
InitQueue(Q);//初始化辅助队列
for (i = 0; i < G; i)//从0号开始遍历
if (!visited[i])//对每个连通分量代用一次BFS
BFS(G, i);
}
void BFS(Graph G, int v)//从顶点v出发,广度优先遍历图G,算法借助一个辅助队列Q
{
visit(v);
visited[i] = TURE;
Enqueue(Q, v);//顶点入队
while (!isEmpty(Q))
{
DeQueue(Q, v);//顶点出队
for(w=FirstNeighbor(G,v);w= NextNeighbor(G,v,w))
if (!visited[w])
{
visit(w);
visited[w] = TURE;
EnQueue(Q, w);
}
}
}
深度优先遍历(算法复杂度为O(|V| 先根遍历)
bool visited[MAX_VERTEX_NUM];//访问标记数组
void DFSTraverse(Graph G)//对图G进行深度优先遍历
{
for (v = 0; v< G;vexnum; v)
visited[v] = FALSE;//初始化已访问标记数据
for (v = 0; v< G; vexnum; v)
if (!visited[v])
DFS(G, v);
}
void DFS(Graph G, int v)
{
visit(v);
visited[v] = TURE;
Enqueue(Q, v);
for(w=FirstNeighbor(G,v);w= NextNeighbor(G,v,w))
if (!visited[w])
{
DFS(G, w);
}
}
Prim算法(时间复杂度O(|V|的平方 适合边稠))
伪代码~~~~
void Prim
T=空树
U={w};
while((V-U)!=kong;
T=Tu{{U,V}};//边归入树
U=U u{V};//顶点归入树
因为是伪代码所以和大家解释一下,7,8行的u表示集合里的并集.
Kruskal算法(适合边稀)
void Kruskal(V,T)//伪代码简单描述
{
T=V;
numS=n;
while(numS>1)
{
if{
T=Tu{{U,V}};
numS--;
}
}
}
Dijkstra算法求解最短路径问题(适合带权有向图,边上带有负权值不适用)
目前代码部分不是重点,所以下面主要介绍一下思想.
Dijkstra是一位图灵奖的获得者,他为计算机领域做出了杰出的贡献,就像我们现在学过的操作系统的PV操作,银行家算法,以及哲学家进餐问题等等都来源于Dijkstra.但是他只活了72岁,就拜拜了.
废话结束,来看一下思想:
该算法主要是设置一个集合S,记录已经求得的最短路径的顶点,
dist[]记录最开始的点,到各顶点当前的最短路径
path[]记录从开始的顶点到顶点i(任意一个顶点)之间的最短路径的前驱结点
简单来说一下就是:带权?什么叫带权,就是A--->B的路上标了数值,这就是权.这个数字到底代表了什么意思?你研究这干嘛?和你没关系,重点是什么,重点就是我们怎走才可以使权值最小,即使从A--->B的路上经过了山路十八弯,只要最后权值和,是所有可以从A--->B里面最小的就行了.这才是重点.漂洋过海来看你!!!嘻嘻
但是有一点我们要知道,Dijkstra是基于贪心策略的,贪心策略大家知道吗,就是只顾眼前利益,值抓眼前最好的.和哲学家进餐问题正好相反(这个不知道的大家自己查查吧,这是操作系统里面的知识,这里不再赘述).我们第一步要干嘛,首先就是找以起点为中心最小的权值,然后第二步在找第二小的,以此类推.
万一遇到边上带有负权值怎么办?你操心这些干嘛,早有人给你研究出来了
请看最短路径第二弹
Floyd算法求解最短路径(允许边在负权值,但是不允许带负权值的边组成回路)
算法思想:递推产生一个n阶的方阵,(因为我没有画图,所以我就举个例子给大家描述一下,可能不是特别学术,我们就从数学的角度说一下,介意慎看),方阵大家都知道吧,有行有列,我们现在设行为i,列为j.当我们给出一个在n阶方阵的行列值以后,有切仅有一个数值或者表示式与之对应.那么这个对应的值我们设为A,现在我们开始带入数据来看.现在i,j分别表示为我们正在研究的有项图的所有顶点,那么A的数值就是现在顶点到顶点之间的距离,有人可能会问,顶点本身也会加入存储吗?那数值又是多少,那肯定加入啊,数值为0,因为我到我没距离.然后我们再去寻找最小权值.
大家猜猜这个算法的思想是基于什么的?递推吗?不是哦,是动态规划
关于动态规划想了解的可以点下方链接
原文链接：https://blog.csdn.net/u013250416/article/details/80558542(来源于百度百科)
,
