表的第一个元素a1为广义表GL的表头,其余部分(a2,…,a,ai+1,…,an)为L的表尾 第8章图 1.图的基本概念 (1)顶点的度、入度和出度 (2)完全图 (3)子图 (4)路径和路径长度 (5)连通、连通图和连通分量 (6)强连通图和强连通分量 (7)权和网 2.图的存储结构 (1)邻接矩阵存储方法 邻接表存储方法 掌握两种存储方法的优缺点,同一种功能在不同存储结构上的实现算法。 3.图的遍历 (1)深度优先搜索遍历 void DFS(ALGraph *G, int v) I ArcNode*p: Visited[v]=1 置已访问标记* printf("%d v) /*输出被访问顶点的编号*/ p=G-> adjlist[v]. firstarc;/*p指向顶点v的第一条弧的弧头结点* while (p!=NULL) I if (visited [p->adjvex]=o) DFS (G, p->ad jex) p= p->nextarc;}}/p指向顶点v的下一条弧的弧头结点*/ (2)广度优先搜索遍历 void BFS(ALGraph *G, int v) ArcNode *p int queue [MAXV], front=0,rear=0;/*定义循环队列并初始化* int visited[MAXV] /*定义存放结点的访问标志的数组* for(i=0;i<G->n;i++) visited[i]=0;/*访问标志数组初始化*/ f("%2d",v) visited[v]= /*置已访问标记*/ rear=(rear+1)%MAXV queue [rear] /*v进队* while( front!=rear)/*若队列不空时循环* I front=(front+1)%MAXV W= queue[ front]:/*出队并赋给w*/ while (p! =NULL t if (visited [p->adjvex]==0) printf("%2d", p->adjvex) visited Lp->adjvex]=l rear=(rear+1)%MAXV p=p->nextarc:) I printf("\n"): 1 (3)非连通图的遍历 采用深度优先搜索遍历非连通无向图的算法如下: for (i=0: i<g->n: i+) if (visitedlil=o)表的第一个元素 a1 为广义表 GL 的表头，其余部分(a2，…，ai，ai+1，…，an )为 GL 的表尾. 第 8 章 图 1.图的基本概念 (1)顶点的度、入度和出度 (2)完全图 (3)子图 (4)路径和路径长度 (5)连通、连通图和连通分量 (6)强连通图和强连通分量 (7)权和网 2.图的存储结构 (1) 邻接矩阵存储方法 (2)邻接表存储方法 掌握两种存储方法的优缺点，同一种功能在不同存储结构上的实现算法。 3.图的遍历 （1）深度优先搜索遍历 void DFS(ALGraph *G,int v) { ArcNode*p;Visited[v]=1; /*置已访问标记*/ printf("%d ",v); /*输出被访问顶点的编号*/ p=G->adjlist[v].firstarc; /*p 指向顶点 v 的第一条弧的弧头结点*/ while (p!=NULL) { if (visited[p->adjvex]==0) DFS(G,p->adjvex); p=p->nextarc; }} /*p 指向顶点 v 的下一条弧的弧头结点*/ （2）广度优先搜索遍历 void BFS(ALGraph *G,int v) { ArcNode *p; int queue[MAXV],front=0,rear=0; /*定义循环队列并初始化*/ int visited[MAXV]; /*定义存放结点的访问标志的数组*/ int w,i; for (i=0;i<G->n;i++) visited[i]=0; /*访问标志数组初始化*/ printf("%2d",v); visited[v]=1; /*置已访问标记*/ rear=(rear+1)%MAXV; queue[rear]=v; /*v 进队*/ while (front!=rear) /*若队列不空时循环*/ { front=(front+1)%MAXV; w=queue[front]; /*出队并赋给 w*/ p=G->adjlist[w].firstarc; while (p!=NULL) { if (visited[p->adjvex]==0) { printf("%2d",p->adjvex); visited[p->adjvex]=1; rear=(rear+1)%MAXV; queue[rear]=p->adjvex; } p=p->nextarc; } } printf("\n");} (3)非连通图的遍历 采用深度优先搜索遍历非连通无向图的算法如下： DFS1(ALGraph *g) { int i; for (i=0;i<g->n;i+) if (visited[i]==0)