Question

数据结构，图的基本操作

Ø1.以邻接表作存储结构，编写深度优先、广度优先的算法。 Ø2、以邻接表作存储结构，编写最小生成树的算法。 Ø3、以邻接表作存储结构，编写最短路径的算法要求 在VC6.0中可以运行

Answer 1

对邻接表存储的图进行深度优先搜索算法：
#include "stdio.h"
#define MAXVER 10 /* 最多顶点数 */
typedef char ElemType; /* 顶点元素类型 */
typedef struct node
{ int num;
struct node *next;
}slink; /* 边或弧的结点类型 */
typedef struct
{ struct
{ ElemType vertex;
slink *first;
}ve[MAXVER]; /* 顶点信息结构 */
int vex,edge,tag; /* 存放顶点数、边数和图的类型 */
}adjlist; /* 邻接表存储结构类型名 */

/* 建立图的邻接表存储表示。 */
void cregraph(adjlist *G,int n,int m) /* 建立邻接表. n为顶点数，m为图的类型 */
{ int i,e=0;slink *p,*q,*s;char x,y;
G->vex=n; G->tag=m;
for(i=0;i<n;i++)
{ G->ve[i].vertex=i+'A'; G->ve[i].first=NULL;} /* 初始化邻接表 */
printf("Input edges(x-->y):"); /* 用大写字母表示顶点 */
scanf("%c%c",&x,&y);
while(x!=' '&&y!=' ') /* 输入边或弧，遇空格符结束 */
{ e++; /* 统计边或弧和数目 */
s=(slink *)malloc(sizeof(slink));
s->num=y-'A'; /* 生成结点插入 */
if(G->ve[x-'A'].first==NULL)
{ G->ve[x-'A'].first=s;
s->next=NULL;
}
else
{ p=G->ve[x-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) {p=q;q=q->next;}
p->next=s;s->next=q;
}
if(!G->tag) /* m=0表示建立无向图的邻接表 */
{ s=(slink *)malloc(sizeof(slink));
s->num=x-'A';
if(G->ve[y-'A'].first==NULL)
{ G->ve[y-'A'].first=s;s->next=NULL;}
else
{ p=G->ve[y-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) { p=q;q=q->next;}
p->next=s;s->next=q;
}
}
scanf("%c%c",&x,&y);
}
G->edge=e;
}
/* 输出用邻接表存储表示的图 */
void list(adjlist *G) /* 输出邻接表 */
{ int i; slink *p;
for(i=0;i<G->vex;i++)
{ printf("%d:%c--->",i,G->ve[i].vertex);
p=G->ve[i].first;
while(p)
{ printf("%3d",p->num);
p=p->next;
}
printf("\n");
}
}
/* 对邻接表存储的图进行深度优先搜索算法 */
int visited[MAXVER+1]; /* 顶点的访问标记数组 */
dfs(adjlist *G,int v) /* v是访问的起始点的下标 */
{ slink *p;
visited[v]=1;
printf("%3c",G->ve[v].vertex);
p=G->ve[v].first;
while(p)
{ if(visited[p->num]==0) /* 从V的未访问过的邻接点出发 */
dfs(G,p->num);
p=p->next; /* 找V的下一个邻接点 */
}
}
void dfsgraph(adjlist *G)
{ int i;
for(i=0;i<G->vex;i++) if(!visited[i]) dfs(G,i);
}
main()
{ adjlist g;
int n=8;
cregraph(&g,n,0);
dfsgraph(&g);
}

对一个采用邻接表作存储结构的图进行广度优先遍历：
/*邻接表结构*/
#include "stdio.h"
#define MAXVER 10 /* 最多顶点数 */
typedef char ElemType; /* 顶点元素类型 */
typedef struct node
{ int num;
struct node *next;
}slink; /* 边或弧的结点类型 */
typedef struct
{ struct
{ ElemType vertex;
slink *first;
}ve[MAXVER]; /* 顶点信息结构 */
int vex,edge,tag; /* 存放顶点数、边数和图的类型 */
}adjlist; /* 邻接表存储结构类型名 */
/*建立邻接表*/
void cregraph(adjlist *G,int n,int m) /* n为顶点数，m为图的类型 */
{ int i,e=0;slink *p,*q,*s;char x,y;
G->vex=n; G->tag=m;
for(i=0;i<n;i++)
{ G->ve[i].vertex=i+'A'; G->ve[i].first=NULL;} /* 初始化邻接表 */
printf("Input edges(x-->y):"); /* 用大写字母表示顶点 */
scanf("%c%c",&x,&y);
while(x!=' '&&y!=' ') /* 输入边或弧，遇空格符结束 */
{ e++; /* 统计边或弧和数目 */
s=(slink *)malloc(sizeof(slink));
s->num=y-'A'; /* 生成结点插入 */
if(G->ve[x-'A'].first==NULL)
{ G->ve[x-'A'].first=s;
s->next=NULL;
}
else
{ p=G->ve[x-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) {p=q;q=q->next;}
p->next=s;s->next=q;
}
if(!G->tag) /* m=0表示建立无向图的邻接表 */
{ s=(slink *)malloc(sizeof(slink));
s->num=x-'A';
if(G->ve[y-'A'].first==NULL)
{ G->ve[y-'A'].first=s;s->next=NULL;}
else
{ p=G->ve[y-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) { p=q;q=q->next;}
p->next=s;s->next=q;
}
}
scanf("%c%c",&x,&y);
}
G->edge=e;
}
/* 输出邻接表 */
void list(adjlist *G) /* 输出用邻接表表示的图 */
{ int i; slink *p;
for(i=0;i<G->vex;i++)
{ printf("%d:%c--->",i,G->ve[i].vertex);
p=G->ve[i].first;
while(p)
{ printf("%3d",p->num);
p=p->next;
}
printf("\n");
}
}
/* 对一个采用邻接表作存储结构的图进行广度优先遍历 */
int visited[MAXVER];
void bfs(adjlist *G,int v)
{ int queue[MAXVER],front,rear,i;/* 定义一个分离队列 */
slink *p;
front=rear=0; /* 队列初始化为空 */
queue[rear++]=v; /* 初始顶点入队列 */
while(front!=rear) /* 队列不空 */
{ v=queue[front++]; /* 出队列访问 */
printf("%c->",G->ve[v].vertex);
visited[v]=1; /* 入访问表 */
p=G->ve[v].first;
while(p!=NULL)
{ for(i=0;i<rear;i++)
if(p->num==queue[i]) break;
if(i>=rear)
queue[rear++]=p->num; /* 该邻接点即没被访问过，也不在队列中，则入队列 */
p=p->next; /* 找V的下一个邻接点 */
}
}
}
void bfsgraph(adjlist *G) /* 若还有不连通的部分，则跳过去访问之 */
{ int i;
for(i=0;i<G->vex;i++)
if(!visited[i]) bfs(G,i);
}
main()
{ adjlist G;
cregraph(&G,8,0);
bfsgraph(&G);
}

最小生成树的算法：
/*求最小生成树的Kruskal算法描述*/
#define MAXE 10
struct edges
{ int bv,tv,w;}; /* 边集类型，存储一条边的起始点bv终止顶点tv和权w */
typedef struct edges edgeset[MAXE+1];
int seeks(int set[],int v)
{ int i=v;
while(set[i]>0)
i=set[i];
return i;
}

kruskal(edgeset ge,int n,int e) /* ge表示的图是按权值从小到大排列的 */
{ int set[MAXE],v1,v2,i,j;
for(i=1;i<=n;i++)
set[i]=0; /* 给set中的每个元素赋初值 */
i=1; /* i表示待获取的生成树中的边数，初值为1 */
j=1; /* j表示ge中的下标，初值为1 */
while(j<n &&i<=e) /* 按边权递增顺序，逐边检查该边是否应加入到生成树中 */
{ v1=seeks(set,ge[i].bv); /* 确定顶点v所在的边通集 */
v2=seeks(set,ge[i].tv);
if(v1!=v2) /* 当v1,v2不在同一顶点集合，确定该边应当选入生成树 */
{ printf(" (%d,%d) ",ge[i].bv,ge[i].tv);
set[v1]=v2;
j++;
}
i++;
}
}
main()
{ edgeset e={{0,0,0},{4,5,2},{3,5,3},{1,4,5},{1,2,6},{2,4,7},{2,5,8},{1,3,9},{3,4,9},{1,5,13},{2,3,14}};
kruskal(e,5,10);
}

最短路径的算法：

#define Max 10 /* 预设最多顶点数 */
#define INFINITY 1000 /* 最大值 */
typedef struct
{ int vexnum,arcnum; /* 顶点数及边或弧的数目 */
char vex[Max]; /* 存顶点信息的一维数组 */
int arc[Max][Max]; /* 存边信息的二维数组 */
}AdjMatrix;

/* 建立有向图的邻接矩阵表示 */
void Creadjm(AdjMatrix *G)
{ int i,j,k,w;
printf("Input vex&arc:");
scanf("%d%d%*c",&G->vexnum,&G->arcnum);/*输入顶点数和边数，并读掉回车符*/
printf("Input Vexinfo:");
for(k=0;k<G->vexnum;k++)
scanf("%c",&G->vex[k]); /* 输入代表顶点的字符 */
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
G->arc[i][j]=INFINITY; /* 初始化邻接矩阵 */
printf("Input %d edges:\n",G->arcnum);
for(k=0;k<G->arcnum;k++)
{ scanf("%d%d%d",&i,&j,&w); /* 输入边或弧 */
G->arc[i][j]=w;
}
}

/* 输出用邻接矩阵表示的有向图 */
void list(AdjMatrix *G)
{ int i,j;
for(i=0;i<G->vexnum;i++)
{ printf("%6c----",G->vex[i]); /* 先输出顶点信息 */
for(j=0;j<G->vexnum;j++)
printf("%4d",G->arc[i][j]); /* 再输出与该顶点有关联的边或弧的信息 */
printf("\n");
}
}

/* 计算从顶点v0到其余各点最短路径算法 */
void dijkstra(AdjMatrix *G,int n,int v0,int d[]) /* d数组存放各顶点最短路径 */
{ int s[Max] ; /* s数组存放顶点是否找到最短路径 */
int i,j,u,mindis;
for(i=0;i<n;i++)
{ d[i]=G->arc[v0][i];s[i]=0;}
s[v0]=1;
for(i=1;i<n;i++)
{ mindis=INFINITY;
for(j=0;j<n;j++)
if(s[j]==0 && d[j]<mindis) { u=j; mindis=d[j];}
s[u]=1; /* 顶点u已找到最短路径 */
for(j=1;j<=n;j++) /* 修改j的最短路径 */
if(s[j]==0&&d[j]>d[u]+G->arc[u][j]) d[j]=d[u]+G->arc[u][j];
}
}

main()
{ AdjMatrix G;
int d[Max],i;
Creadjm(&G);
list(&G);
dijkstra(&G,6,0,d);
for(i=0;i<G.vexnum;i++)
printf("%4d",d[i]);
}