数据结构实验———图实验报告

数 据 结 构

实 验 报 告

目的要求

１．掌握图的存储思想及其存储实现。

２．掌握图的深度、广度优先遍历算法思想及其程序实现。 ３．掌握图的常见应用算法的思想及其程序实现。

实验内容

１．键盘输入数据，建立一个有向图的邻接表。 ２．输出该邻接表。

3．在有向图的邻接表的基础上计算各顶点的度，并输出。 4．以有向图的邻接表为基础实现输出它的拓扑排序序列。 5．采用邻接表存储实现无向图的深度优先递归遍历。

6．采用邻接表存储实现无向图的广度优先遍历。

7．在主函数中设计一个简单的菜单，分别调试上述算法。

源程序：

主程序的头文件：队列 #include <> #include <> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define OVERFLOW -2 typedef int QElemType;

typedef struct QNode{ ata='A'+i;

G->vertices[i].firstarc=NULL; }

for (i=0;ivexnum;)

{ printf(\请输入顶点的数组坐标(若退出，请输入-1)：\ scanf(\ if(i==-1) break;

printf(\请输入顶点所指向下一个顶点的数组坐标：\ scanf(\

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

s->nextarc=G->vertices[i].firstarc; G->vertices[i].firstarc=s; } }

5cata);

for(p=[i].firstarc;p;p=p->nextarc) printf(\ printf(\

} }

egree=0;G->vertices[i].indegree=0;}irstarc;p;p=p->nextarc) {G->vertices[i].degree++;

G->vertices[p->adjvex].degree++; G->vertices[p->adjvex].indegree++; } }

void print_degree(ALGraph G) {

int i;

printf(\ for (i=0;i<;i++)

printf(\ [i].degree,[i].indegree); printf(\ }

ndegree) stack[top++]=i; count=0;

while(top!=0) {

i=stack[--top];

if (count==0) printf(\ else printf(\ count++;

for(p=[i].firstarc;p;p=p->nextarc)

if (![p->adjvex].indegree)stack[top++]=p->adjvex; }

if (count

irstarc) return 0;

else return[v].firstarc->adjvex); }

irstarc;

while(p->adjvex!=u) p=p->nextarc; 出该有向图的度和入度 4.输出该有向图拓扑排序序列 \\n\

printf(\创建一个无向图的邻接表 6.深度优先递归遍历该无向图\\n\

printf(\广度优先遍历该无向图 0.退出 \\n\ printf(\请输入选择： \ scanf(\ switch(select){ case 1:

printf(\创建一个有向图的邻接表：\\n\

creat_link(&G); break; case 2:

printf(\输出该邻接表：\\n\ visit(G); break; case 3:

printf(\输出该有向图的度和入度：\\n\ cacu(&G);

print_degree(G); break; case 4:

printf(\输出该有向图拓扑排序序列：\\n\

if(!TopologiSort(G))printf(\ break; case 5:

printf(\创建一个无向图的邻接表: \\n\ creat_link(&G); break; case 6:

printf(\深度优先递归遍历该无向图: \\n\ DFSTraverse(G); break; case 7:

printf(\广度优先遍历该无向图：\\n\ BFSTraverse(G); break; case 0: break; default:

printf(\输入选项错误！重新输入！\\n\ }

}while(select); }

运行结果截图：

1. 主菜单界面：

2.创建一个有向图的领接表

3.输出该邻接表

4. 在有向图的邻接表的基础上计算各顶点的度，并输出。

5. 输出它的拓扑排序序列

6. 输出所建无向图的邻接表