algraph.cpp

GraphPath 采用邻接矩阵存储图

//ALGraph.cpp
//uuhorse
//2008.05.31
#include "ALGraph.h"
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

int CreatGraph (ALGraph &G)//邻接表存储结构
{
	/*printf ("1、构造图； 2、构造网 \n");
	scanf ("%d", &G.kind);*/
	G.kind =1;
	printf ("请输入图中顶点总数：\n");
	scanf ("%d", &G.vexnum);

	printf ("请输入图中弧的总数：\n");
	scanf ("%d", &G.arcnum);

	G.vertices =(VNode *) malloc ( sizeof(VNode) * G.vexnum );	//分配空间，存储每个顶点


	printf ("请输入各顶点的数据域：\n");
	for (int i=0; i<G.vexnum; i++)		//初始化，将所有顶点依附的弧的指针置空
	{
		while ((G.vertices[i].data =getchar())==' ' || G.vertices[i].data =='\n' )
			;
		G.vertices[i].firstarc = NULL;
	}


	if ( G.kind==1)
	{
		CreatG(G); //邻接表构造图G
	}
/*	else
	{
		CreatN(G); //邻接表构造网G
	}
*/
	return true;
}


int CreatG(ALGraph &G) //邻接表构造图G
{
	for (int i=0; i<G.vexnum; i++)
	{
		ArcNode* newArc=G.vertices[i].firstarc;	//创建的新弧,插入弧域  
		int loc;			//新弧的顶点位置
		/*VertexType*/ char tnode;	//新弧的顶点信息

		

		printf ("请输入与顶点 %c 相邻的顶点(输入'#'结束)：\n", G.vertices[i].data);
		
		while (true)
		{
			while ( (tnode = getchar())==' ' || tnode=='\n')
				;
			if (tnode =='#')
				break;

			newArc = (ArcNode *) malloc ( sizeof(ArcNode)*1 );
			loc = LocateVex (G, tnode);
			if (loc>=G.vexnum)
			{
				printf ("输入节点有误!\n");
				return false;
			}
			newArc->adjvex = loc;
			newArc->info = NULL;

			ArcNode* tmp = G.vertices[i].firstarc;	//不要出错
			G.vertices[i].firstarc = newArc;
			newArc->nextarc = tmp;			
		}
		
	}
	return true;
}

int LocateVex (ALGraph G, VertexType v)	//返回v在G中的位置
{
	for (int i=0; i<G.vexnum && G.vertices[i].data!=v; i++)
		;
	return i;
}

int SearchPath(ALGraph &G, VertexType i ,VertexType s)
//在图G中求一条从顶点i到顶点s 的简单路径。
{
	int fr = LocateVex (G,i);
	int to = LocateVex (G,s);

	int stk[MAX_VERTEX_NUM];
	top=0;
	int flag[MAX_VERTEX_NUM]=0;	//标记可达；
	int ext[MAX_VERTEX_NUM]={0};//标记访问过

	stk[top] = fr;
	flag[fr] = 1;
	ext[fr]=1;
	top++;

	ArcNode* nowarc = G.vertices[fr].firstarc;
	while (fr!=to)
	{
		ArcNode* tarc=nowarc;		
		stk[top]=nowarc->adjvex;
		top++;

		while (tarc!=NULL && fr!=to)
		{
			fr = tarc->adjvex;
			flag[fr]=1;
			tarc = tarc->nextarc;
		}
		if (tarc!=NULL)
		{
			nowarc =nowarc->nextarc;
			top--;
		}
		if (nowarc=NULL)
		{
			if(ext[nowarc->nextarc->adjvex]!=1)
				nowarc=G.vertices[stk[top]].firstarc;
			else

		}

		if (fr==to)
		{
			stk[top]=fr;
			top++;
		}
	}
}