数据结构中图的两种存储结构和两种遍历_图的两种存储和遍历
数据结构中图的两种存储结构和两种遍历由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“图的两种存储和遍历”。
邻接矩阵
#include
#include
typedef struct
{
int a[20][20];
int n;
int e;
}Graph;
int visit[20];
void DFS(Graph *p,int n)
{
int i;
printf(“%4d”,n);
visit[n]=1;
for(i=1;in;i++)
if(i!=n&&visit[i]==0&&p->a[n][i])DFS(p,i);
}
void BFS(Graph *p,int n)
{
int i,top=0,t;
int a[20];
printf(“%4d”,n);
visit[n]=1;
a[++top]=n;
while(top)
{
t=a[1];
for(i=1;i
a[i]=a[i+1];
top--;
for(i=1;in;i++)
if(p->a[t][i]&&visit[i]==0){
printf(“%4d”,i);visit[i]=1;
a[++top]=i;
}
}
}
int main()
{
int i,j,n,m;
Graph *p;
p=(Graph *)malloc(sizeof(Graph));
printf(“输入图的顶点数:”);scanf(“%d”,&p->n);
printf(“输入图的边数:”);scanf(“%d”,&p->e);
for(i=1;in;i++)
for(j=1;jn;j++)
p->a[i][j]=0;
printf(“输入图的每条边:n”);
for(i=1;ie;i++)
{
printf(“%d:”,i);
scanf(“%d%d”,&n,&m);
p->a[n][m]=1;
p->a[m][n]=1;
}
for(i=1;in;i++)
{
for(j=1;jn;j++)
printf(“%4d”,p->a[i][j]);
printf(“n”);
}
for(i=1;in;i++)
visit[i]=0;
printf(“DFS遍历:n”);
DFS(p,1);
printf(“n”);
for(i=1;in;i++)
visit[i]=0;
printf(“BFS遍历:n”);
BFS(p,1);
printf(“n”);
return 0;
}
邻接表 #include
#include
typedef struct node
{
int n;
struct node *next;
}Node;
typedef struct
{
int m;
Node *a;
}PP;
PP a[30];
int n,e,visit[30];
void Create()
{
int i,x,y;
Node *p;
printf(“输入图的顶点数和边数:”);scanf(“%d%d”,&n,&e);
for(i=1;i
{
a[i].m=i;
a[i].a=new Node;
a[i].a->next=NULL;}
printf(“输入图的边数:n”);for(i=1;i
{
printf(“%d: ”,i);
scanf(“%d%d”,&x,&y);p=new Node;
p->n=y;
p->next=a[x].a->next;a[x].a->next=p;
p=new Node;
p->n=x;
p->next=a[y].a->next;
a[y].a->next=p;
}
}
void DFS(int n)
{
Node *p;
visit[n]=1;
printf(“%d ”,n);
for(p=a[n].a->next;p;p=p->next)
if(visit[p->n]==0)
DFS(p->n);
}
void BFS(int n)
{
int i;
int aa[20],top=0;
Node *p;
aa[++top]=n;
while(top)
{
p=a[aa[1]].a->next;
for(i=1;i
aa[i]=aa[i+1];
top--;
for(;p;p=p->next)
if(visit[p->n]==0)
{
printf(“%d ”,p->n);
visit[p->n]=1;
aa[++top]=p->n;
}
}
}
int main()
{
int i;
Node *p;
Create();
for(i=1;i
} /* 8 11 1 2 1 8 2 7 2 6 7 4 4 6 4 3 3 6 3 5 8 5 6 8 */
