合肥高端网站设计,开发一套小程序大概多少钱,开网店怎么开 新手需要多少资金,自助建站网站系统1.图的基本概念 1#xff09;图的定义 图G由顶点集V和边集E组成#xff0c;记为G(V,E),其中V(G)表示图G中定点的有限非空集#xff1b;E(G)表示图G中顶点之间的关系#xff08;边#xff09;集合。V{v1,v2,..,vn},用|V|表示图G中顶点的个数#xff0c;也称为图G的阶…1.图的基本概念 1图的定义 图G由顶点集V和边集E组成记为G(V,E),其中V(G)表示图G中定点的有限非空集E(G)表示图G中顶点之间的关系边集合。V{v1,v2,..,vn},用|V|表示图G中顶点的个数也称为图G的阶E{uv| u ∈ V,v ∈ V},用|E|表示图G中边的条数。 注意线性表可以是空表树可以是空树但图不可一世空图。就是说图中不能一个顶点也没有图的顶点集一定非空但边集E可以为空此时图中只有顶点没有边 2简单图不存在重复边不存在顶点到自身的边则称图G为简单图 多重图图G中两个结点之间的边数多于一条又允许顶点通过同一条边与自己关联则G为多重图。多重图的定义和简单图是相对的。 完全图在无向图中如果任意两个顶点之间都存在边则称该图为无向完全图含有n个顶点的无向完全图又n(n-1)/2条边含有n个顶点的有向完全图有n(n-1)条有向边 3连通在无向图中若从顶点v到顶点w有路径存在则称v和w是连通的若图G中任意两个顶点都是连通的则称图G为连通图否则称为非连通图 无向图中的极大连通子图称为连通分量如果一个图有n个顶点并且有小于n-1条边那么此图必是非连通图。 注意极大连通子图要求该连通子图包含其所有的边极小连通子图是既要保持图连通又要使得边数最少的子图。 4强连通图、强连通分量 在有向图中若从顶点v到顶点w和从顶点w到顶点v之间都有路径则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的则称该图为强连通图。有向图的极大强连通子图称为有向图的强连通分量。 5生成树、生成森林 连通图的生成树是包含图中全部顶点的一个极小连通子图。如果图中定点数为n则它的生成树含有n-1条边。对于生成树而言看去他的一条边则会变成非连通图若加上一条边则会形成回路。在非连通图中连通分量的生成树构成了非连通图的生成森林。 注意包含无向图中全部顶点的极小连通子图只有生成树满足条件因为砍去生成树的任意一条边图将不再连通。 6定点的度、入度出度 每个顶点的度定义为以该顶点为一个端点的边的数目 对于无向图顶点v的度是指依附于该顶点的边的条数记为TD(v)无向图的全部顶点的度之和等于边数的两倍这是因为每条边和两个顶点相关联。 对于有向图顶点v的度分为入度和出度入度是以顶点v为终点的有向边的数目记为ID(v),出度是以顶点v为起点的有向边的数目记为OD(v)顶点v的度等于出度和入度之和TD(v) ID(v) OD(v); 有向图的出度和入度之和相等并且等于边数。 7边的权和网 在一个图中每条边都可以标上具有某种含义的值该数值称为该边的权值。这种边上带权值的图称为带权图也称为网。 8稠密图、稀疏图 边数很少的图称为稀疏图反之称之为稠密图。一般当图满足|E||V|*log|V|时可以看做稀疏图 9路径、路径长度和回路 顶点v1到v2的一条路径指的是顶点序列路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为环或回路。如果一个图有n个顶点并且有大于n-1条边这个图一定有环。 10简单路径、简单回路 在路径序列中顶点不重复出现的路径称为简单路径、除了第一个和最后一个顶点之外其余顶点不重复出现的回路称为简单回路。 11距离 从顶点u出发到顶点v的最短路径若存在则此路径的长度称作从u到v的距离。若从u到v根本不存在路径则记该距离为无穷. 12)有向树有一个顶点的入度为0其余顶点的入度均为1的有向图称为有向树。 2.图的存储及基本操作 所选存储方式应该适合于欲求解的问题无论是无向图还是有向图主要的存储方式都有两种邻接矩阵和邻接表。前者属于图的顺序存储结构后者属于图的链接存储结构。 1邻接矩阵法 稠密图适合使用邻接矩阵的存储表示 2)邻接表法 当图为稀疏图时使用邻接矩阵会浪费大量的空间。而图的邻接表法结合了顺序存储和链式存储方法大大减少了这种不必要的浪费。 对图G中的每个顶点vi建立一个单链表第i个单链表中的结点表示依附于顶点vi的边对于有向图则是以顶点vi为尾的弧这单链表称为vi的边表对于有向图则称为出边表在邻接表中存在两种结点顶点表结点和边表结点。 #define MaxVertexNum 100typedef struct ArcNode{int adjvex; //弧指向的邻接点的位置---顶点数组下标struct ArcNode * next; //指向下一条边的指针//ElemType data; //网的边权值
}ArcNode;typedef struct VNode{VertexType data; //顶点信息ArcNode * first; //指向边表第一个结点
}VNode,AdjList[MaxVertexNum]; typedef struct {AdjList vertices; //邻接表int vexnum,arcnum; //图的顶点数和弧数
}ALGraph; //ALGraph是以邻接表存储的图类型 a)邻接表特点 如果G为无向图则所需存储空间为O(|V|2|E|);如果G为有向图则所需的存储空间为O(|V||E|),无向图中每条边会出现两次 邻接表中给定一个顶点很容易查到它的所有邻边在邻接矩阵中需要扫描一行时间为O(n),如果要确定给定的两个顶点间是否存在边则在邻接矩阵中可以立即查到在邻接表中则需要在相应结点中查找另一结点效率较低。 3十字链表 十字链表是有向图的一种链式存储结构在十字链表中对应于每条弧有一个结点对应于每个顶点也有一个结点。 #define MaxV 100
//本质上也是邻接表
typedef struct ArcNode{ //边表结点int tailVex,headVex; //弧的头尾结点struct ArcNode * hlink,*tlink; //分别指向弧头相同和弧尾相同的结点
// ElemType data; //相关信息
}ArcNode;typedef struct VNode{VertexType data; //顶点信息ArcNode *firstin,*firstout; //指向第一条入弧和出弧
}VNode; typedef struct{ VNode xList[MaxV]; //十字链表int vexnum,arcnum; //图的顶点数和边数
}GLGraph; //以十字链表存储的图类型 在十字链表中极容易找到vi为尾的弧也容易找到以vi为头的弧因而容易求出顶点的出度和入度。 图的十字链表是不唯一的但一个十字链表表示确定一个图。 4邻接多重表 邻接多重表是无向图的另一种链式存储结构与十字链表类似每一条边用一个结点表示 mark | ivex | ilink | jvex | jlink | info mark 为标志域标记该条边是否被搜索过;ivex和jvex分别表示该边依附的两个顶点ilink指向下一条依附于ivex的边jlink指向下一条依附于顶点jvex的边info为指向和边相关的各种信息的指针域。 每一个顶点也用一个结点表示由如下所示的两个域组成 data | firstedge 每一条边只有一个结点 #define MaxVertexNum 100
typedef struct ArcNode{bool mark; //访问标记int ivex,jvex; //分别指向该弧的两个结点struct ArcNode *ilink,*jlink; //分别指向两个顶点的下一条边//InfoType info; //相关信息
}ArcNode;typedef struct VNode{ //顶点表结点VertexType data; //顶点信息ArcNode * firstedge; //指向第一条依附在该顶点的边
}VNode;typedef struct{VNode adjmuList[MaxVertexNum]; //邻接表int vexnum,arcnum; //图的顶点数和弧数
}AMLGraph; 3.图的遍历 图的遍历是指从图中的某一顶点出发按照某种搜索方法沿着图中的边对图中的顶点访问一次且仅访问一次。注意到树是一种特殊的图所以树的遍历也可以看做是一种特殊的图的遍历。两种算法广度优先搜索和深度优先搜索。 1) 广度优先搜索Breadth-First-SearchBFS 类似于二叉树的层序遍历算法 #define MAX_N 100
bool visited[MAX_N];void BFSTraverse(Graph G,){for(int i 0;i G.vnum;i)visited[i] false;InitQueue(Q);for(int i 0;i G.vnum;i)if(!visited[i])BFS(G,i);
}void BFS(Graph G, int v){visit(v);visited[v] true;EnQueue(Q,v);while(!Empty(Q)){DeQueue(Q,v); //顶点v出列for(wneighbor(G,v);w0;wnextNeighbor(G,v,w)){ if(!visited[w]){ visit(w);visited[w] true;EnQueue(Q,w); } }}} 性能分析无论是邻接表还是邻接矩阵的存储方式BFS算法都需要借助一个辅助队列Qn个顶点都需入队一次在最坏的情况下空间复杂度为O(|V|) 采用邻接表存储时每个顶点均需搜索一次或入队一次故时间复杂度为O(|V|),在搜索任一顶点的邻接点时每条边至少访问一次故时间复杂度为O(|E|)算法总的时间复杂度为O(|V||E|).当采用邻接表存储时查找每个顶点的邻接点所需时间为O(|V|),故算法总的时间复杂度为O(|V|^2)。 可以使用BFS算法求解单源最短路径。 给定图的邻接矩阵存储表示是唯一的故其广度优先生成树也是唯一的但由于邻接表存储表示不唯一故其广度优先生成树也是不唯一的。 2深度优先搜索 类似于树的先序遍历 #define MAX_N 100
bool visited[MAX_N];void DFSTraverse(Graph G){for(int i 0;i G.vnum;i){visited[i] false;}for(int i 0;i G.vnum;i){ //对于每个连通分量进行遍历if(!visited[i])DFS(G,i); }
}void DFS(Graph G, int v){visit(v);visited[v] true; //已经访问for(wneighbor(G,v);w 0;wnextneighbor(G,v,w)){if(!visited[w]) //尚未访问结点DFS(G,w);}
} 注意同一个图基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的基于邻接表的遍历所得到的bfs和dfs是不唯一的因为邻接矩阵唯一而邻接表表示不唯一 DFS算法的性能分析 是一个递归算法需要借助递归工作栈空间复杂度为O(|V|);遍历图的过程实质上是对每个顶点查找其邻接点的过程其耗费的时间取决于采用的存储结构。以邻接矩阵表示查找每个顶点的邻接点的所需时间为O(|V|),故总的时间复杂度为O(|V|^2).以邻接表表示时查找所有顶点的邻接点所需时间为O(|E|),访问顶点所需时间为O(|V|),总的时间复杂度为O(|V||E|); 转载于:https://www.cnblogs.com/--CYH--/p/6790242.html
