计算机软件基础课件：图.pptxVIP

;目;;;图的基本概念;无向图：在无向图中，顶点对(x,y)是无序的。

有向图：在有向图中，顶点对x,y是有序的。

无向完全图：若有n个顶点的无向图有n(n-1)/2条边,则此图为无向完全图。即任何2顶点间均有一条边存在。

有向完全图：有n个顶点的有向图有n(n-1)条弧,则此图为有向完全图。即任何2顶点间均有一对方向相反的弧存在。;;权：某些图的顶点或边具有与它相关的数,称之为权。这种带权图叫做网络。

如：交通网的公里数、工程造价图中的造价

顶点的度TD(v)：一个顶点v的度是与它相关联的边的条数。在有向图中,顶点的度等于该顶点的入度与出度之和。

入度ID(v):是以v为终点（弧头）的弧的条数

出度OD(v):是以v为始点（弧尾）的弧的条数;;路径：在图G＝(V,E)中,若从顶点vi出发,沿一些边经过一些顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vivp1vp2...vpmvj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应是属于E的边。;路径长度：非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。

简单路径：若路径上各顶点v1,v2,...,vm均不互相重复,则称这样的路径为简单路径。

回路：若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的路径为回路或环。;;;图的存储结构;无向图的邻接矩阵是对称的;

有向图的邻接矩阵可能是不对称的。;在无向图的邻接表中,统计第i行(列)1的个数可得顶点I的度。

在有向图的邻接表中,统计第i行1的个数可得顶点i的出度，统计第j列1的个数可得顶点j的入度。;1;#defineMaxVerNum100//最大结点数

typedefintVertType;//结点类型

typedefintEdgeType;//边的类型

typedefstruct

{intn;//顶点数VertTypevexs[MaxVerNum];//顶点结构

inte;//边的个数

EdgeTypeedges[MaxVerNum][MaxVerNum];//边结构

}Mgraph;

;建立有向图G的邻接矩阵存储;邻接矩阵的特点;由顺序存储的顶点表及n个链式存储的边链表两部分组成;顶点表：存放顶点本身的数据信息，表中每个表目对应于图的???个顶点，包括两个字段：

VerTex：顶点信息

Firstedge：指向边链表的第一个结点;typedefstructnode//边结点

{intadjvex;//邻接点域

intinfo;//权值（可选）

structnode*next;//边链表指针

}EdgeNode;;无向图的邻接表的建立过程：;voidCreateALGraph(ALGraph*G)//建立有向图的邻接表存储

{inti，j，k；EdgeNode*p；

scanf(“%d，%d”，(G-n)，(G-e)；//读入顶点数和边数

for(i=0；iG-n；i++)//建立有n个顶点的顶点表

{scanf(“%c”，(G-adjlist[i].vertex))；//读入顶点信息

G-adjlist[i].firstedge=nil；//顶点的边表头指针设为空

}

for(k=0；kG-e；k++)/建立边表

{scanf(“%d，%d”，i，j);//读入边Vi，Vj的顶点对应序号

p=(EdgeNode*)malloc(sizeof(EdgeNode))；//生成新边表结点p

p-adjvex=j；//邻接点序号为j

p-next=G-adjlist[i].firstedge；//将边结点插入到顶点Vi的链表头部

G-adjlist[i].firstedge=p；

}

};有向图的