《数据结构》课程设计：停车场管理系统

实验五 图

一、 实验目标

1． 掌握建立无向图（有向图）的邻接矩阵和邻接表算法。

2． 掌握无向图的深度优先遍历和广度优先遍历算法。

3． 理解连通图的最小生成树算法（普里姆算法）。

4． 理解有向无环图的拓扑排序算法。

二、 实验内容

1. 图的深度优先遍历在链式存储结构（邻接表）上的实现。其中函数 createadjlist 的功能

int visited[m];

typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode;

typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode;

void createadjlist(glinkheadnode g[ ])

{

int i,j,k; glinklistnode *p;

for(i=0;i<n;i++) {g[i].vertexinfo=i; g[i].firstarc=0;}

for(k=0;k<e;k++)

{

scanf("%d,%d",&i,&j);

void dfs(glinkheadnode g[ ], int v0)

{

glinklistnode *p;

printf("%d ",v0); visited[v0]=1; p=g[v0].firstarc;

while(p!=0){ if(visited[p->adjvertex]==0)dfs(g,p->adjvertex); p=p->nextarc; }

}

main( )

{

glinkheadnode g[m]; createadjlist(g); dfs(g,0);

}