建站群赚钱有前途吗,宁波江东区网站建设,网络营销论文题目,阿里巴巴国际站买家版app代码参考《妙趣横生的算法.C语言实现》 文章目录前言1、图的概念2、图的存储形式1、邻接矩阵#xff1a;2、邻接表3、代码定义邻接表3、图的创建4、深度优先搜索DFS5、广度优先搜索BFS6、实例分析前言
本章总结#xff1a;图的概念、图的存储形式、邻接表定义、图的创建、图…代码参考《妙趣横生的算法.C语言实现》 文章目录前言1、图的概念2、图的存储形式1、邻接矩阵2、邻接表3、代码定义邻接表3、图的创建4、深度优先搜索DFS5、广度优先搜索BFS6、实例分析前言
本章总结图的概念、图的存储形式、邻接表定义、图的创建、图的遍历(DFS、BFS)、 以及最后给出一个实例分析 1、图的概念
图是由顶点的非空有限集合V与边的集合E(顶点之间的关系)所构成。 图分为有向图和无向图。
2、图的存储形式
最常见的两种邻接矩阵、邻接表
1、邻接矩阵
利用两个数组来存储一个图。 第一个数组为一维数组用来存放图中的数据。vertex[0,1,…,n-1]:存储顶点信息 第二个数组为二维数组用来存储顶点的相互关系称为邻接矩阵。 A[i][j]{1,当顶点i与顶点j之间有边 0,当顶点i与顶点j之间没有边}
有向图有向图的邻接矩阵
通过简单的邻接矩阵就可以把一个复杂的图关系表现出来不过该方法不适合存储稀疏图(边数目少的图)
2、邻接表
邻接表由链表和顺序数组组成。链表用来存放边的信息数组用来存放顶点的数据信息。 每一个顶点分别建立一个链表。 每个链表前面设置一个头结点顶点域vertex用来存放顶点数据信息指针域next指向依附于顶点vertex的第一条边。
vertexnext
每一个链表中链表的每一个结点陈伟边结点表示依附于对应顶点的一条边。adjvex域存放该边的另一端顶点在顶点数组中的位置(数组下标)weight存放边的权重next指向下一条边结点若是最后一个边结点则指向NULL
adjvexweightnext分别对应了头结点以及边结点有向图有向图的邻接表
3、代码定义邻接表
//邻接表定义
#define MAX_VERTEX_NUM 20 //指定图中顶点最大的个数为20
typedef struct ArcNode
{//单链表中结点类型int adjvex; //该边指向顶点在顺序表中的位置(数组下标)struct ArcNode *next; //指向下一条边的指针infoType *weight; //边上的权重
}ArcNode;typedef struct VNode
{//顶点类型VertexType data; //顶点中的数据信息为VertexType类型ArcNode *firstarc; //指向单链表即指向一条边
}VNode;VNode G[MAX_VERTEX_NUM]; //VNode类型的数组G它是图中顶点的存储容器。3、图的创建
图的创建就是创建一个基于邻接表存储的图结构。在此之前必须先设计好图的逻辑结构。 步骤 1、创建图的顶点也就是创建存储图中顶点的顺序表 2、创建顶点之间的边也就是创建单链表。 代码描述如下 1、首先向顶点中赋值。通过Getdata得到每个顶点中的数据并将它赋值到G[i].data中去。 每个顶点的firstarc域要初始化为NULL 2、然后创建顶点之间的边。创建时应该严格按照最开始所设计的图的逻辑结构进行边的输入。 创建边的过程与创建链表的过程类似。 当输入-1时表示该顶点依附的边创建完成
//图的创建
GreatGraph(int n,VNode G[])
{int i,e;ArcNode *p,*q;printf(输入顶点信息\n);for(i0;in;i){ Getdata(G[i]); //得到每条顶点中的数据 G[i].firstarcNULL; //初始化每一个顶点第一条边为空}for(i0;in;i){printf(创建第%d个顶点的边);scanf(%d,e); //输入边指向的顶点坐标while(e!-1){p(ArcNode *)malloc(sizeof(ArcNode)); //创建一条边p-next NULL; //链表结点next指向空p-adjvex e; //将该边指向顶点的信息赋值给adjvexif(G[i].firstarc NULL)G[i].firstarcp; //i结点的第一条边else q-next p;qp;scanf(%d,e);}}
}//如果是创建上面提到过的有向图则
void main()
{VNode G[3];CreatGpraph(3,G);
}4、深度优先搜索DFS
图的遍历从图的某一顶点出发访遍图中其余顶点且使每个顶点只被访问一次。 图的遍历可用于 求解图的连通性问题拓扑排序求解最短路径求解关键路径 深度优先搜索的基本思路 从图中的某个顶点v出发访问该顶点v然后再一次从v的未被访问过的邻接点出发继续优先深度优先遍历该图直到图中与顶点v路径相通的顶点都被访问到为止。 由于一个图结构未必是连通的因此一次的深度优先搜索不一定可以遍历到图中所有的顶点若此时图中仍然有顶点未被访问 就另选图中的一个没有被访问到的顶点作为起始点继续深度优先搜索。 重复上述操作直到图中所有顶点都被访问到为止。 深度优先搜索是一个递归操作重复“访问顶点v再依次从v未被访问过的邻接点出发继续深度优先搜索” //代码描述
/*
深度优先搜索一个连通图
*/
void DFS(VNode G[],int v)
{int w;visit(v); //访问当前顶点visited[v] 1; //将顶点v对应的访问标记置1wFirstAdj(G,v); //找到顶点v的第一个邻接点如果无邻接点返回-1while(w!-1){if(visited[w]0) //如果该顶点未被访问{DFS(G,w); //递归地进行深度优先访问wNextAdj(G,v); //找到顶点v的下一个邻接点如果没有返回-1}}
}//对图中G(V,E)进行深度优先搜索的主算法
void Travel_DFS(VNode G[],int visited[],int n)
{int i;for(i0;in;i)visited[i]0; //将标记数组初始化为0for(i0;in;i)if(visited[i]0) //若有顶点未被访问从该顶点开始继续深度优先搜索DFS(G,i);
}Travel_DFS 函数包含了3个参数 G[]表示存储图结构的容器这里可以理解为邻接表 visited[]为设置的方位标志数组用来标记图中被访问过的顶点 n表示图中的顶点个数。 将visited初始化为0因为一开始时图中的任何定点都没有被访问。 然后从第一个没有被访问的顶点开始调用递归函数DFS从该顶点开始深度优先遍历整个图 之所以不能仅仅通过一个递归函数DFS()来遍历整个图是因为DFS只能遍历到从起始顶点v开始所有与v相连通的图的顶点。 如果这个图不是连通的仅仅通过DFS是无法遍历完全的 可以举个例子来描述详细遍历过程
假设以V0为起点访问标志数组初始值为visited[5]{0,0,0,0,0}; {(1)访问顶点V0visited[5]1,0,0,0,0(2)用函数FirstAdj得到V0第一个邻接点如V1(3)如果不返回-1即有邻接点(3.1)访问顶点V1visited[5]1,1,0,0,0(3.2)用函数FirstAdj得到V1第一个邻接点V2(因为V0已经访问过了)(3.3)如果不返回-1即有邻接点(3.3.1)访问顶点V2visited[5]1,1,1,0,0(3.3.2)用函数FirstAdj得到V2第一个邻接点返回-1因为都被访问过了(3.4)用函数NextAdj()得到V1下一个邻接点返回-1因为都被访问过儿(4)用函数NextAdj()得到V0下一个邻接点返回-1因为都被访问过儿\begin{cases} (1) \text{访问顶点V0visited[5]{1,0,0,0,0}}\\ (2) \text{用函数FirstAdj得到V0第一个邻接点如V1}\\ (3) \text{如果不返回-1即有邻接点}\\ (3.1) \text{访问顶点V1visited[5]{1,1,0,0,0}}\\ (3.2) \text{用函数FirstAdj得到V1第一个邻接点V2(因为V0已经访问过了)}\\ (3.3) \text{如果不返回-1即有邻接点}\\ (3.3.1) \text{访问顶点V2visited[5]{1,1,1,0,0}}\\ (3.3.2) \text{用函数FirstAdj得到V2第一个邻接点返回-1因为都被访问过了}\\ (3.4) \text{用函数NextAdj()得到V1下一个邻接点返回-1因为都被访问过儿}\\ (4) \text{用函数NextAdj()得到V0下一个邻接点返回-1因为都被访问过儿}\\ \end{cases}⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧(1)(2)(3)(3.1)(3.2)(3.3)(3.3.1)(3.3.2)(3.4)(4)访问顶点V0visited[5]1,0,0,0,0用函数FirstAdj得到V0第一个邻接点如V1如果不返回-1即有邻接点访问顶点V1visited[5]1,1,0,0,0用函数FirstAdj得到V1第一个邻接点V2(因为V0已经访问过了)如果不返回-1即有邻接点访问顶点V2visited[5]1,1,1,0,0用函数FirstAdj得到V2第一个邻接点返回-1因为都被访问过了用函数NextAdj()得到V1下一个邻接点返回-1因为都被访问过儿用函数NextAdj()得到V0下一个邻接点返回-1因为都被访问过儿
5、广度优先搜索BFS 广度优先搜索基本思路 从图中的指定顶点v出发先访问顶点v然后依次访问v的各个未被访问的邻接点然后从这些邻接点出发按照同样的原则依次访问它们未被访问的邻接点 如此循环直道图中所有与v相连通的邻接点都被访问。 若此时图中仍有顶点未被访问就另选图中的一个没有被访问到的顶点作为起始点继续广度优先搜索直道图中所有顶点都访问完为止。 深度优先特点从一个顶点深入下去深入到不能再深入下去为止再从另一个未被访问过的顶点深入下去。 广度优先特点:按层次遍历的方法即先访问离顶点v0最近的顶点v1,v2,v3…再逐一访问离v1 v2 v3 …最近的顶点 算法思路 【A】 1、访问顶点v 2、每访问到一个顶点。都将对应的访问标签置1 3、将一杯访问过的顶点v入队列 【B】 循环执行以下操作 1、从队列中取出队头元素(顶点v) 2、得到该顶点的第一个邻接点 3、如果该邻接点还没被访问、则访问并入队列访问标记置1 4、求顶点v的下一个邻接点如果存在邻接点则跳回步骤3如果不存在邻接点跳回到步骤1 循环执行上述操作直到队列取空为止。 一旦队列取空则表明最后访问到的顶点已经没有未访问到的邻接点了 代码描述
void BFS(VNode G[],int v)
{int w;visit(v); //访问顶点vvisited[v]1; //将顶点v对应的访问标记置1EnQueue(q,v); //顶点v入队列while(!emptyQ(q)){DeQueue(q,v); //出队列元素由v返回w FirstAdj(G,v); //找到顶点v的第一个邻接点如果无邻接点返回-1while(w!-1){if(visited[w]0){visit(w);EnQueue(q,w); //顶点w入队列visited[w]1;}wNextAdj(G,v); //找到顶点v的下一个邻接点如果无邻接点返回-1}}
}//对图G(V,E)进行广度优先搜索的主要算法
void Travel_BFS(VNode G[],int visited[],int n)
{int i;for(i0;in;i){visited[0]0; //标记数组初始化为0}for(i0;in;i){if(visited[i]0) //如果顶点未被访问到从该顶点开始继续广度优先搜索BFS(G,i);}
}
/*
BFS实现广度优先搜索一个连通的图参数G[]表示图的存储容器即邻接表
v表示广度优先遍历访问起点可以举个例子来描述详细遍历过程 1、visit(V0),visited[5]{1,0,0,0,0} queue: V0 2、QueOut(V0),Firstadj(V0)V1,visit(V1) queue: 3、visit(V1),visited[5]{1,1,0,0,0} queue: V1 4、NextAdj(V0)V2,visit(V2) queue: V1 5、visit(V2),visited[5]{1,1,1,0,0} queue: V1,V2 6、NextAdj(V0)-1 queue: V1,V2 7、QueOut(V1),Firstadj(V1)V3,visit(V3) queue: V2 8、visit(V3),visited[5]{1,1,1,1,0} queue: V2V3 9、NextAdj(V1)V4,visit(V4) queue: V2V3 10、visit(V4),visited[5]{1,1,1,1,1} queue: V2V3,V4 11、NextAdj(V1)-1 queue: V2V3,V4 12、QueOut(V2),Firstadj(V2)-1 queue: V3,V4 14、QueOut(V3),Firstadj(V3)-1 queue:V4 15、QueOut(V4),Firstadj(V4)-1 queue 此数据结构为二叉树结构所以广度优先搜索适用于对树结构的遍历因为树结构是标准的层次结构 注意我们这里的遍历是按照图中每个顶点之间的关系对一个图的各连通分量进行的遍历而不只是对图中的每个顶点进行访问那么简单。图的遍历可能带有其他操作如计算带权有向图边权之和记录有向图顶点访问轨迹记录两顶点之间的边权值问题都必须依赖图的遍历。
6、实例分析
这里实例化上面涉及到的两个函数FirstAdj()和NextAdj(); FirstAdj(): 功能返回顶点的第一个邻接点在数组G的下标如果该顶点无邻接点返回-1
//返回第一个邻接点在数组中的下标
int FirstAdj(VNode G[],int v)
{if(G[v].firstarc!NULL) return (G[v].firstarc)-adjvex; //如过该结点有第一条边返回下标否则返回-1return -1;
}
NextAdj() 功能返回顶点的下一个邻接点在数组G的下标如果该顶点无邻接点或者该点所有邻接点都被访问过返回-1
//返回下一个邻接点在数组中的下标
int NextAdj(VNode G[],int v)
{ArcNode *p;pG[v].firstarc;while(p!NULL){if(visited[p-adjvex]) pp-next; //如果已经访问过返回-1else return p-adjvex;}return -1;
}用邻接表存储的形式创建一棵无向图并应用深度优先搜索方法遍历该图中的每个顶点
#include stdio.h
#include stdlib.h
#include malloc.h
#include conio.h//邻接表定义
#define MAX_VERTEX_NUM 20 //指定图中顶点最大的个数为20
typedef int VertexType ;
typedef struct ArcNode
{//单链表中结点类型int adjvex; //该边指向顶点在顺序表中的位置(数组下标)struct ArcNode* next; //指向下一条边的指针//infoType* weight; //边上的权重
}ArcNode;typedef struct VNode
{//顶点类型VertexType data; //顶点中的数据信息为VertexType类型ArcNode* firstarc; //指向单链表即指向一条边
}VNode;VNode G[MAX_VERTEX_NUM]; //VNode类型的数组G它是图中顶点的存储容器。
int visited[5] { 0,0,0,0,0 };//图的创建
void GreatGraph(int n, VNode G[])
{int i, e;ArcNode* p, * q;q NULL;printf(输入顶点信息\n);for (i 0;i n;i){scanf(%d, G[i].data); //得到每条顶点中的数据 G[i].firstarc NULL; //初始化每一个顶点第一条边为空}for (i 0;i n;i){printf(创建第%d个顶点的边\n,i);scanf(%d, e); //输入边指向的顶点坐标while (e ! -1){p (ArcNode*)malloc(sizeof(ArcNode)); //创建一条边p-next NULL; //链表结点next指向空p-adjvex e; //将该边指向顶点的信息赋值给adjvexif (G[i].firstarc NULL)G[i].firstarc p; //i结点的第一条边else{q-next p;}q p;scanf(%d, e);}}
}
//返回第一个邻接点在数组中的下标
int FirstAdj(VNode G[], int v)
{if (G[v].firstarc ! NULL) return (G[v].firstarc)-adjvex; //如过该结点有第一条边返回下标否则返回-1return -1;
}//返回下一个邻接点在数组中的下标
int NextAdj(VNode G[], int v)
{ArcNode* p;p G[v].firstarc;while (p ! NULL){if (visited[p-adjvex]) p p-next; //如果已经访问过返回-1else return p-adjvex;}return -1;
}void DFS(VNode G[], int v)
{int w;printf(%d , G[v].data); //访问当前顶点打印出顶点额数据信息visited[v] 1; //将顶点v对应的访问标记置1w FirstAdj(G, v); //找到顶点v的第一个邻接点如果无邻接点返回-1while (w ! -1){if (visited[w] 0) //如果该顶点未被访问{DFS(G, w); //递归地进行深度优先访问}w NextAdj(G, v); //找到顶点v的下一个邻接点如果没有返回-1}
}/*
1、首先向顶点中赋值。通过Getdata得到每个顶点中的数据并将它赋值到G[i].data中去。
每个顶点的firstarc域要初始化为NULL
2、然后创建顶点之间的边。创建时应该严格按照最开始所设计的图的逻辑结构进行边的输入。
创建边的过程与创建链表的过程类似。
当输入-1时表示该顶点依附的边创建完成
*/
int main()
{VNode G[5];GreatGraph(5, G);printf(DFS搜索\n );DFS(G, 0);_getche();return 0;
}效果 放几个链接学习学习
https://blog.csdn.net/ledou2/article/details/81875743 https://blog.csdn.net/ledou2/article/details/81905831
