一、
实验目的
1、理解图的结构特点。
2、掌握存储图的方法（邻接表）。
3、掌握图的遍历方法和基本应用。
二、实验内容
图的应用有以下2个实验内容：
1.建立一个有向图，对其实施深度优先遍历
（1） 建立一个有向图
A、定义图的数据结构，要求用邻接表；
B、定义一个函数建立一个有向图。
（2） 对上边有向图进行深度优先遍历
具体算法思想可参考教材算法7.4和算法7.5
（3） 图的程序编制上较难，所以实验内容1给出全部参考算法，做验证性实验。
2. 求图中结点度数的应用
（1）求图中某个顶点（地址编号为i）的出度
int OutputDegree(ALGraph G, int i){
/*返回编号是i的顶点的出度*/
……
}
（2）求图中某个顶点（地址编号为i）的入度(选做)
int InDegree(ALGraph G, int i){
/*返回编号是i的顶点的入度*/
……
}
三、源程序
#include<stdio.h>
#include<stdlib.h>
#define N 20//N表示图的顶点个数
typedef enum{DG,DN,UDG,UDN} GraphKind;//{有向图，有向网，无向图，无向网}？？
typedef struct ArcNode {
int adjvex;//该弧指向顶点位置
struct ArcNode *nextarc;//指向下一条弧的指针
}ArcNode;
typedef struct VNode{
int data;//注意图的顶点信息是整型
ArcNode *firstarc;//指向第一条邻接该顶点（以该顶点为弧尾）的弧的指针
}VNode,Adjlist[N];//最多N个顶点??
typedef struct{
Adjlist vertices;
int vexnum,arcnum;//分别存图的顶点数和弧数
GraphKind kind;//图的种类标志
}ALGraph;//邻接表
void CreateDG(ALGraph *G){//创建一个有向图
int i,j,k;
ArcNode *s;
G->kind=DG;//有向图
printf("分别输入顶点数和弧数：");
scanf("%d%d",&G->vexnum,&G->arcnum);
printf("输入顶点信息，从0开始，编号连续：\n");
for(i=0;i<G->vexnum;i++){
scanf("%d",&G->vertices[i].data);
G->vertices[i].firstarc=NULL;
}
printf("输入%d条弧，弧的信息格式：顶点信息，顶点信息\n",G->arcnum);
for (k=0;k<G->arcnum;k++){//输入每个边信息，注意录入边的形式，例如顶点0,1之间有边，录入正确形式是：0，1
scanf("%d,%d",&i,&j);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=j;
s->nextarc=G->vertices[i].firstarc;
G->vertices[i].firstarc=s;//相当于头插法？
}
}
int visited[N]={0};//全局变量，初值是0，避免重复遍历
void DFS(ALGraph G,int v){//从顶点v出发进行深度优先遍历，注意参数G的类型
ArcNode *w;
visited[v]=1;//用处
printf("%3d",G.vertices[v].data);//输出顶点信息，在屏幕占3个宽度
//找顶点v的邻接点，如果未被访问，则从相应的邻接点出发深度遍历
for(w=G.vertices[v].firstarc;w;w=w->nextarc)
if(!visited[w->adjvex])
DFS(G,w->adjvex);//递归
}
void DFSGraph(ALGraph G){//尝试从各点出发DFS
int i;
for(i=0;i<G.vexnum;i++)
if(!visited[i]){
printf("\n从顶点%d出发，深度遍历的结果：",i);
DFS(G,i);//从i出发深度遍历
putchar('\n');//换行
}
}
int OutputDegree(ALGraph G,int i){//返回编号是i的顶点的出度
int out=0;
ArcNode *s;
s=G.vertices[i].firstarc;
while (s){
out++;
s=s->nextarc;
}
return out;
}
void main(){
int i,outv;
ALGraph G;
CreateDG(&G);//创建一个有向图
DFSGraph(G);//对图G深度优先遍历
printf("查询 号顶点的出度");
scanf("%d",&i);
outv=OutputDegree(G,i);//返回编号是i的顶点的出度
printf("%d\n",outv);
}
四、运行结果
五、实验小结
-
在编写程序之前先复习书本上的知识内容，尽量做到不参照书本由自己思考写出程序。
-
在编写程序时找出了自己还不明白的问题并在报告中做出了批注，帮助记忆复习。
-
课上没想清楚的问题课后要继续思考，在程序很复杂的情况下要画图，先理清楚各个结构体的组成再去思考他要存储的内容及功能。
-
在输入或者书写代码时注意大小写的区分，养成规范良好的习惯，上下文保持一致，多注意上文所定义的函数名。