图的设计作业

课程设计题目和内容

一.图的基本操作的实现

1)自选存储结构，输入含n个顶点(用字符表示顶点)和

e条边的图G；

(2)求每个顶点的度，输出结果；

(3)指定任意顶点x为初始顶点，对图G作DFS遍历，输

出DFS顶点序列(提示:使用一个栈实现DFS)；

(4)指定任意顶点x为初始顶点，对图G作BFS遍历，输出

BFS顶点序列(提示:使用一个队列实现BFS)；

(5)输入顶点x,查找图G:若存在含x的顶点，则删除该结

点及与之相关连的边，并作DFS遍历(执行操作3)；否则

输出信息“无X”；

(6)判断图G是否是连通图，输出信息“YES”/“NO”；

(7)如果选用的存储结构是邻接矩阵，则用邻接矩阵的信

息生成图G的邻接表，即复制图G,然再执行操作(2)；反

之亦然。

二.程序中所采用的数据结构及存储结构的说明

1邻接矩阵：适用于图中边或弧的

数目比较多的情况，压缩存储方式结构。

邻接矩阵是表示顶点之间相邻关系的矩阵。若图有n个

顶点，则邻接矩阵是一个n*n阶的方阵，结构唯一。邻

接矩阵A的元素规定为：用邻接矩阵存储网时只需要将

矩阵中的1换为相应的权值，将0用一个不可能存在的

权值代替即可。当图用邻接矩阵表示后图的某些操作的

实现是很方便的，如求某一顶点Vi的第一邻接点，只需

在第i行找到第1个非零元即可。若求某一顶点vi的度,

对于无向图来说，只须统计第i行的非零元个数或第i

列的非零元个数（无向图的邻接矩阵是对称的）；当图

中顶点数确定，插入一条边（V“Vj）只须将矩阵中第i

行j列和第j行i列的元素分别改为1或相应的权值；

插入一条弧i,V。只须将矩阵中第i行j列的元素改为1

或相应的权值即可。

2邻接表：一种链式存储结构

在邻接表中对图的每个顶点建立一个单链表，第i个单

链表中包含第i个顶点的所有邻接点，每一个单链表包

含两种结点，头结点和表结点。

在图的邻接表中，可以比较方便地查找一个顶点的边（出

边）或邻接点（出边邻接点），这只要首先从表头向量

中取出对应的表头指针，然后从表头指针出发进行查找

即可。

邻接表则是以一数组（结构体数组）的元素作为头指针，

后面链接和它相邻的结点.

3邻接矩阵表示法与邻接表表示法的

比较：

1）邻接矩阵是唯一的，邻接表不唯一；

2）存储稀疏图用邻接表，存储稠密图用邻接矩阵；

3）求无向图顶点的度都容易，求有向图顶点的度邻

接矩阵较方便；

4）判断是否是图中的边，邻接矩阵容易，邻接表最

坏时间为0（n）；

5）求边数e,邻接矩阵耗时为0（rT2）,与e无关，

邻接表的耗时

三.算法的设计思想

1邻接矩阵存储图的基本思路：

图用邻接矩阵表示后图的某些操作的实现是很方便的，

如求某一顶点V1的第一邻接点，只需在第i行找到第1

个非零元即可。若求某一顶点X的度，对于无向图来说,

只须统计第i行的非零元个数或第i列的非零元个数（无

向图的邻接矩阵是对称的）；对于有向图来说，第i行

的非零元个数为该顶点的出度，第i列的非零元个数为

该顶点的入度，两者相加为该顶点的度。当图中顶点数

确定，插入一条边（Vi,Vj）只须将矩阵中第i行j列和

第j行i列的元素分别改为1或相应的权值；插入一条

弧i,V。只须将矩阵中第i行j列的元素改为1或相应的

权值即可。

2邻接表存储图的基本思路：

若无向图中有n个顶点e条边，则邻接表需要n个头结

点和2e个表结点。在边稀疏的情况下，采用邻接表比采

用邻接矩阵节省存储空间。

在无向图的邻接表中，顶点Vi的度恰好为第i个链表中

的表结点数。

若有向图中有n个顶点e条弧，则邻接表需要n个头结

点和e个表结点。在有向图的邻接表中，第i个链表中

的结点数为顶点Vi的出度。为求顶点V1的入度，需要遍

历整个邻接表，在所有链表中其邻接点域的值为i的结

点个数为顶点口的入度。在邻接表中，容易找到任意一

顶点的第一邻接点和下一个邻接点，但要判断任意两个

顶点Vi和Vj之间是否有边相连，则须搜索第i或j个链

表，因此，不及邻接矩阵方便。

3深度优先遍历图的基本思路是：

(1)访问图中的指定起始点Vo；

(2)从Vo出发，访问一个与Vo邻接的顶点叫

后，再从W1出发，访问与W1邻接的且未访问的顶点W2。

然后从W2出发，重复上述过程，直到找不到未被访问的

顶点为止。

(3)回退到尚有未被访问过的邻接点的顶点，

从该顶点出发，重复上面的步骤，直到所有被

访问过的顶点的邻接点都已访问为止。

4广度优先遍历是图的实现思路是：

(1)访问图中的指定起始点Vo；

(2)从Vo出发，依次访问Vo的未被访问的邻

接点W),w2,W3,,,,,Wno然后依次访问Wl,W2,W3,,,,,Wn的未被

访问的邻接点。

(3)重复上面的第二步，直到所有顶点的邻

接点都已访问为止。

四.程序清单

#include<stdio.h>

#include<stdlib.h>

#defineNULL0

#definemaxsize10

typedefstructnode

{

intdata;

structnode*next;

}dnode;

typedefstruct

{intvex;

dnode*first;

}Node;

typedefstruct

{

Nodearry[maxsize];

intnum;

}graph;

intvisit[maxsize];

graphcreat()〃创建邻接表

grapha;

dnode*p;

inti,x,y,e;

printf("输入顶点数和边数(以空格分割)：")；

scanf("%d%d",&a.num,&e);

for(i=1;i<=a.num;i++)

{

a.arry[i].first=NULL;

a.arry[i].vex=i;

)

for(i=1;i<=e;i++)

{

printf("输入第%d个顶点的边二i);

scanf("%d%d",&x,&y);

p=(dnode*)malloc(sizeof(dnode));

p->data=y;

p->next=a.arry[x].first;

a.arry[x].first=p;

p=(dnode*)malloc(sizeof(dnode));

p->data=x;

p->next=a.arry[y].first;

a.arry[y].first=p;

returna;

voidcopy(graphb,intv[][maxsize])〃令B接矩阵与令B接表

转换

{

inti,j;

dnode*p;

for(i=1;i<=b.num;i++)

for(j=1;j<=b.num;j++)

v[i]U]=O;

for(i=1;i<=b.num;i++)

(

p=(dnode*)malloc(sizeof(dnode));

p=b.arry[i].first;

while(p)

v[i][p->data]=1;

p=p->next;

for(i=1;i<=b.num;i++)

for(j=1;j<=b.num;j++)

printf("%d",v[i][j]);

printf("\n")；

)

)

voidvexdu(grapha)//求度数

{

dnode*p;

inti,count;

for(i=1;i<=a.num;i++)

(

p=a.arry[i].first;

count=0;

while(p)

{

count++;

p=p->next;

)

printf("%d的度数:％d\rT,a.arry[i].vex,count);

voidclr()

inti;

for(i=1;i<=maxsize;i++)

visit[i]=0;

)

voiddfs(grapha,intv)

{

dnode*p;

if(a.arry[v].vex!=O)

printf("%d",a.arry[v].vex);

visit[v]=1;

p=a.arry[v].first;

while(p)

if(!visit[p->data])

dfs(a,p->data);

p=p->next;

voidfindl(grapha)

intv;

clr();

printf("输入开始搜索节点：");

scanf("%d",&v);

dfs(a,v);

printf("\n");

)

voidfind2(grapha)

{

intx,i;

dnode*p,*q;

dr()；

printf("输入要查找删除的点：")；

scanf("%d",&x);

for(i=1;i<=a.num;i++)

if(a.arry[i].vex==x)break;

if(i>a.num)

printf("没找到！\rT);

return;

)

else

{

printf("找至U!\n");

q=p=a.arry[i].first;

a.arry[i].vex=O;

if(p->data==x)p=p->next;

else

while(p)

(

if(p->data==x)

{

q->next=p->next;

break;

)

q=p;

p=p->next;

)

)

dfs(a,x);

printf("\n");

voidfind3(grapha)

inti;

clr();

dfs(a,1);

for(i=1;i<a.num;i++)

if(visit[i]==O)

{

printf("此图不是连通的。\n")；

return;

)

printf("此图不是连通的。\n");

return;

)

voidfind4(grapha)

(

intv[maxsize][maxsize];

copy(a,v);

voidmain()

graphh;

h=creat();

vexdu(h);

find1(h);

find2(h);

find3(h);

find4(h);

}

五.运行结果

6*C:\DOCUIEITSAUDSETTIIGSXADIINISTRATOR.IICROSOF-ABlFF7\^ffi\Debug\fe...

以

敢

好

入

顶V

j44

边

□点L

入

T顶12

度

点

边

个

入

顶22

边

点

入

个

顶32

度

点

边

入

顶