图.cpp

图的遍历

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

#include "stdafx.h"
#include<iostream>
using namespace std;

const int maxNumV=30;
class Graph;//图的类的声明
struct EdgeNode//边信息
{
	friend class Graph;
	int adjvex;//在数组中的
	EdgeNode *nextEdge;
	EdgeNode(){adjvex=NULL; nextEdge=NULL;}
};
struct VertexNode
{
	friend class Graph;
	int data;
	EdgeNode *firstEdge;
};
class Graph
{
private:
	VertexNode *vertexesTable;
	int currNumV;//当前的顶点数 
	int currNumE;//当前的边数
	int getVertexPox(int v);//返回顶点v在数组中的位置
public:
	Graph():currNumV(0),currNumE(0){vertexesTable=new VertexNode[maxNumV];}
	~Graph();
	int insertVextex(int v);//插入顶点
	int insertEdge(int v1,int v2);//插入边
//	void delVertex(int v);//删除顶点以及和顶点相关联的边
//	void delEdge(int v1,int v2);//删除边(v1,v2)
	bool empty()const{return currNumV==0;}//判断图是否为空，图空返回1，否则返回0；
	int numVertex(){return currNumV;}//返回图的顶点数
	int numEdge(){return currNumE;}//返回边数
	void DFT();
	void DFS(int i,int *visited);
};
int Graph::getVertexPox(int v)//得到顶点v在数组中的位置
{
	for(int i=0;i<currNumV;i++)
	{
		if(vertexesTable[i].data==v)
			return i;
	}
		return -1;
}
Graph::~Graph()//析构函数
{
	for(int i=0;i<currNumV;i++)
	{
		EdgeNode *p=vertexesTable[i].firstEdge;
		EdgeNode *q;
		while(p)
		{
			q=p;
			p=q->nextEdge;
			delete q;
		}
	}
	delete []vertexesTable;
}
int Graph::insertVextex(int v)//插入顶点
{
	if(currNumV<maxNumV-1)
	{
		vertexesTable[currNumV].data=v;
		vertexesTable[currNumV].firstEdge=NULL;
		currNumV++;
		return 1;
	}
	return 0;
}
int Graph::insertEdge(int v1,int v2)//插入边
{
	int m,n;
	m=getVertexPox(v1);
	n=getVertexPox(v2);
	EdgeNode *p=new EdgeNode;
	EdgeNode *q=vertexesTable[m].firstEdge;
	p->adjvex=n;
	p->nextEdge=NULL;
	if(m!=-1&&n!=-1)
	{
		if(q==NULL)
			vertexesTable[m].firstEdge=p;
		else
		{
			while(q->nextEdge!=NULL)
			{
				q=q->nextEdge;
			}
		//	for(;q->nextEdge!=NULL;q=q->nextEdge);
				q->nextEdge=p;
		}
	}
	return 0;
}

void Graph::DFT()
{
	int i,n=numVertex();
	int *visited=new int[n];
	for(i=0;i<n;i++)
		visited[i]=0;
	for (i=0;i<n;i++)
	{
		if(!visited[i])
			DFS(i,visited);
	}

}
void Graph::DFS(int i,int *visited)
{
	cout<<vertexesTable[i].data<<" ";
	visited[i]=1;
	EdgeNode *p;
	p=vertexesTable[i].firstEdge;
	int n;
	if(p!=NULL)
	{
		n=p->adjvex;
		if(visited[n])
		{
			while(visited[n])
			{
				p=p->nextEdge;
			//	n=p->adjvex;
			}
		}
		if(!visited[n])
			DFS(n,visited);
		while(p->nextEdge)
		{		
			while(visited[n]&&p->nextEdge);
			{
				p=p->nextEdge;
				n=p->adjvex;
			}
			if(!visited[n])
			DFS(n,visited);
		}
	}
	
}


int main(int argc, char* argv[])
{
	Graph graph;//声明对象
	graph.insertVextex(4);//连续插入顶点
	graph.insertVextex(8);//1
	graph.insertVextex(9);//2
	graph.insertVextex(3);//3
	graph.insertVextex(20);//4
	graph.insertVextex(55);//5
	graph.insertVextex(7);//6
	graph.insertVextex(23);//7
	graph.insertVextex(6);//8
	graph.insertEdge(4,8);//连续插入边
	graph.insertEdge(8,9);
	graph.insertEdge(3,55);
	graph.insertEdge(55,7);
	graph.insertEdge(7,23);
	graph.insertEdge(9,3);
/*	graph.insertEdge();
	graph.insertEdge();
	graph.insertEdge();
	graph.insertEdge();
	graph.insertEdge();
	graph.insertEdge();
	graph.insertEdge();
	graph.insertEdge();
	graph.insertEdge();
	graph.insertEdge();
	graph.insertEdge();
	graph.insertEdge();
	graph.insertEdge();*/
	graph.DFT();
		return 0;
}