程序.cpp

题 目: 判别图中两个顶点之间的简单路径的程序设计 初始条件： （1） 采用邻接表作为存储结构。 （2） 编写程序判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径。 （3）

// czh.cpp : 定义控制台应用程序的入口点。
#include <stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
int n=0,e=0;
#define MAX_VERTEX_NUM 12
#define TRUE 1
#define FALSE 0
typedef char  vextype;
typedef int  adjtype;
//弧结点（表结点）
typedef  struct edgenode
	{
	int  adjvex;
	struct edgenode  *next;
	} edgenode;
//顶点（头节点）
typedef struct vexnode
	{
	vextype  vertex;
	edgenode *link;
	}vexnode,ga[MAX_VERTEX_NUM];
//整个图的信息
typedef struct ALGraph{
	struct vexnode *vertexNum ; 
	
    int link;
}ALGraph;
//辅助数组，记录每个顶点是否被访问过
int      visited[MAX_VERTEX_NUM];
int exist_path_len(ALGraph &G, vexnode *gc,int i,int j,int k)//判断邻接表方式存储的无向图G的顶点i到j是否存在长度为k的简单路径  
{  G.vertexNum=gc;
	int l;
	edgenode  *s;
  if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 
  else if(k>0) 
  { 
    visited[i]=1; 
    for(s=G.vertexNum[i].link;s;s=s->next) 
    { 
      l=s->adjvex; 
      if(!visited[l]) 
        if(exist_path_len(G,gc,l,j,k-1)) return 1; //剩余路径长度减一 
    }//for 
    visited[i]=0; 
  }//else 
  return 0; //没找到 
  
}//exist_path_len
/*----------------------创建图---------------------------*/
void creatgraph( vexnode *ga){

	int i,j,k;
	edgenode  *s;
	printf("   输入顶点信息（以编号的顺序，每个顶点占两位）\n\t ");
	for(i=1; i<=n; i++)
	{
	/*	printf("	第%d个顶点是:",i);  */
		scanf("%2c",&ga[i].vertex);
		ga[i].link=NULL;
	}
	printf("	输入组成边的点\n");
	printf("	如: 边(2,3); 则输入2 3\n");
	for(k=1; k<=e; k++)
	{
		printf("	第%d条边的点对:",k);
		scanf("%d%d",&i,&j);
		s=(edgenode *)malloc(sizeof(edgenode));//新建结点存储边，为之分配存储空间
		s->adjvex=j;
		s->next=ga[i].link;
		ga[i].link=s;
		s=(edgenode *)malloc(sizeof(edgenode));//新建结点存储边，为之分配存储空间
		s->adjvex=i;
		s->next=ga[j].link;
		ga[j].link=s;
	}

}
/*------------------主函数-----------------*/
void main()
{
	cout<<"程序编写者  软件0501  陈宗浩"<<endl;
	cout<<"n的数值e的数值"<<endl;
    cin>>n>>e;
vexnode gb[MAX_VERTEX_NUM];
ALGraph Ga;
creatgraph(gb);                               //创建图
cout<<"第i个顶点"<<"第j个顶点"<<"k的值"<<endl;
int i,j,k,m;
cin>>i>>j>>k;
m=exist_path_len(Ga,gb,i,j,k);               //寻找简单路径
if(m)cout<<"找到(存在)简单路径"<<endl;
else  cout<<"不存在简单路径"<<endl;
int a;
cout<<"是否继续? 按1继续 OR 2退出"<<endl;
cin>>a;
if(a==1) main();
}