#define maxnode 40
#define null 0
#define m 20
#include <stdio.h>
#include <stdlib.h>
typedef struct st_arc
{int adjvex;
int weight;
struct st_arc *nextarc;
}arcnode;
typedef struct
{int vertex;
struct st_arc *firstarc;
}vernode;
typedef vernode adjlist[maxnode];
int queue[maxnode];
void dfs(adjlist g,int k,int visited[]) //从顶点k出发，深度优先搜索
{arcnode *p;
int w;
visited[k]=1;
printf("%d",g[k].vertex);
p=g[k].firstarc;
while(p!=null)
{w=p->adjvex;
if(visited[w]==0)
dfs(g,w,visited);
p=p->nextarc;
}
}
void bfs(adjlist g,int k,int visited[]) //从顶点k出发，广度优先搜索
{int front=0,rear=1,w;
arcnode *p;
visited[k]=1; //访问初始顶点
printf("%d",k);
queue[rear]=k; //初始顶点入队列
while(front!=rear) //队列不为空
{front=(front+1)%m;
w=queue[front]; //按访问次序依次出队列
p=g[w].firstarc;
while(p!=null)
{if(visited[p->adjvex]==0)
{visited[p->adjvex]=1;
printf("%d",p->adjvex);
rear=(rear+1)%m;
queue[rear]=p->adjvex;;
}
p=p->nextarc;
}
}
}
void trave_bfs(adjlist g,int n)
{int i,visited[maxnode]; //数组visited标志图中的顶点是否已被访问
for(i=1;i<=n;i++)
visited[i]=0;
for(i=1;i<=n;i++)
if(visited[i]==0)
bfs(g,i,visited);
}
void trave_dfs(adjlist g,int n)
{int i,visited[maxnode]; //数组visited标志图中的顶点是否已被访问
for(i=1;i<=n;i++)
visited[i]=0;
for(i=1;i<=n;i++)
if(visited[i]==0)
dfs(g,i,visited);
}
void print(adjlist g,int n)
{arcnode *q;
int i;
printf("输出无向图的邻接链表示：\n");
for(i=1;i<=n;i++)
{printf("\t%d\t",i);
printf("%d->",g[i].vertex);
q=g[i].firstarc;
while(q!=null)
{printf("%d",q->adjvex);
printf("%d->",q->weight);
q=q->nextarc;
}
printf("\n");
}
}
int main()
{arcnode *p,*q;
adjlist g;
int i,j,n,k,w,e;
printf("输入图中顶点的个数,边数：");
scanf("%d,%d",&n,&e);
for(k=1;k<=n;k++)
{getchar();
printf("\t第%d个顶点信息:",k);
scanf("%d",&g[k].vertex);
g[k].firstarc=null; //对顺序存储部分初始化
}
for(k=1;k<=e;k++)
{printf("第%d条边的起点，终点，权值：",k);
scanf("%d,%d,%d",&i,&j,&w);
q=(arcnode *)malloc(sizeof(arcnode));
q->adjvex=j;
q->weight=w;
q->nextarc=g[i].firstarc;
g[i].firstarc=q;
p=(arcnode *)malloc(sizeof(arcnode));
p->adjvex=i;
p->weight=w;
p->nextarc=g[j].firstarc;
g[j].firstarc=p;
}
print(g,n);
printf("\n");
printf("图的深度优先搜索:");
trave_dfs(g,n);
printf("\n");
printf("图的广度优先搜索:");
trave_bfs(g,n);
printf("\n");
}
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
