数据结构作业
2002 年第七章 图
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 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）邻接表；
A ∧
B
C
D
E
F
1
2
3
4
5
6
1 ∧
图 邻接表序号 头结点 数组 表 结点 单链表
4 ∧1
3 6 ∧5
6 ∧2
1 5 ∧2
（ 4）逆邻接表；
A
B
C
D
E
F
1
2
3
4
5
6
图逆 邻接表序号 头结点 数组 表 结点 单链表
6 ∧3
2 6 ∧5
4 ∧
2 ∧
6 ∧4
6 ∧3
（ 5）强连通分量。
B D
A E F
C
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 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;i<= G->vexnum;i++) /*图 G的邻接矩阵第 G->vexnum*/
{ G->arcs[G->vexnum][i]=val; /*行、列设置为 val*/
G->arcs[i][G->vexnum]=val;
}
return 1; /*成功返回 */
}
int InsertArc(MGraph *G,VertexType V,VertexType w)
{ int i=0,j=0,k,val;
for(k=1;k<= G->vexnum;k++) /*查询顶点 v的序号 i*/
if (G-> vexs[k]==v) i=k;
for(k=1;k<= G->vexnum;k++) /*查询顶点 w的序号 j*/
if (G-> vexs[k]==w) j=k;
if (i==0 || j==0 || i==j ) /*失败返回 */
{
printf(“弧不存在” );
return 0;
}
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; /*成功返回 */
}
int DeleteArc(MGraph *G,VertexType V,VertexType w)
{
int i=0,j=0,k,val;
for(k=1;k<= G->vexnum;k++) /*查询顶点 v的序号 i*/
if (G-> vexs[k]==v) i=k;
for(k=1;k<= G->vexnum;k++) /*查询顶点 w的序号 j*/
if (G-> vexs[k]==w) j=k;
if (i==0 || j==0 || i==j) /*失败返回 */
{
printf(“弧不存在” );
return 0;
}
val=(G->kind==DG||G->kind==UDG)? 0,INFINITY;
G->arcs[i][j]=val;
if (G->kind==UDG || G->kind==UDN) /*图 G为无向图、无向网时 */
G->arcs[j][i]=val;
return 1; /*成功返回 */
}
int DeleteVex(MGraph *G,VertexType V )
{ int i=0,j,k;
for(i=1;i<= G->vexnum;i++) /*查询顶点 v的序号 k*/
if (G-> vexs[i]==v) k=i;
if ( k==0 ) {/*失败返回 */
printf(“顶点不存在” );
return 0;}
/*从顶点数组中删除第 k个顶点，后续顶点据向前移动 */
for(i=k+1;i<= G->vexnum;i++)
G->vexs[i-1]= G->vexs[i];
/*从邻接矩阵中删除第 k（行、列）,后续（行、列）数据向前移动 */
for(i=k+1;i<= G->vexnum;i++)
for(j=1;j<= G->vexnum;j++)
{
G->arcs[i-1][j]= G->arcs[i][j]; /*后续行的前移 */
G->arcs[j][i-1]= G->arcs[j][i]; /*后续列的前移 */
}
G->vexnum--;
return 1; /*成功返回 */
}
/* 注,也可以简单的将第 G->vexnum位置数据复制到第 k位置 */