mgraph.cpp

GraphPath 采用邻接矩阵存储图

//MGraph.cpp
//uuhorse
//2008.05.31

#include "MGraph.h"
#include <stdio.h>
#include <malloc.h>

int CreatGraph (MGraph &G)//采用数组（邻接矩阵）表示法，构造图G
{
	printf("请输入图的类型:\n");
	printf("0、有向图，1、有向网，2、无向图，3、无向网!\n");
	scanf("%d",&G.kind);
	switch (G.kind)
	{
	case DG:
		return CreatDG(G);
	case DN:
		return CreatDN(G);
	case UDG:
		return CreatUDG(G);
	case UDN:
		return CreatUDN(G);
	}
	return true;
}

int CreatDG(MGraph &G) //构造有向图G
{
		//int IncInfo = 0;	//每个节点存储的信息量；
	printf ("请输入图中的节点数、弧数和存储的信息数：\n");
	scanf ("%d%d",&G.vexnum, &G.arcnum/*, &IncInfo*/);

	printf ("请输入各顶点向量: \n");
	for (int i=0; i<G.vexnum; i++)
	{
		scanf ("%c", &G.vexs[i]);
		if (G.vexs[i]=='\n' || G.vexs[i]==' ')	//除去回车和空格
			i--;
	}

	for (i=0; i<G.vexnum; i++)		//初始化邻接矩阵
		for (int j=0; j<G.vexnum; j++)
		{
			G.arcs[i][j].adj = 0;
			G.arcs[i][j].info = NULL;
		}

	printf ("请每次输入一条边的两个顶点\n");
	VertexType v1,v2;

	for (int j,k=0; k<G.arcnum; k++)
	{
		//scanf ("%c%c", &v1, &v2);	//输入一条边的两个端点
		v1 = getchar();
		while (v1=='\n' || v1==' ')
		{
			v1 = getchar();
		}
		v2 = getchar();
		while (v2=='\n' || v2==' ')
		{
			v2 = getchar();
		}

		i = LocateVex (G, v1);	j = LocateVex (G, v2);	//确定v1、v2在图G中的位置
		G.arcs[i][j].adj = 1;	//弧<v1,v2>的权值
		/*if (IncInfo >0)
		{
			printf ("请输入弧<%c,%c>含有的相关信息：\n");
			G.arcs[i][j].info = (InfoType *)malloc (sizeof (InfoType) * IncInfo );
			//Input(G.arcs[i][j].info);
		}*/
	}

	return true;
}

int CreatDN(MGraph &G) //构造有向网G
{
	//int IncInfo = 0;	//每个节点存储的信息量；
	printf ("请输入图中的节点数、弧数和存储的信息数：\n");
	scanf ("%d%d",&G.vexnum, &G.arcnum/*, &IncInfo*/);

	printf ("请输入各顶点向量: \n");
	for (int i=0; i<G.vexnum; i++)
	{
		scanf ("%c", &G.vexs[i]);
		if (G.vexs[i]=='\n' || G.vexs[i]==' ')	//除去回车和空格
			i--;
	}

	for (i=0; i<G.vexnum; i++)		//初始化邻接矩阵
		for (int j=0; j<G.vexnum; j++)
		{
			G.arcs[i][j].adj = INFINITY;
			G.arcs[i][j].info = NULL;
		}

	printf ("请每次输入一条边及其依附的顶点及其权值\n");
	VertexType v1,v2;
	int w;
	for (int j,k=0; k<G.arcnum; k++)
	{
		//scanf ("%c%c%d", &v1, &v2, &w);	//输入一条边及其依附的顶点及其权值
		v1=getchar();
		while (v1=='\n' || v1==' ')
		{
			v1 = getchar();
		}
		v2=getchar();
		while (v2=='\n' || v2==' ')
		{
			v2 = getchar();
		}
		scanf ("%d",&w);	//输入一条边及其依附的顶点及其权值

		i = LocateVex (G, v1);	j = LocateVex (G, v2);	//确定v1、v2在图G中的位置
		G.arcs[i][j].adj = w;	//弧<v1,v2>的权值
		/*if (IncInfo >0)
		{
			printf ("请输入弧<%c,%c>含有的相关信息：\n");
			G.arcs[i][j].info = (InfoType *)malloc (sizeof (InfoType) * IncInfo );
			//Input(G.arcs[i][j].info);
		}*/
	}

	return true;
}

int CreatUDG(MGraph &G) //构造无向图G
{
	//int IncInfo = 0;	//每个节点存储的信息量；
	printf ("请输入图中的节点数、弧数和存储的信息数：\n");
	scanf ("%d%d",&G.vexnum, &G.arcnum/*, &IncInfo*/);

	printf ("请输入各顶点向量: \n");
	for (int i=0; i<G.vexnum; i++)
	{
		scanf ("%c", &G.vexs[i]);
		if (G.vexs[i]=='\n' || G.vexs[i]==' ')	//除去回车和空格
			i--;
	}

	for (i=0; i<G.vexnum; i++)		//初始化邻接矩阵
		for (int j=0; j<G.vexnum; j++)
		{
			G.arcs[i][j].adj = 0;
			G.arcs[i][j].info = NULL;
		}

	printf ("请每次输入一条边的两个顶点\n");
	VertexType v1,v2;
	for (int j,k=0; k<G.arcnum; k++)
	{
		//scanf ("%c%c", &v1, &v2);	//输入一条边的两个顶点
		v1 = getchar();
		while (v1=='\n' || v1==' ')
		{
			v1 = getchar();
		}
		v2 = getchar();
		while (v2=='\n' || v2==' ')
		{
			v2 = getchar();
		}

		i = LocateVex (G, v1);	j = LocateVex (G, v2);	//确定v1、v2在图G中的位置
		G.arcs[i][j].adj = G.arcs[j][i].adj = 1;	//弧<v1,v2>的权值
		/*if (IncInfo >0)
		{
			printf ("请输入弧<%c,%c>含有的相关信息：\n");
			G.arcs[i][j].info = (InfoType *)malloc (sizeof (InfoType) * IncInfo );
			//Input(G.arcs[i][j].info);
		}*/
	}

	return true;
}

int CreatUDN(MGraph &G) //构造无向网G
{
	int IncInfo = 0;	//每个节点存储的信息量；
	printf ("请输入图中的节点数、弧数和存储的信息数：\n");
	scanf ("%d%d",&G.vexnum, &G.arcnum/*, &IncInfo*/);

	printf ("请输入各顶点向量: \n");
	for (int i=0; i<G.vexnum; i++)
	{
		scanf ("%c", &G.vexs[i]);
		if (G.vexs[i]=='\n' || G.vexs[i]==' ')	//除去回车和空格
			i--;
	}

	for (i=0; i<G.vexnum; i++)		//初始化邻接矩阵
		for (int j=0; j<G.vexnum; j++)
		{
			G.arcs[i][j].adj = INFINITY;
			G.arcs[i][j].info = NULL;
		}

	printf ("请每次输入一条边及其依附的顶点及其权值\n");
	VertexType v1,v2;
	int w;
	for (int j,k=0; k<G.arcnum; k++)
	{
		//scanf ("%c%c%d", &v1, &v2, &w);	//输入一条边及其依附的顶点及其权值
		v1=getchar();
		while (v1=='\n' || v1==' ')
		{
			v1 = getchar();
		}
		v2=getchar();
		while (v2=='\n' || v2==' ')
		{
			v2 = getchar();
		}
		scanf ("%d",&w);	//输入一条边及其依附的顶点及其权值

		i = LocateVex (G, v1);	j = LocateVex (G, v2);	//确定v1、v2在图G中的位置
		G.arcs[i][j].adj = G.arcs[j][i].adj = w;	//弧<v1,v2>的权值
		/*if (IncInfo >0)
		{
			printf ("请输入弧<%c,%c>含有的相关信息：\n");
			G.arcs[i][j].info = (InfoType *)malloc (sizeof (InfoType) * IncInfo );
			//Input(G.arcs[i][j].info);
		}*/
	}

	return true;
}



int SearchPath(MGraph &G, VertexType i ,VertexType s)
//在图G中求一条从顶点i到顶点s 的简单路径。
{
	int stkPath[MAX_VERTEX_NUM];	//队列存储可达节点序号
	int flag[MAX_VERTEX_NUM]={0};	//标记已经访问的节点
	int j = LocateVex (G, i);	//i在图中的序列
	int k = LocateVex (G, s);	//s在图中的序列
	int ivex = 0;
	flag[ivex]=1;	//标记
	stkPath[ivex] = j;	ivex ++;	//将i入队
	int begin = 0;		//标记开始搜索位置

	while (ivex>0)
	{
		while ( j!=k && ivex>0)	//未找到这样一条路径
		{
			for (int m= begin; m<G.vexnum; m++)
			{
				if (flag[m]==1)	//已经访问过
					continue;
				if (G.arcs[j][m].adj >0 && G.arcs[j][m].adj <INFINITY )	//找到邻接点
				{
					j = m;	//迭代，从 m 继续查找
				
					stkPath[ivex] = j;	flag[j] = 1;		//标记为已访问/////////////////////注意标记对象
					ivex ++;	//将i入队
					break;
				}
			}
			if ( m == G.vexnum)	//上个节点未找到,返回上次找到的节点，从begin位置开始查找
			{
				ivex --;
				begin = stkPath[ivex] +1;
				j = stkPath[ivex-1];
			}
			else		//上次找到，直接从头查找下一个节点
			{
				begin =0;
			}
		}

		//if (ivex == 0)	//已找玩所有顶点，未找到
		//	return false;
		printf ("\n");
		for (int n=0; n<ivex; n++)	//找到路径
		{
			printf ("%c ",G.vexs[ stkPath[n] ]); //输出从i 到 s 的路径
		}
		printf ("\n");

		//开始回溯
		ivex --;	
		begin = stkPath[ivex] +1;
		flag[begin-1] = 0;		//去除标记	///////////////////////////////注意标记对象
		j = stkPath[ivex-1];

	}//while (ivex>0)
	return true;
}

int LocateVex (MGraph G, VertexType v)	//返回v在G中的位置
{
	for (int i=0; i<G.vexnum && G.vexs[i]!=v; i++)
		;
	if (G.vexs[i]!=v)	//未找到
		return -1;
	else
		return i;
}