数据结构实验：无向图的邻接表操作

Luz5年前 (2019-12-02)实验4200

实验题目：无向图的邻接表操作
需求分析：
本演示程序在TC2.0环境下编写调试，完成图的邻接表存储，并基于图的邻接表存储结构上的图的深度优先遍历和广度优先遍历。
首先要根据键盘输入的数据建立图的邻接表存储，并在此基础上实现图的深度优先遍历和广度优先遍历。程序所能达到的功能。完成无向图的邻接表创建、深度优先遍历、广度优先遍历。

输入顶点数量，边数量 5,5
分别输入每条边的关联顶点编号 1,2 2,3 3,4 4,5 5,1
输入深度优先遍历的出发点为3
得到深度优先遍历的次序为3->4->5->1->2
输入广度优先遍历的出发点为2
得到广度优先遍历的次序为2->3->4->5->1
测试数据。

概要设计

主函数main()
建立无向图的邻接表 creat_L()
输出邻接表 output_L()
深度优先遍历 dfsL()
广度优先遍历 bfsL()
为了实现上述程序功能，需要定义循环顺序队列的数据结构。
本程序包含5个函数

详细设计
#include<stdio.h>
#include<stdlib.h>
#define MAX 20
typedef int VexType;
typedef struct Vnode
{
VexType data;
struct Vnode *next;
}Vnode;
typedef Vnode Lgraph[MAX];
typedef struct
{
int V[MAX];
int front;
int rear;
}Queue;
void creat_L(Lgraph G);
void output_L(Lgraph G);
void dfsL(Lgraph G,int v);
Lgraph Ga;
int n,e,visited[MAX];
int main()
{
int v1,i;
for(i=0;i<MAX;i++)
visited[i]=0;
creat_L(Ga);
output_L(Ga);
printf("\n 请输入深度优先遍历的出发点:");
scanf("%d",&v1);
printf("\n 深度优先遍历的结果为:");
dfsL(Ga,v1);
for(i=0;i<MAX;i++)
visited[i]=0;
printf("\n 请输入广度优先遍历的出发点:");
scanf("%d",&v1);
printf("\n 广度优先遍历的结果为:");
dfsL(Ga,v1);
}
void creat_L(Lgraph G)
{
Vnode *p,*q;
int i,j,k;
printf("\n 请输入图的顶点数和边数:");
scanf("%d,%d",&n,&e);
for(i=1;i<=n;i++)
{
G[i].data=i;
G[i].next=NULL;
}
for(k=1;k<=e;k++)
{
printf(" 请输入每条边的关联顶点编号:");
scanf("%d,%d",&i,&j);
p=(Vnode *)malloc(sizeof(Vnode));
p->data=i;
p->next=G[j].next;
G[j].next=p;
q=(Vnode *)malloc(sizeof(Vnode));
q->data=j;
q->next=G[i].next;
G[i].next=q;
}
}
void output_L(Lgraph G)
{
int i;
Vnode *p;
for(i=1;i<=n;i++)
{
printf("\n 与[%d] 关联的顶点有:",i);
p=G[i].next;
while(p!=NULL)
{
printf("%5d",p->data);
p=p->next;
}
}
}
void initqueue(Queue *q)
{
q->front=-1;
q->rear=-1;
}
int quempty(Queue *q)
{
if(q->front==q->rear)
{
return 1;
}
else
{
return 0;
}
}
void enqueue(Queue *q,int e)
{
if((q->rear+1)%MAX==q->front)
printf(" 队列满!\n");
else
{
q->rear=(q->rear+1)%MAX;
q->V[q->rear]=e;
}
}
int dequeue(Queue *q)
{
int t;
if(q->front==q->rear)
{
printf(" 队列空!\n");
return 0;
}
else
{
q->front=(q->front+1)%MAX;
t=q->V[q->front];
return t;
}
}
void dfsL(Lgraph G,int v)
{
Vnode *p;
printf("%d->",G[v].data);
visited[v]=1;
p=G[v].next;
while(p)
{
v=p->data;
if(visited[v]==0)
dfsL(G,v);
p=p->next;
}
}
void bfsL(Lgraph g,int v)
{
int x;
Vnode *p;
Queue *q=(Queue *)malloc(sizeof(Queue));
initqueue(q);
printf("\n %d->",g[v].data);
visited[v]=1;
enqueue(q,v);
while(!quempty(q))
{
x=dequeue(q);
p=g[x].next;
while(p)
{
v=p->data;
if(visited[v]==0)
{
printf("%d->",g[v].data);
visited[v]=1;
enqueue(q,v);
}
p=p->next;
}
}
printf("\n");
}
调试分析