graph.cpp

用C实现树和图的相关算法

#include <stdio.h>
#include <malloc.h>
#include "list.h"
#include "string.h"
#include "poly.h"
#include "graph.h"
#include "queue.h"


graph newGraph(mystring name)
{
  graph g=(graph)malloc(sizeof(*g));
  g->graphName=name;
  g->vertices=newList();
  return g;
}



graphVertex newGraphVertex(poly ver)
{
	graphVertex v=(graphVertex)malloc(sizeof(*v));
	v->edges=newList();
	v->level=0;
	v->vInfo=ver;
	v->visitFlag=0; 
	v->x=0;
	v->y=0;
	return v;
}


graphEdge newGraphEdge(graphVertex start,graphVertex end)
{
	graphEdge e1=(graphEdge)malloc(sizeof(*e1));
	e1->eInfo=NULL;
	e1->from=start;
	e1->to=end;
	e1->eTpye=ORD;
	return e1;
}


void graphInsertVertex (graph g, poly x)
{
	graphVertex v=newGraphVertex(x);
	insertListTail(g->vertices,v);	
}


graphVertex searchGraphVertex(graph g,poly v)
{
	list l=g->vertices;
	l=l->next;
	while(l)
	{
		if(  ((graphVertex)(l->element))->vInfo==v)
			return (graphVertex)(l->element);
		l=l->next;
	}

	

	printf("\nSearch Failure\n");
	return NULL;
}



graphEdge searchEdge(graph g,poly start,poly end)
{
	graphVertex vFrom=searchGraphVertex(g,start);
	graphVertex vTo=searchGraphVertex(g,end);
	if(vFrom&&vTo)                             //两个结点都存在
	{
		list l=vFrom->edges;
		l=l->next;
		while(l)
		{
			if(	!equalString((mystring)(((graphVertex)(l->element))->vInfo),(mystring)vTo))
				return (graphEdge)(l->element);
			l=l->next;
		}
	}

	return NULL;
}




void graphInsertEdge (graph g, poly from, poly to)
{
	graphVertex vFrom=searchGraphVertex(g,from);
	graphVertex vTo=searchGraphVertex(g,to);
	if(vFrom&&vTo)                               //两个结点都存在
	{
		graphEdge e=newGraphEdge(vFrom,vTo);
		insertListTail(vFrom->edges,e);
	}
	else
		printf("\ninsert edge failure");

}




void graphInsertEdgeInfo (graph g, poly start, poly end, poly info)
{
	graphEdge e=searchEdge(g,start,end);
	if(e)
	{
		e->eInfo=info;
	}

	else
		printf("\nthe edge no exist\n");

}

void graphClear(graph p)
{
	list l=p->vertices;
	l=l->next;
	while(l)
	{
		graphVertex v=(graphVertex)(l->element);
		v->visitFlag=0;
		l=l->next;
	}

}

void graphDfsSub(graph g,graphVertex start)
{

	
	if(!start->visitFlag)
	{
		visitGraph(start->vInfo);
		start->visitFlag=1;
		list l=start->edges;
		l=l->next;
		while(l)
		{
			graphEdge e=(graphEdge)(l->element);
			graphVertex v=e->to;
			if(!v->visitFlag)
			{
				e->eTpye=TRE;
			}
			graphDfsSub(g,e->to);
			l=l->next;
		}
	}
}

void graphDfs(graph g, graphVertex start)
{
	graphDfsSub(g,start);

	list l=g->vertices;
	l=l->next;

	while(l)
	{
		graphVertex v=(graphVertex)(l->element);
		if(!v->visitFlag)
		{
			graphDfsSub(g,v);
		}
		l=l->next;
	}


}


void graphBfsSub(graph g,graphVertex start)
{
	queue q=newQueue();
	enQueue(q,start);
	
	while(!queueIsEmpty(q))
	{
		poly pTemp=deQueue(q);
		graphVertex vTemp=(graphVertex)(pTemp);

		if(vTemp->visitFlag==0)
		{
			visitGraph(vTemp->vInfo);
			vTemp->visitFlag=1;

		}
		list l=vTemp->edges;
		l=l->next;

		while(l)
		{
			graphEdge e=(graphEdge)(l->element);
			graphVertex v=e->to;
			if(v->visitFlag==0)
			{
				e->eTpye=TRE;
				enQueue(q,v);
			}

			l=l->next;
		}
	}
}

void graphBfs (graph g, graphVertex start)
{
	graphBfsSub(g,start);

	list l=g->vertices;
	l=l->next;

	while(l)
	{
		graphVertex v=(graphVertex)(l->element);
		if(v->visitFlag==0)
		{
			graphBfsSub(g,v);
		}
		l=l->next;
	}

}

/*void outputDfsEdge(graph g,graphVertex start)
{
	graphClear(g);
	printf("\nDFS:\n");
	graphDfs(g,start);

	list l=g->vertices;
	l=l->next;
	printf("\ntree edge:\n");
	while(l)
	{
		graphVertex v=(graphVertex)(l->element);
		list lEdge=v->edges;
		lEdge=lEdge->next;
		while(lEdge)
		{
			graphEdge e=(graphEdge)(lEdge->element);
			if(e->eTpye==TRE)
			{
				visit(e->from->vInfo);
				visit(e->to->vInfo);
				printf("\n");
			}
			lEdge=lEdge->next;
		}

		l=l->next;
	}
}

*/

tree graphDfsTree (graph g, graphVertex start)
{
	mystring gName=g->graphName;
	mystring tName=contactString(gName,"_Dfs_Tree");
	tree t=newTree(tName);

	graphClear(g);
	graphDfs(g,start);

	list l=g->vertices;
	l=l->next;

	list lv1=l;
	while(lv1)                                                   //先建立结点
	{
		graphVertex gV=(graphVertex)(lv1->element);
		treeInsertVertex(t,gV->vInfo);
		lv1=lv1->next;
	}


	list lv2=l;                                                   //建立边
	while(lv2)
	{
		graphVertex gV2=(graphVertex)(lv2->element);               //取出结点
		list lEdge=gV2->edges;
		lEdge=lEdge->next;
		while(lEdge)                                               
		{
			graphEdge gE=(graphEdge)(lEdge->element);
			if(gE->eTpye==TRE)
			{
				mystring p1=(mystring)(gE->from->vInfo);
				mystring p2=(mystring)(gE->to->vInfo);

				printf("\nTree edge:\n");
				visit(p1);
				visit(p2);
				
				treeInsertEdge(t,p1,p2);

			}

			lEdge=lEdge->next;
		}
		lv2=lv2->next;

	}

	return t;
}




tree graphBfsTree (graph g, graphVertex start)
{
	mystring gName=g->graphName;
	mystring tName=contactString(gName,"_BFS_Tree");
	tree t=newTree(tName);
	
	graphClear(g);
	graphBfs(g,start);

	list l=g->vertices;
	l=l->next;

	list lv1=l;
	while(lv1)                                                   //先建立结点
	{
		graphVertex gV=(graphVertex)(lv1->element);
		treeInsertVertex(t,gV->vInfo);
		lv1=lv1->next;
	}

	list lv2=l;                                                   //建立边
	while(lv2)
	{
		graphVertex gV2=(graphVertex)(lv2->element);               //取出结点
		list lEdge=gV2->edges;
		lEdge=lEdge->next;
		while(lEdge)                                               
		{
			graphEdge gE=(graphEdge)(lEdge->element);
			if(gE->eTpye==TRE)
			{
				mystring p1=(mystring)(gE->from->vInfo);
				mystring p2=(mystring)(gE->to->vInfo);

				printf("\nTree edge:\n");
				visit(p1);
				visit(p2);
				
				treeInsertEdge(t,p1,p2);

			}

			lEdge=lEdge->next;
		}
		lv2=lv2->next;

	}




	
	
	return t;


}

void visitGraph(poly x)
{
	printf("%s ",x);
}

int graphInDegreeIs(graph g)                              //判断该图是否有入度为零的结点
{
	list l=g->vertices;
	l=l->next;

	while(l)
	{
		graphVertex v=(graphVertex)(l->element);
		if(v->x==0)
			return 1;
		l=l->next;
	}
	printf("ai");
	return 0;

}


void graphTopoSort(graph g)
{
	list l=g->vertices;
	l=l->next;

	list l1=l;
	while(l1)                                            //求出各个结点的入度
	{
		graphVertex vG=(graphVertex)(l1->element);
		list eList=vG->edges;
		eList=eList->next;
		while(eList)
		{
			graphEdge eG=(graphEdge)(eList->element);
			(eG->to->x)++;
			eList=eList->next;
		}

		l1=l1->next;
	}

	list l2=l;
	
	while(graphInDegreeIs(g)==1)
	{
		
		while(l2)
		{
		graphVertex vG2=(graphVertex)(l2->element);
//		printf("\n%s  %d",vG2->vInfo,vG2->x);                       //第一次执行时，打印出入度
		
		if(vG2->x==0)
		{
			visit(vG2->vInfo);
			list lVE=vG2->edges;
			lVE=lVE->next;
			while(lVE)
			{
				graphEdge eVG=(graphEdge)(lVE->element);
				(eVG->to->x)--;
				lVE=lVE->next;
			}

		}
		
		
		l2=l2->next;
		}
	}



}