20023
数据结构作业 2002 年 第七章 图
71已知如右图所示的有向图请给出 (1)各顶点的入/出度; (2)邻接矩阵; (3)邻接表; (4)逆邻接表; (5)强连通分量。 解答:(1) 顶点入度出度顶点入度出度 B ACE 2 D 233
7.1 已知如右图所示的有向图，请给出 （1）各顶点的入/出度； （2）邻接矩阵； （3）邻接表； （4）逆邻接表； （5）强连通分量。 B D A E F C 解答：（1） 顶点 入度 出度 顶点 入度 出度 A 3 0 B 2 2 C 1 2 D 1 3 E 2 1 F 2 3
(2)邻接矩阵; A C DE F A(000000 V[1..6] B100100 C010001 AB CDEF D001011 123456 E100000 顶点数组 F(110010 邻接矩阵
（2）邻接矩阵； A B C D E F A 0 0 0 0 0 0 B 1 0 0 1 0 0 C 0 1 0 0 0 1 D 0 0 1 0 1 1 E 1 0 0 0 0 0 F 1 1 0 0 1 0 M= 邻接矩阵 A B C D E F 1 2 3 4 5 6 顶点数组 V[1..6]
(3)邻接表; 序号头结点数组表结点单链表 123456 ABCDEF 1[4 3→D[6人 →区[5 图邻接表
（3）邻接表； A ∧ B C D E F 1 2 3 4 5 6 1 ∧ 图邻接表 序号 头结点数组 表结点单链表 1 4 ∧ 3 5 6 ∧ 2 6 ∧ 1 2 5 ∧
4)逆邻接表; 序号头结点数组表结点单链表 ⑤→[6 123456 ABCDEF 4 图逆邻接表
（4）逆邻接表； A B C D E F 1 2 3 4 5 6 图逆邻接表 序号 头结点数组 表结点单链表 3 6 ∧ 2 5 6 ∧ 4 ∧ 2 ∧ 4 6 ∧ 3 6 ∧
(5)强连通分量
（5）强连通分量。 B D A E F C
。15 #define maX VErteX num2o /图中最多顶点数* #define nfinity 32767 /定义无穷大* /DG:有向图,DN:有向网,UDG:无向图,UDN:无向网* typedefenum DG, DN, UDG, UDN Graph Kind; typedef char VertexType;/假定顶点数据类型为字符* typedef struct /定义存储图的数据类型* VertexType vexsIMAX VERTEX NUM+1;/顶点数组 int arcs MAX VERTEX NUM+IMAX VERTEX NUM+1 /邻接矩阵 vexnum /顶点数 Graph Kind kind; /图类型:DG,DN,UDG,UDN* 3 MGraph;
7。15 #define MAX_VERTEX_NUM 20 /*图中最多顶点数*/ #define INFINITY 32767 /*定义无穷大*/ /* DG：有向图,DN：有向网,UDG：无向图,UDN：无向网*/ typedef enum {DG,DN,UDG,UDN} GraphKind; typedef char VertexType; /*假定顶点数据类型为字符*/ typedef struct { /*定义存储图的数据类型*/ VertexType vexs[MAX_VERTEX_NUM+1]; /*顶点数组*/ int arcs[MAX_VERTEX_NUM+1][MAX_VERTEX_NUM+1]; /*邻接矩阵*/ int vexnum; /*顶点数*/ GraphKind kind; /*图类型：DG,DN,UDG,UDN */ } MGraph;
int Insert Vex ( MGraph *G, Vertex Type v) finti, val; if(G->vexnum>=MAX VERTEX NUM) printf(OVERFLOW”); return0;}失败返回* G->vexnum++ /图G的顶点数加1* G-> vexs G->vexnum=v; /顶点数据写入图G的顶点数组中 val=(G->kind==DGG->kind==UDG)?0: INFINITY; for(i=l; ivexnum; i++) /图G的邻接矩阵第G> vexnum* {G-> arcs-> vexnum[ ival;/行、列设置为val*/ G->arcsilIG->vexnum=val; return1;/成功返回
int InsertVex(MGraph *G， VertexType v) {int i，val; if (G->vexnum> =MAX_VERTEX_NUM ) { printf(“OVERFLOW”); return 0;} /*失败返回*/ G->vexnum++; /*图G的顶点数加1*/ G-> vexs[G->vexnum]=v; /*顶点数据写入图G的顶点数组中*/ val=(G->kind==DG||G->kind==UDG) ? 0 : INFINITY; for(i=1;ivexnum;i++) /*图G的邻接矩阵第G->vexnum*/ { G->arcs[G->vexnum][i]=val; /*行、列设置为val*/ G->arcs[i][G->vexnum]=val; } return 1; /*成功返回*/ }
int InsertArc(MGraph *G, Vertex Type V, Vertex Type w) i int i=0,j=0, k, val: for(k=1;k vexnum;k+)/查询顶点v的序号 if(G-> vexs(k]=v) i-k for(k=1;k vexnum;k+)/查询顶点w的序号j if (G-> vexs[k==w) j=k; if(i=0‖j==0i=j) /失败返回 printi(“弧不存在”); return 0?
int InsertArc(MGraph *G, VertexType V , VertexType w) { int i=0,j=0,k,val; for(k=1;kvexnum;k++) /*查询顶点v的序号i*/ if (G-> vexs[k]==v) i=k; for(k=1;kvexnum;k++) /*查询顶点w的序号j*/ if (G-> vexs[k]==w) j=k; if (i==0 || j==0 || i==j ) /*失败返回*/ { printf(“弧不存在”); return 0; }
if (G->kind==DGIG->kind=UDG /*区分图和网* val printi(“输入权值:”); scanf(“%od”,&val); G->arcsin=val; ifG->kind=UDGG->kind=UDN)/图G为无向图、无向网* G->arcsili-val return1;/成功返回
if (G->kind==DG||G->kind==UDG) /*区分图和网*/ val= 1 ; else { printf(“输入权值：”）； scanf(“%d”, &val); } G->arcs[i][j]=val; if (G->kind==UDG|| G->kind==UDN) /*图G为无向图、无向网*/ G->arcs[j][i]=val; return 1; /*成功返回*/ }