网站图标的制作h1优化代码,上海网站建设制作微信,建设银行投资网站首页,网站开发客户的思路总结文章目录图的认识图的概念无向图有向图简单图完全图子图连通、连通图、连通分量边的权和网加权图邻接和关联路径简单路径、简单回路环顶点的度、入度和出度割点#xff08;关节点#xff09;桥(割边)距离有向树图的表示邻接列表邻接矩阵图的遍历深度优先遍历广度优先遍历生成…
文章目录图的认识图的概念无向图有向图简单图完全图子图连通、连通图、连通分量边的权和网加权图邻接和关联路径简单路径、简单回路环顶点的度、入度和出度割点关节点桥(割边)距离有向树图的表示邻接列表邻接矩阵图的遍历深度优先遍历广度优先遍历生成树图的认识
图(Graph)是由顶点和连接顶点的边构成的离散结构。一个图就是一些顶点的集合这些顶点通过一系列边结对连接。顶点用圆圈表示边就是这些圆圈之间的连线。顶点之间通过边连接。
注意线性表可以是空表树可以是空树图不可以是空图图可以没有边但是至少要有一个顶点。
图是最灵活的数据结构之一很多问题都可以使用图模型进行建模求解。 树可以说只是图的特例但树比图复杂很多 注意顶点有时也称为节点或者交点边有时也称为链接。
图有各种形状和大小。边可以有权重weight即每一条边会被分配一个正数或者负数值。边可以是有方向的。有方向的边意味着是单方面的关系。从顶点 X 到 顶点 Y 的边是将 X 联向 Y不是将 Y 联向 X。
树和链表都可以被当成是树是一种更简单的形式。他们都有顶点节点和边连接。
图的概念
图是由顶点集合以及顶点间的关系集合组成的一种数据结构。 由顶点 V 集和边 E 集构成因此图可以表示成 Graph (V,E) V是顶点的有穷非空集合E是顶点之间关系的有穷集合也叫边集合。 图按照边或弧的多少分稀疏图和稠密图
无向图 无向图顶点对x,y是无序的。 无向边若顶点Vi到Vj之间的边没有方向则称这条边为无向边用无序偶对(Vi,Vj)来表示 无向图顶点的边数叫做度。 无向图中顶点的度就是与顶点相关联的边的数目没有入度和出度。 如果图中任意两个顶点时间的边都是无向边则称该图为无向图 上图是无向图所以连接顶点A与D的边可以表示为无序对(A,D)也可以写成(D,A) 对于如上无向图来说G(V,{E}) 其中顶点集合V{A,B,C,D}边集合E{(A,B),(B,C),(C,D),(D,A),(A,C)} 完全无向图若有n个顶点的无向图有n(n-1)/2 条边, 则此图为完全无向图。 有向图 如果任意两个顶点之间都存在边叫完全图有向的叫有向图。 有向图具有方向性顶点 (u,v)之间的关系和顶点 (v,u)之间的关系不同后者或许不存在。 有向图顶点对x,y是有序的 有向边若从顶点Vi到Vj的边有方向则称这条边为有向边也称为弧。 用有序偶Vi,Vj来表示Vi称为弧尾Vj称为弧头。 连接顶点A到D的有向边就是弧A是弧尾D是弧头A,D表示弧。注意不能写成D,A。 对于如上有向图来说G(V,{E})其中顶点集合V{A,B,C,D};弧集合E{A,D,B,A,C,A,B,C}
图中顶点之间有邻接点。有向图顶点分为入度和出度。
简单图
若无重复的边或顶点到自身的边则叫简单图。 1不存在重复边 2不存在顶点到自身的边 所以上面的有向图和无向图都是简单图。与简单图相对的是多重图即两个结点直接边数多于一条又允许顶点通过同一条边与自己关联。
完全图
无向图中任意两点之间都存在边称为无向完全图 有向图中任意两点之间都存在方向向反的两条弧称为有向完全图 完全有向图有n个顶点的有向图有n(n-1)条边, 则此图为完全有向图。
子图
若有两个图G(V,E),G1(V1,E2)若V1是V的子集且E2是E的子集称G1是G的子图。
连通、连通图、连通分量
1.连通 在无向图中两顶点有路径存在就称为连通的。
2.连通图 若图中任意两顶点都连通同此图为连通图。 如果对于任意两个顶点都是连通的则称该图是连通图。 对于有向图如果图中每一对顶点Vi和Vj是双向连通的则该图是强连通图。 连通无向图中每一对不同的顶点之间都有路径。如果这个条件在有向图里也成立那么是强连通的。如果从顶点v到顶点v’有路径或从顶点v’到顶点v有路径则称顶点v和顶点v’是连通的。 有向图的连通分支将有向图的方向忽略后任何两个顶点之间总是存在路径则该有向图是弱连通的。有向图的子图是强连通的且不包含在更大的连通子图中则可以称为图的强连通分支。 上图 a 、e没有到 { b , c , d } 中的顶点的路径所以各自是独立的连通分支。因此上图有三个强连通分支用集合写出来就是 { { a } , { e } , { b , c , d } }
3.连通分量 无向图中的极大连通子图称为连通分量。
双连通图不含任何割点的图。
边的权和网
图上的边和弧上带权则称为网 图中每条边上标有某种含义的数值该数值称为该边的权值。这种图称为带树图也称作网。
加权图
加权图与加权图对应的就是无权图又叫等权图。如果一张图不含权重信息我们认为边与边之间没有差别。
邻接和关联
邻接(adjacency)邻接是两个顶点之间的一种关系。如果图包含 (u,v)则称顶点v 与顶点u邻接。在无向图中这也意味着顶点 u 与顶点 v 邻接。
关联(incidence)关联是边和顶点之间的关系。在有向图中边 (u,v)从顶点 u开始关联到 v或者相反从v关联到u。在有向图中边不一定是对称的有去无回是完全有可能的。
路径
两顶点之间的路径指顶点之间经过的顶点序列经过路径上边的数目称为路径长度。若有n个顶点且边数大于n-1此图一定有环。 路径(path)依次遍历顶点序列之间的边所形成的轨迹。 路径非空序列V0 E1 V1 E2 ... Vk称为顶点V0到顶点Vk的一条路径。
树中根节点到任意节点的路径是唯一的但是图中顶点与顶点之间的路径却不是唯一的。 路径的长度是路径上的边或弧的数目。 无权图的路径长是路径包含的边数。 有权图的路径长要乘以每条边的权。
简单路径、简单回路
简单路径没有重复顶点的路径称为简单路径。 除第一个顶点和最后一个顶点外其余顶点不重复出现的回路称为简单回路。
环 环包含相同的顶点两次或者两次以上。上图序列 1,2,4,3,11出现了两次当然还有其它的环比如1,4,3,1。
无环图没有环的图其中有向无环图有特殊的名称DAG(Directed Acyline Graph)
顶点的度、入度和出度
顶点的度为以该顶点为一个端点的边的数目。
对于无向图顶点的边数为度度数之和是顶点边数的两倍。 对于有向图入度是以顶点为终点出度相反。有向图的全部顶点入度之和等于出度之和且等于边数。顶点的度等于入度与出度之和。
割点关节点
割点如果移除某个顶点将使图或者分支失去连通性则称该顶点为割点。某些特定的顶点对于保持图或连通分支的连通性有特殊的重要意义。
割点的重要性不言而喻。如果你想要破坏互联网你就应该找到它的关节点。同样要防范敌人的攻击首要保护的也应该是关节点
桥(割边)
桥(割边)和割点类似删除一条边就产生比原图更多的连通分支的子图这条边就称为割边或者桥。
距离
若两顶点存在路径其中最短路径长度为距离。
有向树
有一个顶点的入度为0其余顶点的入度均为1的有向图称作有向树。
图的表示
邻接列表
邻接列表在邻接列表实现中每一个顶点会存储一个从它这里开始的边的列表。比如如果顶点A 有一条边到B、C和D那么A的列表中会有3条边邻接列表只描述了指向外部的边。A 有一条边到B但是B没有边到A所以 A没有出现在B的邻接列表中。 优点 1 便于增加和删除结点。 2 便于统计边的数目按顶点表顺序扫描所有边表可得到边的数目时间复杂度为O(ne)。 3空间效率高。对于一个具有n个顶点e条边的图G若图G是无向图则在邻接表表示中有n个顶点表结点和2n个边表结点。若G是有向图则在它的邻接表表示或逆邻接表表示中均有n个顶点表结点和e个边表结点。因此邻接表的空间复杂度为O(ne)。 缺点 1 不便于判断顶点之间是否有边要判断vi 和vj之间是否有边就需扫描第i个边表最换情况下要耗费O(n)时间。 2 不便于计算有向图各个顶点的度。
邻接矩阵 图最常见的表示形式为邻接链表和邻接矩阵 特点 ⑴0表示这两个顶点之间没有边1表示有边 ⑵顶点的度是行内数组之和 ⑶求顶点的邻接点遍历行内元素即可
邻接矩阵一个存储着边的信息的矩阵而顶点则用矩阵的下标表示。对于一个邻接矩阵M如果M(i,j)1则说明顶点i和顶点j之间存在一条边对于无向图来说M (j ,i) M (i, j)所以其邻接矩阵是一个对称矩阵对于有向图来说则未必是一个对称矩阵。邻接矩阵的对角线元素都为0。下图是一个无向图和对应的邻接矩阵 需要注意的是当边上有权值的时候称之为网图则邻接矩阵中的元素不再仅是0和1了邻接矩阵M中的元素定义为
邻接矩阵在邻接矩阵实现中由行和列都表示顶点由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连、如果相连这个值表示的是相连边的权重。例如如果从顶点A到顶点B有一条权重为 5.6 的边那么矩阵中第A行第B列的位置的元素值应该是5.6 优点 1 便于判断两个顶点之间是否有 边即根据A[i][j] 0或1来判断。 2 便于计算各顶点的度。对于无向图邻接矩阵的第i行元素之和就是顶点i的度。对于有向图第i行元素之和就是顶点i的出度第i列元素之和就是顶点i的入度。 缺点
1 不便于增加删除顶点。
2空间复杂度高。如果是有向图n个顶点需要n*n个单元存储边。如果无向图其邻接矩阵是对称的所以对规模较大的邻接矩阵可以采用压缩存储的方法仅存储下三角元素这样需要n(n-1)/2个单元。无论哪种存储方式邻接矩阵表示法的空间复杂度均为0(n*n)区别
邻接列表在表示稀疏图时非常紧凑而成为了通常的选择但稀疏图表示时使用邻接矩阵会浪费很多内存空间遍历的时候也会增加开销。 如果图是稠密图可以选择更加方便的邻接矩阵。 还有顶点之间有多种关系的时候也不适合使用矩阵。因为表示的时候矩阵中的每一个元素都会被当作一个表
图的遍历
深度优先遍历 在深度优先搜索中保存候补节点是栈栈的性质就是先进后出即最先进入该栈的候补节点就最后进行搜索。 深度优先遍历也有称为深度优先搜索Depth_First_Search简称DFS。其实就像是一棵树的前序遍历。 它从图中某个结点v出发访问此顶点然后从v的未被访问的邻接点出发深度优先遍历图直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问则另选图中一个未曾被访问的顶点作起始点重复上述过程直至图中的所有顶点都被访问到为止。
#includeiostream
using namespace std;
int n,m,x,y,a[105][105],book[105][105] {};
int minn 999999;
void dfs(int starx,int stary,int step) {int nx,ny;if(starxxstaryy) {if(minn step) {minn step;}return ;}int next[4][2] {0,1,0,-1,1,0,-1,0};for(int i0; i4; i) {nx starxnext[i][0]; ny starynext[i][1];if(nxn||nx1||nym||ny1)continue;if(a[nx][ny]0book[nx][ny]0) {book[nx][ny]1;dfs(nx,ny,step1);book[nx][ny]0;}}return ;
}
int main() {cinnmxy;for(int i1; in; i) {for(int j1; jm; j) {cina[i][j];}}book[1][1]1;dfs(1,1,0);cout最小值为;coutminnendl;return 0;
}
/*
5 4 4 3
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
*/
邻接矩阵表达方式
#define MAXVEX 100 //最大顶点数
typedef int Boolean; //Boolean 是布尔类型其值是TRUE 或FALSE
Boolean visited[MAXVEX]; //访问标志数组
#define TRUE 1
#define FALSE 0//邻接矩阵的深度优先递归算法
void DFS(Graph g, int i)
{int j;visited[i] TRUE;printf(%c , g.vexs[i]); //打印顶点也可以其他操作for(j 0; j g.numVertexes; j){if(g.arc[i][j] 1 !visited[j]){DFS(g, j); //对为访问的邻接顶点递归调用}}
}//邻接矩阵的深度遍历操作
void DFSTraverse(Graph g)
{int i;for(i 0; i g.numVertexes; i){visited[i] FALSE; //初始化所有顶点状态都是未访问过状态}for(i 0; i g.numVertexes; i){if(!visited[i]) //对未访问的顶点调用DFS若是连通图只会执行一次{DFS(g,i);}}
}邻接表存储结构
//邻接表的深度递归算法
void DFS(GraphList g, int i)
{EdgeNode *p;visited[i] TRUE;printf(%c , g-adjList[i].data); //打印顶点也可以其他操作p g-adjList[i].firstedge;while(p){if(!visited[p-adjvex]){DFS(g, p-adjvex); //对访问的邻接顶点递归调用}p p-next;}
}//邻接表的深度遍历操作
void DFSTraverse(GraphList g)
{int i;for(i 0; i g.numVertexes; i){visited[i] FALSE;}for(i 0; i g.numVertexes; i){if(!visited[i]){DFS(g, i);}}
}对比两个不同的存储结构的深度优先遍历算法对于n个顶点e条边的图来说邻接矩阵由于是二维数组要查找某个顶点的邻接点需要访问矩阵中的所有元素因为需要O(n2)的时间。而邻接表做存储结构时找邻接点所需的时间取决于顶点和边的数量所以是O(ne)。显然对于点多边少的稀疏图来说邻接表结构使得算法在时间效率上大大提高。
广度优先遍历
广度优先搜索和深度优先搜索一样都是对图进行搜索的算法都是从起点开始顺着边搜索此时并不知道图的整体结构直到找到指定节点(即终点)。在此过程中每走到一个节点就会判断一次它是否为终点。
广度优先搜索会根据离起点的距离按照从近到远的顺序对各节点进行搜索。而深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止然后再折返开始搜索下一条路径。
在广度优先搜索中有一个保存候补节点的队列队列的性质就是先进先出即先进入该队列的候补节点就先进行搜索。 广度优先搜索将点存储到队列中 广度优先遍历Breadth_First_Search,又称为广度优先搜索简称BFS。 深度遍历类似树的前序遍历广度优先遍历类似于树的层序遍历。
邻接矩阵的广度遍历算法
void BFSTraverse(Graph g)
{int i, j;Queue q;for(i 0; i g.numVertexes; i){visited[i] FALSE;}InitQueue(q);for(i 0; i g.numVertexes; i)//对每个顶点做循环{if(!visited[i]) //若是未访问过{visited[i] TRUE;printf(%c , g.vexs[i]); //打印结点也可以其他操作EnQueue(q, i); //将此结点入队列while(!QueueEmpty(q)) //将队中元素出队列赋值给{int m;DeQueue(q, m); for(j 0; j g.numVertexes; j){//判断其他顶点若与当前顶点存在边且未访问过if(g.arc[m][j] 1 !visited[j]){visited[j] TRUE;printf(%c , g.vexs[j]);EnQueue(q, j);}}}}}
}邻接表的广度优先遍历
void BFSTraverse(GraphList g)
{int i;EdgeNode *p;Queue q;for(i 0; i g.numVertexes; i){visited[i] FALSE;}InitQueue(q);for(i 0; i g.numVertexes; i){if(!visited[i]){visited[i] TRUE;printf(%c , g.adjList[i].data); //打印顶点也可以其他操作EnQueue(q, i);while(!QueueEmpty(q)){int m;DeQueue(q, m);p g.adjList[m].firstedge; 找到当前顶点边表链表头指针while(p){if(!visited[p-adjvex]){visited[p-adjvex] TRUE;printf(%c , g.adjList[p-adjvex].data);EnQueue(q, p-adjvex);}p p-next;}}}}
}对比图的深度优先遍历与广度优先遍历算法会发现它们在时间复杂度上是一样的不同之处仅仅在于对顶点的访问顺序不同。可见两者在全图遍历上是没有优劣之分的只是不同的情况选择不同的算法。
生成树
生成树的性质 一个有n个顶点的连通图的生成树有且仅有n-1条边 一个连通图的生成树并不唯一
