实验五 图
一、 实验目标
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);
}