实验8 图的基本知识

实验目的：

1、了解图的概念 2、掌握图的各种属性

3、掌握图的深度和广度遍历

实验内容：

1、在给定的头文件cg.h（实现的是无向图和有向图的邻接矩阵和邻接表的生成）的基础上实现如下功能：统计有向图的出度，入度和度。 #include \"stdio.h\" #include \"malloc.h\"

#define VERTEX_MAX 30 /*最大顶点数*/ #define MAXSIZE 20

/*============以下为邻接矩阵的结构描述============*/ typedef char Vextype[3]; /*顶点类型*/ typedef struct {

Vextype vexs[VERTEX_MAX]; /*顶点信息*/

int arcs[VERTEX_MAX][VERTEX_MAX]; /*邻接矩阵存储 */ int vexnum,arcnum; /*顶点数、边数*/ } MGraph;

/*=============以下为邻接表的结构描述============*/ typedef struct node /*边结点定义*/ { int adjvex; /*邻接点域*/

struct node *next; /*指向下一个边结点的指针域*/ }EdgeNode;

typedef struct vnode /*表头结点定义*/ { Vextype vertex; /*顶点信息*/ EdgeNode *firstedge; }VertexNode;

typedef struct /*图的邻接表存储*/ { VertexNode adjlist[VERTEX_MAX]; int n,e; /*顶点数和边数*/ } ALGraph;

/*============以下为创建有向图的邻接矩阵过程=========*/ void creat_MGraph2(MGraph *g) {

int i,j,k; int n,m;

printf(\"以下是邻接矩阵操作，请输入顶点数vex和边数arc:\"); /*入顶点数n和边数m*/

scanf(\"%d,%d\ g->vexnum=n;

输 g->arcnum=m;

printf(\"请输入顶点信息:\"); /*输入顶点信息，如V0,V1等*/ for (i=0;iscanf(\"%s\

for (i=0;iarcs[i][j]=0;

printf(\"请输入两个顶点间的边edge(i,j)\\n\");

for (k=0;kscanf(\"%d,%d\ g->arcs[i][j]=1; }

printf(\"创建成功!\\n\"); }

/*============以下为创建有向图的邻接表过程=========*/ void CreateALGraph2(ALGraph *G) { int i,j,k; EdgeNode * s;

printf(\"以下是邻接表操作：请输入顶点数vex和边数arc，如3,3:\"); /*输入顶点数n和边数m*/

scanf(\"%d,%d\

printf(\"请输入顶点信息，如V0回车V1等:\"); /*输入顶点信息，如V0,V1等*/

for (i=0;in;i++)

{ scanf(\"%s\ G->adjlist[i].firstedge=NULL; }

printf(\"请输入两个顶点间的弧edge如0,1\\n\"); /*请输入弧的信息*/

for (k=0;ke;k++) /*建立边表*/ { scanf(\"%d,%d\

s=(EdgeNode*)malloc(sizeof(EdgeNode)); s->adjvex=j;

s->next=G->adjlist[i].firstedge; /*前插方法*/ G->adjlist[i].firstedge=s; }

}/*CreateALGraph*/

void printMG(MGraph *g) /*输出邻接矩阵*/ {

int i,j;

for (i=0;ivexnum;i++) {for (j=0;jvexnum;j++)

printf(\" %d\

printf(\"\\n\"); } }

void printALG(ALGraph *g) /*输出邻接表*/ {

int i,j;

EdgeNode *p;

for (i=0;in;i++)

{ printf(\"%s\ p=g->adjlist[i].firstedge; while (p) {

printf(\"->%d\ p=p->next; }

printf(\"\\n\"); } }

void f_ind(ALGraph *G) //此函数为实现利用邻接表统计出度，入度和总度 {

int i;

int ind[VERTEX_MAX]={0}; int outd[VERTEX_MAX]={0}; int totald[VERTEX_MAX]={0};

/*3个变量分别为入度、出度和总度数*/ EdgeNode *p;

for (i=0;in;i++) /*求出度和入度*/ {

p=G->adjlist[i].firstedge; while (p!=NULL) {

ind[p->adjvex]++; outd[i]++; p=p->next; } }

for (i=0;in;i++) {

totald[i]=ind[i]+outd[i];//求总度 }

printf(\"顶点 入度 出度 度：\\n\"); for(i=0;in;i++) {

printf(\"%s %d %d %d\\notald[i]); } }

void h_ind(MGraph *G) //此函数为实现利用邻接矩阵统计出度，入度和总度 {

int i,j;

int ind[VERTEX_MAX]={0}; int outd[VERTEX_MAX]={0};

int totald[VERTEX_MAX]={0};

/*3个变量分别为入度、出度和总度数*/

for (____________i=0;ivexnum;i++_________) /*求出度和入度*/ {

for(_______j=0;jvexnum;j++_______________) {

if(G->arcs[i][j]==1) {

ind[j]++; outd[i]++; } } }

for (i=0;ivexnum;i++) {

____totald[i]=ind[i]+outd[i]; __;//求总度 }

printf(\"顶点 入度 出度 度：\\n\"); for(i=0;ivexnum;i++) {

printf(\"%s %d %d %d\\n\; } }

int main() {

int i,j; ALGraph *g; EdgeNode *p;

g=(ALGraph *)malloc(sizeof(ALGraph)); CreateALGraph2(g);

printALG(g); f_ind(g);

MGraph *h;

h=(MGraph *)malloc(sizeof(MGraph)); creat_MGraph2(h); printMG(h); h_ind(h); }