图.cpp

该程序实现图的建立与先深和先广遍历

#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
#include<assert.h>

#define VEXNUM 10

struct Graph
{	
	char Vexlist[VEXNUM];
	int  Edge[VEXNUM][VEXNUM];
	int  n;
};
struct point
{
	char a;
	char e;
};
struct stack
{
	point *ele[VEXNUM-1];
	int   top;
};
int  Empty(stack *);
void MakeNULL(stack *);
void Push(stack *,point *);
point *Pop(point *,stack *);
Graph *CreatGraph();
void  Operates(stack *,stack *,Graph *,int);
void  Operates2(stack *,stack *,Graph *,int);
void  VistGraphdep(Graph *);
void  VistGraphwild(Graph *);
main()
{
	Graph *graph;
	graph=CreatGraph();
	//建立图
	cout << "先深遍历如下:" << endl;
	VistGraphdep(graph);
	cout << "先广遍历如下:" << endl;
	VistGraphwild(graph);
	getchar();
	return 0;
}
void MakeNULL(stack *st)//将栈置空 ，时间复杂度O(1)
{
	st->top = VEXNUM-1;
}
void Push(stack *st,point *p)//压栈，时间复杂度O(1)
{
	st->top = st->top-1;
	st->ele[st->top] = p;
}
point *Pop(point *p,stack *st)//弹栈,时间复杂度O(1)
{
	p= st->ele[st->top];
	st->top = st->top+1;
	return p;
}
int Empty(stack *st)//判断栈是否为空,时间复杂度O(1)
{
	if(st->top == VEXNUM-1)
		return 1;
	else
		return 0;
}
Graph *CreatGraph()//时间复杂度O(n+2n*n+e),n由图的定点数决定，e由图的边数决定
{
	Graph *Pic = (Graph *)malloc(sizeof(Graph));
	int i,j,w;
	char choice;
	cout << "有多少个节点 ";
	cin >> Pic->n;
	assert(Pic->n <= VEXNUM);
	for(i = 0;i < Pic->n;i++)//建立节点集合 
	{
		cin >> Pic->Vexlist[i];
	}
	for(i = 0;i < Pic->n;i++)
		for(j = 0;j <Pic->n;j++)
			 Pic->Edge[i][j] = 0;
	//建立空图
	cout << "建立边集,是否为有向图(Y/N)";
	cin >> choice;
	do
	{
		cin >> i >> j >> w ;
		if(choice == 'y' || choice == 'Y')//建立有向图的边 
			Pic->Edge[i][j] = w;
		else if(choice == 'n' || choice =='N')//建立无向图的边
		{
			Pic->Edge[i][j] = w;
			Pic->Edge[j][i] = w;
		}
		else
			cout << "选择错误" << endl;
	}while(i >= 0 && j >= 0);
	cout << "图的矩阵表示如下:" << endl;
	for(i = 0;i < Pic->n;i++)//输出图的矩阵表示
	{
		for(j = 0;j <Pic->n;j++)
		{
			cout << Pic->Edge[i][j] << ' ' ;
		}
		cout << '\n';
	}
	cout << '\n';
	return Pic;
}
void VistGraphdep(Graph *MGraph)//时间复杂度O(n+x),n由图的定点数决定，x和图的连通性有关
{
	stack *s = (stack*)malloc(sizeof(stack));
	stack *s2 = (stack*)malloc(sizeof(stack));
	int  k = 0,j = 1;
	char ch = MGraph->Vexlist[k],op;
	point *q ;
	MakeNULL(s);
	MakeNULL(s2);
	cout << ch;								//输出选定的起点节点
	while(j	< MGraph->n)
	{
		op = MGraph->Vexlist[j];//标出下一个节点
		if(MGraph->Edge[k][j] != 0)//判断与起点之间是否有边
		{
			cout << "->" << op;
			ch=op;//将该节点赋值给目标节点
			k=j;
			j++;
		}
		else
		{
			q = (point *)malloc(sizeof(point));
			q->a = op;
			q->e = j;
			Push(s,q);
			j++;
		}
		//将按先深遍历过程中访问不到的节点存入栈中
	}
	while(Empty(s) == 0 || Empty(s2) == 0)//对栈中的节点重复先深遍历
	{
		if(Empty(s) == 0)
		{
			Operates(s,s2,MGraph,k);
		}
		else if(Empty(s2) == 0) 
		{
			Operates(s2,s,MGraph,k);
		}
	}
	cout <<"\n";
}
void VistGraphwild(Graph *Mgraph)//时间复杂度O(n+x),n由图的定点数决定，x和图的连通性有关
{
	stack *s = (stack*)malloc(sizeof(stack));
	stack *s2 = (stack*)malloc(sizeof(stack));
	int  k=0,j=1;
	char ch = Mgraph->Vexlist[k],op;
	point *q ;
	point *tar=(point *)malloc(sizeof(point));
	point *tar2=(point *)malloc(sizeof(point));
	MakeNULL(s);
	MakeNULL(s2);
	cout << ch << "->(";//输出起点
	while(j < Mgraph->n)
	{
		op = Mgraph->Vexlist[j];
		if(Mgraph->Edge[k][j] != 0)
		{
			cout << op << ' ';
			j++;
		}
		//将与起点之间有边的节点输出
		else
		{
			q = (point *)malloc(sizeof(point));
			q->a = op;
			q->e = j;
			Push(s,q);
			j++;
		}
		//将按先广遍历过程中访问不到的节点存入栈s中
	}
	cout << ")" << endl;
	while(Empty(s) == 0 || Empty(s2) == 0)//对栈中的节点重复先广遍历
	{
		if(Empty(s) == 0)
		{
			Operates2(s,s2,Mgraph,k);
			cout << ")" << endl;
		}
		else if(Empty(s2) == 0)
		{
			Operates2(s2,s,Mgraph,k);
			cout << ")" << endl;
		}
	}
}
void  Operates(stack *st,stack *st2,Graph *mgraph,int m)
{
	point *w = NULL;
	point *tar=(point *)malloc(sizeof(point));
	point *tar2=(point *)malloc(sizeof(point));
	tar=Pop(w,st);
	if(mgraph->Edge[m][tar->e] != 0)
		cout << "->" << tar->a;
	else
		cout << '\n' << tar->a;
	m=tar->e;
	while(Empty(st) == 0)
	{
		tar2=Pop(w,st);
		if(mgraph->Edge[m][tar2->e] != 0)
		{
			cout << "->" << tar2->a;
			m = tar2->e;
		}
		else
		{
			w = (point *)malloc(sizeof(point));
			w->a = tar2->a;
			w->e = tar2->e;
			Push(st2,w);
		}
	}
}
void  Operates2(stack *st,stack *st2,Graph *mgraph,int m)
{
	point *w = NULL;
	point *tar=(point *)malloc(sizeof(point));
	point *tar2=(point *)malloc(sizeof(point));
	tar=Pop(w,st);
	cout << tar->a << "->(";
	while(Empty(st) == 0)
	{
		tar2=Pop(w,st);
		if(mgraph->Edge[tar->e][tar2->e] != 0)
			cout <<  tar2->a;
		else
		{
			w = (point *)malloc(sizeof(point));
			w->a = tar2->a;
			w->e = tar2->e;
			Push(st2,w);
		}
	}
}