graph.cpp

数据结构有关图的算法。矩阵和链表实现的都有。实现先序中序后序遍历算法。

#include<iostream>
using namespace std;
#define max1 50
#define max2 50
struct vertex1
{ int  ver[max1];
  int  e[max1][max1];
  int m,n;
};

//定义队列
struct QUEUE{ int que[max1];
              int first,last;
};

struct edge
{ int data;
  int weight;
  edge *next;
};
//定义点的结点
struct verteies
{ int ch;
  edge *first;
};
//定义邻接表
struct vertex2
{ verteies head[max1];
  int m,n;
};
//用邻接表创造图
int visit[max1];
void creat1(vertex1 *G1);
void find1(vertex1 *G1,int i);
void bfs1(vertex1 *G1);
void dfs1(vertex1 *G1);
int DEQUEUE(QUEUE *q);
void MAKEQUEUE(QUEUE *q);
void ENQUEUE(int x,QUEUE *q);
int EMPTY(QUEUE *q);
void creat2(vertex2 *G2);
void bfs2(vertex2 *G2);
void find2(vertex2 *G2,int i);
void dfs2(vertex2 *G2);
int main (void)
{   vertex1 *G1=new vertex1;
    vertex2 *G2=new vertex2;
	creat1(G1);
	bfs1(G1);
    dfs1(G1);
	creat2(G2);
	 bfs2(G2);
	 dfs2(G2);
	delete G1,G2;
	return 0;
}
//---------队列函数-------------
void MAKEQUEUE(QUEUE *q)
{ q->first=q->last=0;
}
int EMPTY(QUEUE *q)
{ if(q->first==q->last)
   return 0;
}
void ENQUEUE(int x,QUEUE *q)
{ q->last++;
  q->que[q->last]=x;
}
int DEQUEUE(QUEUE *q)
{ q->first++;
  return q->que[q->first];
}
//--------------创建邻接矩阵形式----------------
void creat1(vertex1 *G1)
{    int i,j;
     int a,b,k;
	cout<<"请输入顶点数，边数"<<endl;
	cin>>G1->m>>G1->n;
	cout<<"请输入各个顶点(用数字表示)："<<endl;
	for(i=0;i<G1->m;i++)
	   cin>>G1->ver[i];
    for(i=0;i<G1->m;i++)
		for(j=0;j<G1->m;j++)
			G1->e[i][j]=0;
    cout<<"请输入各个边的权值(两点,权值)："<<endl;
	for(j=0;j<G1->n;j++)
	{  cin>>a>>b>>k;
	   G1->e[a][b]=G1->e[b][a]=k;
	}
}
void bfs1(vertex1 *G1)
{   int i; 
    for(i=0;i<G1->m;i++)
		visit[i]=0;
    for(i=0;i<G1->m;i++)
		if(visit[i]==0)
			find1(G1,i);
	cout<<endl;
}
void find1(vertex1 *G1,int i)
{      
  cout<<G1->ver[i];
    visit[i]=1;
	for(int j=0;j<G1->m;j++)
		if(G1->e[i][j]!=0&&visit[j]==0)
			find1(G1,j);
}
void dfs1(vertex1 *G1)
{ QUEUE *q=new QUEUE;
  int i,k;
  for(int i=0;i<G1->m;i++)
	  visit[i]=0;
  MAKEQUEUE(q);
  for(i=0;i<G1->m;i++)
  { 
	  if(visit[i]==0)
      { cout<<G1->ver[i];
        visit[i]=1;
		ENQUEUE(G1->ver[i],q);
		while(EMPTY(q)!=0)
	    {    k=DEQUEUE(q);
			for(int j=0;j<G1->m;j++)
				if(G1->e[k][j]!=0&&visit[j]==0)
				{ cout<<G1->ver[j];
			      visit[j]=1;
                  ENQUEUE(G1->ver[j],q);
				}
		}
	  }
    }
  cout<<endl;
}
void creat2(vertex2 *G2)
{   	int i,p,q,k;
	cout<<"请输入顶点数，边数"<<endl;
	cin>>G2->m>>G2->n;
    cout<<"请输入顶点:"<<endl;
	for(i=0;i<G2->m;i++)
	{ cin>>G2->head[i].ch;
	  G2->head[i].first=NULL;
	}	
	cout<<"请输入边(顶点1.顶点2.权值)"<<endl;
    for(i=0;i<G2->n;i++)
	{ cin>>p>>q>>k;
	  edge *ptr=new edge;
	  ptr->data=q;
	  ptr->weight=k;
	  ptr->next=G2->head[p].first;
	  G2->head[p].first=ptr;
	  ptr=new edge;
	  ptr->data=p;
	  ptr->weight=k;
	  ptr->next=G2->head[q].first;
	  G2->head[q].first=ptr;
	}
    
}
void bfs2(vertex2 *G2)
{   int i; 

     for(i=0;i<G2->m;i++)
	   visit[i]=0;
  for(i=0;i<G2->m;i++)
		if(visit[i]==0)
			find2(G2,i);
	cout<<endl;
}
void find2(vertex2 *G2,int i)
{   edge *p=new edge; 
    int j=0;
    cout<<G2->head[i].ch;
    visit[i]=1;
	p=G2->head[i].first;
	while(p!=NULL)
	{  for(j=0;j<G2->m&&p->data!=G2->head[j].ch;)
			   j++;
		   if(visit[j]==0)
			 find2(G2,j);
		     p=p->next;
	}
}
void dfs2(vertex2 *G2)
{  int i,k,j;
     QUEUE *q=new QUEUE;
	 edge *p=new edge;
	 MAKEQUEUE(q);
	cout<<"先广遍历："<<endl;
   for(i=0;i<G2->m;i++)
	   visit[i]=0;
   for(i=0;i<G2->m;i++)
   { if(visit[i]==0)
     {  cout<<G2->head[i].ch;
        ENQUEUE(G2->head[i].ch,q);
        visit[i]=1;
      
      while(EMPTY(q)!=0)
      {  k=DEQUEUE(q);
	     for( j=0;j<G2->m&&k!=G2->head[j].ch;)
			 j++;
	     k=G2->head[j].ch;
         p=G2->head[k].first;
         while(p!=NULL)
		 { for( j=0;j<G2->m&&p->data!=G2->head[j].ch;)
			 j++;
		   if(visit[j]==0)
		   {cout<<p->data;
		   visit[j]=1;
		  ENQUEUE(G2->head[j].ch,q);
		   }
		   p=p->next;
		 }
      }
     }
   }
}