图.cpp

图的操作,实现遍历功能

// 23.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "iostream.h"
#include "string.h"

#define MAX_VERTEX_NUM 5  //最大的顶点个数




class MGraph{
public:
	   int vexs[MAX_VERTEX_NUM]; //顶点向量
	   int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //领接矩阵
	   int vexnum,arcnum; //图的当前顶点数和弧数
};

class Graph{
public:
	   MGraph data;
	   bool CreatGraph(void); //创建图
	   bool DFSTraverse(void);//遍历图
	   void DFS(int k);
	   void NextAdjVex(int k);
};

Graph *mygraph=new Graph();


bool Graph::CreatGraph()  //创建图
{

	int i,j;
	int HVex,TVex;  //确定顶点的关系
	char OPTION;
	char HArc[10],TArc[10]; //HArc为弧头，TArc为弧尾
	
	for(i=1;i<=5; i++)
	{
		printf("vexs%d=",i);
		cin>>data.vexs[i];
	}
	for(i=0;i<5;i++)
		for(j=0;j<5;j++)
			data.arcs[i][j]=0;

reput: 
		{
			cout<<endl<<endl<<"请输入顶点间的关系："<<endl;
	        cout<<endl<<"弧头=";
			cin>>HArc;
			if(strcmp(HArc,"v1")==0)   HVex=0;
			if(strcmp(HArc,"v2")==0)   HVex=1;
			if(strcmp(HArc,"v3")==0)   HVex=2;
			if(strcmp(HArc,"v4")==0)   HVex=3;
			if(strcmp(HArc,"v5")==0)   HVex=4;	
	        cout<<endl<<"弧尾=";
			cin>>TArc;
			if(strcmp(TArc,"v1")==0)   TVex=0;
			if(strcmp(TArc,"v2")==0)   TVex=1;
			if(strcmp(TArc,"v3")==0)   TVex=2;
			if(strcmp(TArc,"v4")==0)   TVex=3;
			if(strcmp(TArc,"v5")==0)   TVex=4;				
	        data.arcs[HVex][TVex]=1;
		}
		cout<<endl<<"是否继续输入顶点间的关系（y OR n) OPTION=";
		cin>>OPTION;
		if(OPTION=='y') goto reput;

		return true;
}



int visited[MAX_VERTEX_NUM];
int v;



void NextAdjVex(v)
{   
	int n;
    for(n=0;n<5;n++)
	{
		    if(data.arcs[v][n]=1)  break;			    
	}
    if(n<5) v=n;

}



void Graph::DFS(v)
{   
	visited[v]=1;
	cout<<data.vexs[v];
    for(v;v<5;v=mygraph->NextAdjVex(v))   
	{
		if(!visited[v])  mygraph->DFS(v);       
	}
}


bool Graph::DFSTraverse()  //遍历图
{
    int i;	
	for(i=0;i<5;++i)    visited[i]=0;
	cout<<"请输入你想访问的第一个顶点v=";
	cin>>v;

	mygraph->DFS(v);

	return true;
}




int main(int argc, char* argv[])
{
	
	mygraph->CreatGraph();
	mygraph->DFSTraverse();
	return 0;
}