数据结构与算法图与网.ppt

第五章 图与网 第五章 图与网 5.1 图与网的基本概念 5.1.1 图与网的定义和术语 图的定义 G=(V,E) 5.1.1 图与网的定义和术语 顶点与边的关系 无向图：0≤e≤n(n-1)/2 有向图：0≤e≤n(n-1) 5.1.1 图与网的定义和术语 网的定义 弧或边标上具体的数字，这些数称为权。 带有权的图称为网 5.1.1 图与网的定义和术语 子图的定义 5.1.2图的相关术语 无向图顶点的度 无向图顶点的度等于依附于该顶点的边的数目，例： TD(A)=3 5.1.2图的相关术语 有向图顶点的度 有向图中：分为入度ID(V)和出度OD(V) TD(V)= ID(V)+ OD(V) 例：TD(E)=3，其中出度为OD(E) 1，入度ID(E)为2 5.1.2图的相关术语 顶点的度和边的关系 5.1.2图的相关术语 路径、回路(环)，简单路径 路径：从A到D所经过的顶点序列 回路(环):AEDBA 简单路径：顶点不重复出现 5.1.2图的相关术语 连通图，连通分量 连通图：无向图中，任何两个顶点都连通。 连通分量：非连通图的极大连通子图 5.1.2图的相关术语 强连通图，强连通分量 强连通图：有向图中从Vi到Vj，从Vj到Vi都 存在路径 强连通分量：非强连通图的极大连通子图 5.1.2图的相关术语 连通图的生成树 定义：极小连通子图，包含全部n个顶点，只有n-1条边 5.2 图与网的存储结构 5.2.1邻接矩阵 5.2.1邻接矩阵 网的邻接矩阵 5.2.1邻接矩阵 邻接矩阵类型定义 #define maxvernum 100 #define infinity maxinteger typedef struct {vertextype vex[maxvernum]; int adjmatrix[maxvernum][maxvernum]; int n,e; /*定义顶点数和边或弧数变量单元*/ }mgraph; 5.2.2 邻接表与逆邻接表 无向网的邻接表 5.2.2 邻接表与逆邻接表 有向网的邻接表 5.2.2 邻接表与逆邻接表 邻接表结点定义 邻接表中结点和表头结点的形式描述定义如下： #define maxvernum 100 /*定义表结点结构*/ typedef struct node {int adjvex,info; struct node *next; } nodetype; /*定义表头结点结构*/ typedef struct frontnode {vertextype data; struct node *next; } frontnodetype; typedef frontnodetype adjlist[maxvernum]; 5.2.2 邻接表与逆邻接表 逆邻接表 有向图中为了便于查找以某结点为终点的边 5.2.3 邻接多重表 5.2.3 邻接多重表 结点定义 typedef struct edgenode /*定义边结点类型*/ {int mark ,ivex ,jvex; /*对于网可增加整型info域*/ struct edgenode *ilink,*jlink; }edgenodetype ; /*定义顶点结点类型*/ typedef struct vexnode {int data; struct edgenode *firstedge; }vexnodetype; typedef vexnodetype adjmulist[maxvernum] 5.3图的遍历 从图中某一顶点出发，访问图中其余顶点， 且使每一顶点仅被访问一次。 深度优先有哪些信誉好的足球投注网站遍历 广度优先有哪些信誉好的足球投注网站遍历 5.3.1深度优先有哪些信誉好的足球投注网站遍历 递归算法描述如下，类似树的先根遍历 5.3.1深度优先有哪些信誉好的足球投注网站遍历 深度优先算法的实现 1.先定义存储结构 假设图用邻接表作存储结构 为了在遍历过程中区分顶点是否已被访问过，设置标志数组c[n+1]，初始值全为0，一旦顶点vi被访问时置c[i]为1。 5.3.1深度优先有哪些信誉好的足球投注网站遍历 2.从顶点v 出发按深度优先有哪些信誉好的足球投注网站遍历图的递归算法dfs如 下： void dfs(adjlist g[],int v,int c[]) {int i ; nodetype *p; c[v]=1; printf(“%d\n”,v); /*访问顶点v*/ for(p=g[v].next;p!=NULL;p=p-next) {i=p-ad