allpath.cpp

文件夹中包括常用的数据结构的算法

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



//邻接表结点：
typedef   struct  Jnode
{    int  vex;   //顶点域
     struct  Jnode  *Nextarc;   //链域
}Jnode;

//表头结点：
typedef  struct  tnode
{
	int data;
	//int  in;  //入度域
    Jnode  *firstarc;    //链域
}tnode;

typedef  struct ALGrahp
{
	//int data;
    tnode vertices[MAX_VERTEX_NUM];   //图的表头结点
	int vexnum;                       //图的顶点数
}ALGrahp;

int Stack[MAX_VERTEX_NUM];  //建栈，存放顶点序号
int sTop=0;                 //从栈底到栈顶为当前路径

///////////////////////////////////////////////////////////////////////////////////////////////////////
void AllPath(ALGrahp &G, int v1, int v2)  
{

    Stack[sTop++] = v1;  //将v1节点入栈

	Jnode *p = G.vertices[v1-1].firstarc;  //指针指向V1的第一个节点
  
	while(p)
	{
		if( p->vex != v2)      //如果当前点不是目的节点，压入栈中
		{
			AllPath(G, p->vex, v2);    //继续深度遍历当前节点 
		}
		else
		{  //如果当前点是目的节点，打印栈中所有顶点
			for(int i=0; i < sTop; i++)
			{
			    printf("%d,\t", Stack[i]);
			}
			printf("%d,\n", v2);
		}
		p = p->Nextarc;
	}
    sTop--;   //当前节点执行完后，说明从经过所有前驱，又经过当前节点的路径已经遍历，退栈
};


void main()
{
///////////////////////////////////////////////////////////////////////////////////////////////////////
	///生成图
    ALGrahp G;
	printf("输入顶点数\n");  //读入顶点数
	scanf("%d", &G.vexnum) ;
	for(int i=0; i < G.vexnum; i++ )
	{
	    int nextNum=0;
		G.vertices[i].data = i+1;    //顶点号为脚标 +1
//		printf("输入顶点%d的入度\n", i+1);
//		scanf("%d", &G.vertices[i].in );
		printf("输入顶点%d的下一个邻接顶点号，如结束输入负数\n", i+1);
		scanf("%d", &nextNum);
		if(nextNum >= 0)
		{
			Jnode *p;
			
		    G.vertices[i].firstarc = p = (Jnode *)malloc(sizeof(Jnode));
            p->vex = nextNum;
			p->Nextarc = NULL;
			printf("输入顶点%d的下一个邻接顶点号，如结束输入负数\n", i+1);
	     	scanf("%d", &nextNum);
			while(nextNum >= 0)
			{
			    p->Nextarc = (Jnode *)malloc(sizeof(Jnode));
                p = p->Nextarc;
				p->vex = nextNum;
                printf("输入顶点%d的下一个邻接顶点号，如结束输入负数\n", i+1);
	     	    scanf("%d", &nextNum);
			}
            p->Nextarc = NULL;
		}//nextNum > =0
		else
		{
		    G.vertices[i].firstarc = NULL;
		}

	};
///////////////////////////////////////////////////////////////////////////////////////////////////////
	int source = 0, dest = 0;

	printf("输入起始顶点\n");
    scanf("%d", &source);

    printf("输入目的顶点\n");
	scanf("%d", &dest);

	AllPath(G, source, dest);
	printf("\n");

}