无向图.c

数据结构无向图的算法

#include<stdio.h>
#include<stdlib.h>
#define MAX 20
#define NULL 0
struct ArcNode
{int adjvex;
	struct ArcNode *nextarc;
};
struct Vnode
{int data;
    struct ArcNode *firstarc;
};
struct Vnode AdjList[MAX];
int m,n,v,cord;
main()
{void CreatGraph(struct Vnode A[MAX]);
	void DFS(struct Vnode A[MAX]);
	void BFS(struct Vonde A[MAX]);
	do
	{printf("\n   主菜单");
		printf("\n  1 建立无向图的邻接链表");
		printf("\n  2 按深度遍历图");
		printf("\n  3 按广度遍历图");
		printf("\n  4 结束程序运行");
		printf("\n------------------");
		printf("\n  请输入您的选择 1，2，3，4");
		scanf("%d",&cord);
		switch(cord)
		{case 1:CreatGraph(AdjList);break;
			case 2:DFS(AdjList);break;
			case 3:BFS(AdjList);break;
			case 4:exit(0);
		}
	}while(cord<=4);
}/*main*/
void CreatGraph(struct Vnode A[MAX])
{int i,j,k;
	struct ArcNode *p;
	printf("input arces and vexes");
	scanf("%d,%d",&m,&n);
	for(k=0;k<n;k++)
	{A[k].data=k+1;
		A[k].firstarc=NULL;
	}
	for(k=0;k<n;k++)
	{printf("\ninput arc");
		scanf("%d,%d",&i,&j);
		p=(struct ArcNode*)malloc(sizeof(struct ArcNode));
		p->adjvex=j;
		p->nextarc=A[i-1].firstarc;
		A[i-1].firstarc=p;
		p=(struct ArcNode*)malloc(sizeof(struct ArcNode));
		p->adjvex=i;
		p->nextarc=A[j-1].firstarc;
		A[j-1].firstarc=p;
	}
	printf("\n");
	for(k=0;k<n;k++)
	{printf("%d",A[k].data);
		p=a[k].firstarc;
		while(p)
		{printf("%d",p->adjvex);
			p=p->nextarc;
		}
		printf("\n");
	}
}/*CreatGraph*/
void DFS(struct VNode A[MAX])
{struct ArcNode *p,*ar[MAX];
	int x,i,y,top=-1;
	int visited[MAX];
	for(i=0;i<n;i++) visited[i]=0;
	printf("\ninput x");
	scanf("%d",x);
	visited[x-1]=1;
	p=A[x-1].firstarc;
	while((p)||(top>=0));
	{if(!p){p=ar[top];top--;}
	 y=p->adjvex;
	 if(visited[y-1]==0)
	 {visited[y-1]=1;
	 	printf("->%d",y)
	 	p=p->nextarc;
	 	if(p){top++;ar[top]=p;}
	 	p=A[y-1].fistarc;
	 }
	 else p=p->nextarc;
	}
}/*DFS*/
viod BFS(struct Vnode A[MAX])
{struct ArcNode *p;
	int x,i,y,front=-1,rear=-1,ar[MAX],visited[MAX];
	for(i=0;i<n;i++)visited[i]=0;
	printf("\ninput x");
	scanf("%d",&x);
	printf("%d",x);
	visited[x-1]=1;
	p=A[x-1].firstarc;
	while((p)||(front!=rear))
	{if(!p){front++;
		y=ar[front];
		p=A[y-1].firstarc;
		}
		y=p->adjvex;
		if(visited[y-1]==0)
		{if(!p){front++;
			y=ar[front];
			p=A[y-1].firstarc;
			}
			y=p->adjvex;
			if(visited[y-1]==0)
			{visited[y-1]=1;
				printf("->%d",y);
				rear++;
				ar[rear]=y;
			}
			p=p->nextarc;
		}
		}/*BFS*/