数据结构之图（数据结构之图结构）

前言:

接下来就不给大家上概念性知识了,虽然基础知识不能忽视,但是我打字也慢,概念性的东西比较浪费时间,直接就上核心内容了(我认为的核心).要是需要了解基础概念的大家自行查阅.因为我目前在准备考试,所有内容的侧重点就是考试大纲.

邻接矩阵法

#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(来源于百度百科)