_DataStructure_C_Impl:求图G中从顶点u到顶点v的一条简单路径

发布时间:2017-7-9 7:14:31编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"_DataStructure_C_Impl:求图G中从顶点u到顶点v的一条简单路径 ",主要涉及到_DataStructure_C_Impl:求图G中从顶点u到顶点v的一条简单路径 方面的内容,对于_DataStructure_C_Impl:求图G中从顶点u到顶点v的一条简单路径 感兴趣的同学可以参考一下。

#pragma once#include<stdio.h>#include<stdlib.h>#define StackSize 100typedef int DataType;	//栈元素类型定义typedef struct{	DataType stack[StackSize];	int top;}SeqStack;//将栈初始化为空栈仅仅须要把栈顶指针top置为void InitStack(SeqStack *S){	S->top=0;//把栈顶指针置为0}//推断栈是否为空。栈为空返回1,否则返回0int StackEmpty(SeqStack S){	if(S.top==0)		return 1;	else		return 0;}//取栈顶元素。将栈顶元素值返回给e。并返回1表示成功;否则返回0表示失败。int GetTop(SeqStack S,DataType *e){	if(S.top<=0){		//在取栈顶元素之前。推断栈是否为空		printf("栈已经空!\n");		return 0;	}else{		*e=S.stack[S.top-1];	//在取栈顶元素		return 1;	}}//将元素e进栈,元素进栈成功返回1,否则返回0int PushStack(SeqStack *S,DataType e){	if(S->top>=StackSize){	//在元素进栈前。推断是否栈已经满		printf("栈已满,不能进栈!

\n"); return 0; }else{ S->stack[S->top]=e; //元素e进栈 S->top++; //改动栈顶指针 return 1; }}//出栈操作。将栈顶元素出栈,并将其赋值给e。

出栈成功返回1。否则返回0int PopStack(SeqStack *S,DataType *e){ if(S->top<=0){ //元素出栈之前。推断栈是否为空 printf("栈已经没有元素。不能出栈!\n"); return 0; }else{ S->top--; //先改动栈顶指针。即出栈 *e=S->stack[S->top]; //将出栈元素赋值给e return 1; }}//求栈的长度。即栈中元素个数,栈顶指针的值就等于栈中元素的个数int StackLength(SeqStack S){ return S.top;}//清空栈的操作void ClearStack(SeqStack *S){ S->top=0;}

#include<stdio.h>#include<stdlib.h>#include<string.h>#include"SeqStack.h"typedef char VertexType[4];typedef char InfoPtr;typedef int VRType;#define MaxSize 50	//最大顶点个数typedef enum{DG,DN,UG,UN}GraphKind;	//图的类型:有向图、有向网、无向图和无向网//边结点的类型定义typedef struct ArcNode{	int adjvex;		//弧指向的顶点的位置	InfoPtr *info;	//弧的权值	struct ArcNode *nextarc;	//指示下一个与该顶点相邻接的顶点}ArcNode;//头结点的类型定义typedef struct VNode{	VertexType data;	//用于存储顶点	ArcNode *firstarc;	//指示第一个与该顶点邻接的顶点}VNode,AdjList[MaxSize];//图的类型定义typedef struct{	AdjList vertex;	 //头结点	int vexnum,arcnum;	//图的顶点数目与弧的数目	GraphKind kind;	//图的类型}AdjGraph;//求图G中从顶点u到顶点v的一条简单路径void BriefPath(AdjGraph G,int u,int v){	int k,i;	SeqStack S;	ArcNode *p;	int visited[MaxSize];	int parent[MaxSize];	//存储已经訪问顶点的前驱顶点	InitStack(&S);	for(k=0;k<G.vexnum;k++)		visited[k]=0;	//訪问标志初始化	PushStack(&S,u);	//開始顶点入栈	visited[u]=1;		//訪问标志置为1	while(!StackEmpty(S)){	//广度优先遍历图,訪问路径用parent存储		PopStack(&S,&k);		p=G.vertex[k].firstarc;		while(p!=NULL){			if(p->adjvex==v){	//假设找到顶点v				parent[p->adjvex]=k;		//顶点v的前驱顶点序号是k				printf("顶点%s到顶点%s的路径是:",G.vertex[u].data,G.vertex[v].data);				i=v;				do{			//从顶点v開始将路径中的顶点依次入栈					PushStack(&S,i);					i=parent[i];				}while(i!=u);				PushStack(&S,u);				while(!StackEmpty(S)){ //从顶点u開始输出u到v中路径的顶点					PopStack(&S,&i);					printf("%s ",G.vertex[i].data);				}				printf("\n");			}else if(visited[p->adjvex]==0){	//假设未找到顶点v且邻接点未訪问过。则继续寻找				visited[p->adjvex]=1;				parent[p->adjvex]=k;				PushStack(&S,p->adjvex);			}			p=p->nextarc;		}	}}//返回图中顶点相应的位置int LocateVertex(AdjGraph G,VertexType v){	int i;	for(i=0;i<G.vexnum;i++)		if(strcmp(G.vertex[i].data,v)==0)			return i;	return -1;}//採用邻接表存储结构,创建无向图Nvoid CreateGraph(AdjGraph *G){	int i,j,k,w;	VertexType v1,v2;					/*定义两个顶点v1和v2*/	ArcNode *p;	printf("请输入图的顶点数,边数(以逗号分隔): ");	scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);	printf("请输入%d个顶点的值:",G->vexnum);	for(i=0;i<G->vexnum;i++)			/*将顶点存储在头结点中*/	{		scanf("%s",G->vertex[i].data);		G->vertex[i].firstarc=NULL;		/*将相关联的顶点置为空*/	}	printf("请输入边的两个顶点(以空格作为分隔):\n");	for(k=0;k<G->arcnum;k++)			/*建立边链表*/	{		scanf("%s%s",v1,v2);		i=LocateVertex(*G,v1);		j=LocateVertex(*G,v2);		/*j为入边i为出边创建邻接表*/		p=(ArcNode*)malloc(sizeof(ArcNode));		p->adjvex=j;		p->info=(InfoPtr*)malloc(sizeof(InfoPtr));		/*将p指向的结点插入到边表中*/		p->nextarc=G->vertex[i].firstarc;		G->vertex[i].firstarc=p;		/*i为入边j为出边创建邻接表*/		p=(ArcNode*)malloc(sizeof(ArcNode));		p->adjvex=i;		p->info=NULL;		p->nextarc=G->vertex[j].firstarc;		G->vertex[j].firstarc=p;	}	(*G).kind=UG;}//销毁无向图Gvoid DestroyGraph(AdjGraph *G){	int i;	ArcNode *p,*q;	for(i=0;i<G->vexnum;++i)		/*释放图中的边表结点*/	{		p=G->vertex[i].firstarc;	/*p指向边表的第一个结点*/		if(p!=NULL)					/*假设边表不为空,则释放边表的结点*/		{			q=p->nextarc;			free(p);			p=q;		}	}	(*G).vexnum=0;					/*将顶点数置为0*/	(*G).arcnum=0;					/*将边的数目置为0*/}//图G的邻接表的输出void DisplayGraph(AdjGraph G){	int i;	ArcNode *p;	printf("该图中有%d个顶点:",G.vexnum);	for(i=0;i<G.vexnum;i++)		printf("%s ",G.vertex[i].data);	printf("\n图中共同拥有%d条边:\n",2*G.arcnum);	for(i=0;i<G.vexnum;i++)	{		p=G.vertex[i].firstarc;		while(p)		{			printf("(%s,%s) ",G.vertex[i].data,G.vertex[p->adjvex].data);			p=p->nextarc;		}		printf("\n");	}}void main(){	AdjGraph G;	CreateGraph(&G);		/*採用邻接表存储结构创建图G*/	DisplayGraph(G);		/*输出无向图G*/	BriefPath(G,0,4);		/*求图G中从顶点a到顶点e的简单路径*/	DestroyGraph(&G);		/*销毁图G*/	system("pause");}



上一篇:Alpine Linux配置使用技巧【一个只有5M的操作系统(转)】
下一篇:Linux内核线程之深入浅出【转】 - 张昺华

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款