5.cpp

基于C语言关于数据结构深度优先遍历图的设计。

#include "stdlib.h"
#include "stdio.h"

#define FLASE 0
#define TRUE 1
#define MAX_VERTEX_NUM 20
#define MAX 20
#define OVERFLOW -2
#define ERROR 0

typedef int Boolean;
typedef char VertexType;
typedef int Status;
typedef char QElemType;

typedef int InfoType;
typedef enum{DG,DN,UDG,UDN}Graphkind;

typedef struct QNode 
{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef struct
{
	QueuePtr front;
    QueuePtr rear;
}LinkQueue;


 
typedef struct ArcNode 
{
	int adjvex;//该弧所指向的顶点的位置
	struct ArcNode *nextarc;//指向下一条弧的指针
	InfoType *info;//该弧相关信息的指针
}ArcNode;

typedef struct VNode
{
	VertexType data;//顶点信息
	ArcNode *firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct
{
	AdjList vertices;
    Status vexnum,arcnum;//图的当前顶点数和弧数
	Graphkind kind;//图的种类标志
}ALGraph;

Status LocateVex(ALGraph G,char c)
{//若G中存在顶点U,则返回该顶点在图中位置:否则返回ERROR
	for(int i=0;i<G.vexnum;i++)
	{
		if(G.vertices[i].data==c)
	    return i;
	}
    return ERROR;
}

Status (*VisitFunc)(ALGraph G,int v);//全局变量
Boolean visited[MAX];

void CreateUDG(ALGraph &G)
{//创造一个无向图UDG,利用邻接表存储
    printf("建造一个无向图\n");
	char v1,v2;
	int head,tail;
	ArcNode *pi,*pi_next;
	printf("请输入顶点个数:");
	scanf("%d",&G.vexnum);
    getchar();
	printf("请输入边的数目:");
	scanf("%d",&G.arcnum);
	getchar();
	for(int i=0;i<G.vexnum;i++)
	{
		printf("输入第%d顶点:",i+1);
		scanf("%c",&G.vertices[i].data);
		getchar();
		G.vertices[i].firstarc=NULL;
	}
    for(int k=0;k<G.arcnum;k++)
	{   
		printf("请输入边的起点:");
		scanf("%c",&v1);
		getchar();
		printf("请输入边的终点:");
		scanf("%c",&v2);
		getchar();
		head=LocateVex(G,v2);
		tail=LocateVex(G,v1);

		if(!(pi=(ArcNode *)malloc(sizeof(ArcNode))))
			exit(OVERFLOW);
		pi->adjvex=head;
		pi->nextarc=NULL;

		if(!(pi_next=(ArcNode *)malloc(sizeof(ArcNode))))
			exit(OVERFLOW);
		pi_next->adjvex=tail;;
		pi_next->nextarc=NULL;
		ArcNode *p_link=G.vertices[tail].firstarc;
		if(!p_link)
			G.vertices[tail].firstarc=pi;
		else
		{
			while(p_link->nextarc)
				p_link=p_link->nextarc;
			p_link->nextarc=pi;
		}
        ArcNode *p_next=G.vertices[head].firstarc;
		if(!p_next)
			G.vertices[head].firstarc=pi_next;
		else
		{
			while(p_next->nextarc)
				p_next=p_next->nextarc;
			p_next->nextarc=pi_next;
		} 
	}
}

Status FirstAdjVex(ALGraph G,int v)
{//返回v的第一个邻接顶点位置,否则返回'空'
    ArcNode *p_link=G.vertices[v].firstarc;
	if(p_link)
	{int t=p_link->adjvex;
    return t;}
	else return -1;
}

Status NextAdjVex(ALGraph G,int v,int w)
{//返回v的相对于w的下一个邻接顶点位置,否则返回'空'
    int t;
	ArcNode *p_link=G.vertices[v].firstarc;
	if(p_link&&p_link->nextarc)
	{
		while(p_link->nextarc)
		{t=p_link->adjvex;
	    if(t==w)
        {int h=p_link->nextarc->adjvex;
        return h;}
		p_link=p_link->nextarc;}
	}
    return -1;
}


void DFS(ALGraph G,int v)
{
	visited[v]=TRUE;VisitFunc(G,v);
	for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
    if(!visited[w]) DFS(G,w);
}		
		
Status Visit(ALGraph G,int v)
{//输出函数 
	printf("%3c",G.vertices[v].data);
    return 1;
}


void DFSTraverse(ALGraph G,Status (* Visit)(ALGraph G,int v))
{//从第v个顶点出发递归地深度优先遍历图G
	VisitFunc=Visit;int v;
    for(v=0;v<G.vexnum;++v) visited[v]=FLASE;
    for(v=0;v<G.vexnum;++v)
	if(!visited[v]) DFS(G,v);
}
	
void Pop(ALGraph G)
{//输出所得邻接链表   
	printf("\n所得邻接链表为:\n");
	for(int i=0;i<G.vexnum;i++)
	{
		printf("%3c",G.vertices[i].data);
	    ArcNode *p_link=G.vertices[i].firstarc;
        while(p_link)
		{
		int t=p_link->adjvex;
        printf("%3c",G.vertices[t].data);	
        p_link=p_link->nextarc;
		}
    printf("\n");
    }
}

void main()
{
	ALGraph G;
	CreateUDG(G);
    Pop(G);
	printf("\n深度优先遍历:");
    DFSTraverse(G,(*Visit));
    printf("\n");
}