图.cpp

数据结构中的重要结构

#include<stdio.h>
#include<malloc.h>
#define MAX_VERTEX_NUM 20

int visited[MAX_VERTEX_NUM];
int queue[MAX_VERTEX_NUM];

typedef struct ArcNode{
	int adjvex;
	struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode{
	int num;
	ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct ALGraph{
	AdjList vertices;
	int vexnum,arcnum;
}ALGraph;

void dfs(ALGraph &G,int v){//深度优先遍历
	ArcNode *p;
	visited[v]=1;
	printf("%4d",G.vertices[v].num);
	p=G.vertices[v].firstarc;
	while(p!=NULL){
		if(visited[p->adjvex]==0) dfs(G,p->adjvex);//递归
		p=p->nextarc;
	}
}

void bfs(ALGraph &G,int vi){//从第vi个开始广度优先遍历
	int v,i,front,rear;
	ArcNode *p;
	front=0;rear=1;
	for(i=1;i<=MAX_VERTEX_NUM;i++) visited[i]=0;
	visited[vi]=1;
	printf("%4d",G.vertices[vi].num);
	queue[rear]=vi; //queue相当于队列queue
	while(front!=rear){//顶点没有全部遍历
		front=front+1;
		v=queue[front];
		p=G.vertices[v].firstarc;
		while(p!=NULL){
			if(visited[p->adjvex]==0){
				visited[p->adjvex]=1;
				printf("%4d",p->adjvex);
				rear=rear+1;
				queue[rear]=p->adjvex;
			}
			p=p->nextarc;
		}
	}
}

void main(){
	ALGraph G;
	int n,i,j,s,d,c;
	ArcNode *p,*q;
	printf("                         图的遍历\n");
	printf("-----------------------------------------------------------\n");
	for(i=1;i<=MAX_VERTEX_NUM;i++)  visited[i]=0;
	printf("请输入图的顶点个数：");
	scanf("%d",&G.vexnum);
	printf("请输入图的顶点边数：");
	scanf("%d",&G.arcnum);
//	printf("\n");
	for(i=1;i<=G.vexnum;i++){
		G.vertices[i].num=i;
		G.vertices[i].firstarc=NULL;
	}
	for(j=1;j<=G.arcnum;j++){
		printf("第%d条边=〉端点序号:",j);
		scanf("%d",&s);
		printf("第%d条边=〉邻接点序号:",j);
		scanf("%d",&d);
		p=(ArcNode*)malloc(sizeof(ArcNode));
		q=(ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex=d;q->adjvex=s;
		p->nextarc =G.vertices[s].firstarc;
		G.vertices[s].firstarc=p;
		q->nextarc=G.vertices[d].firstarc;
		G.vertices[d].firstarc=q;
	}
	printf("构成的邻接表为如下形式");
	for(i=1;i<=G.vexnum;i++){
		printf("\n%8d",G.vertices[i].num);
		p=G.vertices[i].firstarc;
		while(p){
			printf("%4d",p->adjvex);
			p=p->nextarc;
		}
	}
	n=1;
	while(n){
		printf(" \n                        图的遍历\n");
		printf("--------------------------------------------------------------\n");
		printf("深度优先搜索(1)      广度优先搜索(2)      运行结束(3)\n");
		scanf("%d",&c);
		switch(c){
		case 1:printf("深度优先搜索序列:");dfs(G,1);break;
		case 2:printf("广度优先搜索序列:");bfs(G,1);break;
		case 3:n=0;break;
		default:n=0;
		}
	}
}