与顶点v相关的边的条数称作顶点v的度。 路径长度是指路径上边或弧的数目。 若第一个顶点和最后一个顶点相同,则这条路 径是一条回路。 若路径中顶点没有重复出现,则称这条路径为 简单路径。 在无向图中,如果从顶点v到顶点v有路径, 则称v和y连通。如果图中任意两个顶点之间都连通, 则称该图为连通图,否则,将其中的极大连通子图称 为连通分量。 在有向图中,如果对于每一对顶点v和y,从v 到v和从v到v都有路径,则称该图为强连通图;否则, 将其中的极大连通子图称为强连通分量。 请单赤鼠标左键换页!
与顶点v相关的边的条数称作顶点v的度。 路径长度是指路径上边或弧的数目。 若第一个顶点和最后一个顶点相同，则这条路 径是一条回路。 若路径中顶点没有重复出现，则称这条路径为 简单路径。 在无向图中，如果从顶点vi到顶点vj有路径， 则称vi和vj连通。如果图中任意两个顶点之间都连通， 则称该图为连通图，否则，将其中的极大连通子图称 为连通分量。 在有向图中，如果对于每一对顶点vi和vj，从vi 到vj和从vj到vi都有路径，则称该图为强连通图；否则， 将其中的极大连通子图称为强连通分量
6.1.2图的基本操作一 基本操作: (1)创建一个图结构 Create Graph(G) (2)检索给定顶点 Locate vex(G,item) (3)获取图中某个顶点 Get vex(G,) (4)为图中顶点赋值 Putvex(G,w, valuel) (5)返回第一个邻接点 FirstAdjVex(G,y) (6)返回下一个邻接点 NextAdjVex(Gv,w) (7)插入一个顶点 Insert vex(G,v) (8)删除一个顶点 Delete vex(G,v) (9)插入一条边 Inserted(G,V,w) (10)删除一条边 Delete edge(G,V,w) 11)遍历图 Traverse(G,v) 请单鼠标左键换页!
6.1.2 图的基本操作 基本操作： （1）创建一个图结构 CreateGraph(G) （2）检索给定顶点LocateVex(G,item) （3）获取图中某个顶点 GetVex(G,v) （4）为图中顶点赋值 PutVex(G,v,value) （5）返回第一个邻接点 FirstAdjVex(G,v) （6）返回下一个邻接点 NextAdjVex(G,v,w) （7）插入一个顶点 InsertVex(G,v) （8）删除一个顶点 DeleteVex(G,v) （9）插入一条边 InsertEdge(G,v,w) （10）删除一条边DeleteEdge(G,v,w) （11）遍历图Traverse(G,v)
6.2图的存信结构 6.2.1邻接矩阵 有向图的邻接矩阵 具有n个顶点的有向图可以用一个nXn的方形矩阵 表示。假设该矩阵的名称为M,则当y>是该有向 图中的一条弧时,M[ij-1;否则M[ij=0。第个顶点 的出度为矩阵中第中“1”的个数;入度为第列中 1”的个数,并且有向图弧的条数等于矩阵中“1”的 数。 请单赤鼠标左键换页!
6.2 图的存储结构 6.2.1 邻接矩阵 1. 有向图的邻接矩阵 具有n个顶点的有向图可以用一个nn的方形矩阵 表示。假设该矩阵的名称为M，则当<vi ,vj>是该有向 图中的一条弧时，M[i,j]=1；否则M[i,j]=0。第i个顶点 的出度为矩阵中第i行中“1”的个数；入度为第i列中 “1”的个数，并且有向图弧的条数等于矩阵中“1”的 个数
1.2无向图的邻接矩阵 具有n个顶点的无向图也可以用一个nXn的方形矩 阵表示。假设该矩阵的名称为M,则当(v;v;)是该无 向图中的一条边时,M[=Mi,=1;否则, M[ijl=Mij-=0。第i个顶点的度为矩阵中第i行中“1” 的个数或第列中“1”的个数。图中边的数目等于矩阵 中“1的个数的一半,这是因为每条边在矩阵中描述 了两次。 请单赤鼠标左键换页!
1．2 无向图的邻接矩阵 具有n个顶点的无向图也可以用一个nn的方形矩 阵表示。假设该矩阵的名称为M，则当（vi ,vj）是该无 向图中的一条边时，M[i,j]=M[j,i]=1；否则， M[i,j]=M[j,j]=0。第i个顶点的度为矩阵中第i行中“1” 的个数或第i列中“1”的个数。图中边的数目等于矩阵 中“1”的个数的一半，这是因为每条边在矩阵中描述 了两次
01000 00110 M=00010 0000 00100 图6-4 请单鼠标左键换页!
图 6-4