实验五 图
一、 实验目标
1． 掌握建立无向图（有向图）的邻接矩阵和邻接表算法。
2． 掌握无向图的深度优先遍历和广度优先遍历算法。
3． 理解连通图的最小生成树算法（普里姆算法）。
4． 理解有向无环图的拓扑排序算法。
二、 实验内容
1. 图的深度优先遍历在链式存储结构（邻接表）上的实现。其中函数 createadjlist 的功能
是实现建立邻接表，函数 dfs 的功能是实现图的深度优先遍历算法。
#include "stdio.h"
#define m 100
#include "stdlib.h"
#define n 6
#define e 6
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);
p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j;
p->nextarc=g[i].firstarc; g[i].firstarc=p;
p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i;
p->nextarc=g[j].firstarc; g[j].firstarc=p;
}
}
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);
}
2. 图的广度优先遍历在顺序存储结构（邻接矩阵）上的实现。其中函数 creatematrix 的功
评论2