数据结构实验程序参考

#define MAX 20 typedef int vextype; typedef struct arcnode

{ int adjvex; /*弧所指向的顶点序号*/

struct arcnode *nextarc; /*指向下一条弧结点*/ }arcnode;

typedef struct vexnode

{ vextype vexdata; /*顶点信息*/

arcnode *firstarc; /*指向第一条从该顶点出发的弧*/ }vexnode; typedef struct

{ vexnode adjlist[MAX]; int vexnum; /*图的顶点数*/ }ALgraph;

creat_adjlist(ALgraph *g) { arcnode *ptr; int n,i,v1,v2;

printf(\

scanf(\ /*输入顶点数*/ g->vexnum=n; for (i=0;i

{ g->adjlist[i].firstarc=NULL;/*邻接表指针初始化*/ g->adjlist[i].vexdata=i+1;

/* scanf(\ g->adjlist[i].vexdata=ch;*/ }

while(1)

{ printf(\

scanf(\ if((v1==0)&&(v2==0)) break;

ptr=(arcnode*)malloc(sizeof(arcnode)); ptr->adjvex=v2-1;

ptr->nextarc=g->adjlist[v1-1].firstarc; g->adjlist[v1-1].firstarc=ptr;

ptr=(arcnode*)malloc(sizeof(arcnode)); ptr->adjvex=v1-1;

ptr->nextarc=g->adjlist[v2-1].firstarc; g->adjlist[v2-1].firstarc=ptr; } }

int visited[MAX]; /*标志数组*/ dfstraverse (ALgraph g) { int v;

for(v=0;v

dfs(ALgraph g, int v0) /* 从顶点v出发遍历*/ { int w; arcnode *p;

printf(\ p=g.adjlist[v0].firstarc;

while(p) { w=p->adjvex;

if(!visited[w]) dfs(g,w); p=p->nextarc; } }

bfs(ALgraph g, int v0) { int u,v,w; arcnode *p;

int front=-1, rear=-1, queue[MAX];

for(v=0;vadjvex; if(!visited[w])

{ printf(\ queue[++rear]=w; }

p=p->nextarc; } }

} void main() { ALgraph g; creat_adjlist(&g);

printf(\ printf(\ printf(\}

7. 图的遍历（用邻接矩阵作存储结构）

#include #define MAXVEX 20 typedef struct

{ int arcs[MAXVEX][MAXVEX]; int vexnum; }Mgraph;

void creat_Mgraph(Mgraph *g) { int i,j,n,v1,v2;

printf(\ g->vexnum=n; for(i=0;iarcs[i][j]=0; printf(\