- #include<stdio.h>
- #include<string.h>
- #include "stdlib.h"
- #define PATH_LENGTH 100//路径
- #define MAX_VERTEX_NUM 20//顶点个数
- #define MAX_NAME 5 /* 顶点字符串的最大长度+1 */
- typedef char VertexType[MAX_NAME];
- #define OK 1
- #define ERROR 0
- #define TRUE 1
- #define FALSE 0
- typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
- typedef struct ArcNode
- {
- int posvex;//顶点位置
- VertexType adjvex;//该弧所指向的顶点
- struct ArcNode *nextarc;//指向下一条弧的指针
- }ArcNode;
- typedef struct VNode
- {
- VertexType data;//顶点信息
- ArcNode *firstarc;//指向第一条依附该顶点的弧的指针
- }VNode,AdjList[MAX_VERTEX_NUM];
- typedef struct
- {
- AdjList vertices;
- int vexnum,arcnum;// 图的当前顶点数和弧数
- }MGraph;
- int LocateVex(MGraph G,VertexType u)
- { /* 初始条件:图G存在,u和G中顶点有相同特征 */
- /* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
- int i;
- for(i=0;i<G.vexnum;++i)
- if(strcmp(u,G.vertices [i].data )==0)
- return i;
- return -1;
- }
- void CreateUDL(MGraph *G)//创建邻接表
- {
- int i,k;
- VertexType va,vb;
- printf("请输入无向网G的顶点数,弧数: ");
- scanf("%d%*c%d",&(*G).vexnum,&(*G).arcnum);
- printf("请输入%d个顶点的值(<%d个字符):\\n",(*G).vexnum,MAX_NAME);
- for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
- {
- scanf("%s",(*G).vertices [i].data);
- (*G).vertices [i].firstarc =NULL;
- }
- printf("请输入%d条弧的弧尾、弧头: \\n",(*G).arcnum);
- for(k=0;k<(*G).arcnum;++k)
- {
- scanf("%s%s%*c",va,vb); /* %*c吃掉回车符 */
- for(int count=0;count<(*G).vexnum ;count++)
- {
- if(strcmp(va,(*G).vertices [count].data )==0)
- {
- ArcNode *tpArcNode =new ArcNode;
- strcpy(tpArcNode->adjvex ,vb);
- tpArcNode->posvex =LocateVex((*G),vb);
- tpArcNode->nextarc =NULL;
- if(!(*G).vertices [count].firstarc )
- {
- (*G).vertices [count].firstarc =tpArcNode;
- }
- else
- {
- ArcNode *tp=(*G).vertices [count].firstarc;
- while(tp->nextarc )
- {
- tp=tp->nextarc ;
- }
- tp->nextarc =tpArcNode;
- }
- }
- if(strcmp(vb,(*G).vertices [count].data )==0)
- {
- ArcNode *tpArcNode =new ArcNode;
- strcpy(tpArcNode->adjvex ,va);
- tpArcNode->posvex =LocateVex((*G),va);
- tpArcNode->nextarc =NULL;
- if(!(*G).vertices [count].firstarc )
- {
- (*G).vertices [count].firstarc =tpArcNode;
- }
- else
- {
- ArcNode *tp=(*G).vertices [count].firstarc;
- while(tp->nextarc )
- {
- tp=tp->nextarc ;
- }
- tp->nextarc =tpArcNode;
- }
- }
- }
- }
- printf("邻接表为:\\n");
- for(i=0;i<(*G).vexnum ;i++)
- {
- printf("%4s",(*G).vertices [i].data );
- ArcNode *tp=(*G).vertices [i].firstarc;
- while(tp)
- {
- printf("%4s",tp->adjvex );
- tp=tp->nextarc ;
- }
- printf("\\n");
- }
- }
- Status PathLength(MGraph &G,int pos_v1,int pos_v2,int v_PL,char path[],int visited[MAX_VERTEX_NUM])//求长度为v_PL的路径
- {
- int v_temp_pos;
- visited[pos_v1]=TRUE;//将顶点标记为已经历
- ArcNode *tp=G.vertices [pos_v1].firstarc ;
- while(tp)
- {
- v_temp_pos=tp->posvex ;
- if(!visited[v_temp_pos])
- {
- if(v_PL==1&&v_temp_pos==pos_v2)
- {
- return OK;
- }
- if(!v_PL&&v_temp_pos==pos_v2)
- {
- return OK;
- }
- if(PathLength(G,v_temp_pos,pos_v2,v_PL-1,path,visited))
- {
- strcat(path,"--\\0");
- strcat(path,G.vertices [v_temp_pos].data );//记录路径
- return OK;
- }
- tp=tp->nextarc ;
- }
- else
- {
- tp=tp->nextarc ;
- }
- }
- visited[pos_v1]=FALSE;
- return ERROR;
- }
- void main()
- {
- MGraph g;
- VertexType m_va,m_vb;
- char path[PATH_LENGTH]={'\\0'};//存放路径
- int m_PL=0;
- int pos_v1,pos_v2;
- int visited[MAX_VERTEX_NUM]={0};//用于记录顶点是否被访问过
- CreateUDL(&g);
- printf("输入两个顶点与所求路径长度:\\n");
- scanf("%s%s%d%*c",m_va,m_vb,&m_PL);
- pos_v1=LocateVex(g,m_va);//获得顶点所在位置
- pos_v2=LocateVex(g,m_vb);
- strcat(path,m_vb);
- if(PathLength(g,pos_v1,pos_v2,m_PL,path,visited))
- {
- printf("%s,%s之间存在长度为%d的简单路径:\\n",m_va,m_vb,m_PL);
- strcat(path,"--\\0");
- strcat(path,m_va);
- printf("%s\\n",path);
- }
- else
- {
- printf("%s,%s之间不存在长度为%d的简单路径!\\n",m_va,m_vb,m_PL);
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/140720149965.html
来源: http://www.codesnippet.cn/detail/140720149965.html