欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的邻接表存储、创建、深度优先遍历、广度优先遍历

程序员文章站 2022-05-22 09:57:56
...
#include<iostream>
#include<stdlib.h>
#include<malloc.h>
#include<queue>
#define MAXLEN 100
using namespace std;
typedef char DataType;
bool visited[MAXLEN];
typedef struct EdgeNode{   //边结点 
	int adjvex;            //邻接点在顶点数组中的下标 
	struct EdgeNode *next;//链域  指向下一个邻接点 
}EdgeNode;

typedef struct VertexNode{   //头结点 
	DataType data;  //顶点信息
	EdgeNode *firstEdge; //边表头指针(指向第一条依附于该顶点的弧的指针) 
}VertexNode; 

typedef struct Graph{       
	VertexNode adjList[MAXLEN];   
	int numVertexes,numEdges;  //图中当前的结点数及边数 
}Graph;
void CreateGraph(Graph *&G)   //建立无向图的邻接表 
{
//	if(G==NULL)
	G=(Graph*)malloc(sizeof(Graph));
	
	cout<<"输入图的顶点数:"<<endl;
	cin>>G->numVertexes;
	
	cout<<"输入图的边数:"<<endl;
	cin>>G->numEdges;
	
	cout<<"输入各个顶点的数据:"<<endl;
	for(int i=1;i<=G->numVertexes;i++)
	{
		cout<<"顶点"<<i<<":"<<endl;
		cin>>G->adjList[i].data;
		G->adjList[i].firstEdge=NULL; 
	 } 
	 
	 for(int k=1;k<=G->numEdges;k++)
	 {
	 	int i,j;
	 	cout<<"输入(vi,vj)上的顶点序号:"<<endl;
		cin>>i>>j;
		
		EdgeNode *p,*t;
		
		p=(EdgeNode*)malloc(sizeof(EdgeNode));
		if(G->adjList[i].firstEdge!=NULL)
		{
			t=G->adjList[i].firstEdge;
			while(t->next!=NULL)
			t=t->next;
			p->adjvex=j; p->next=NULL; t->next=p;
		}
		else
		{
			p->adjvex=j; p->next=G->adjList[i].firstEdge; G->adjList[i].firstEdge=p;
		}
		
		
		p=(EdgeNode*)malloc(sizeof(EdgeNode));
		if(G->adjList[j].firstEdge!=NULL)
		{
			t=G->adjList[j].firstEdge;
			while(t->next!=NULL)
			t=t->next;
			p->adjvex=i;p->next=NULL;t->next=p; 
		}
		else
		{
			p->adjvex=i; p->next=G->adjList[j].firstEdge; G->adjList[j].firstEdge=p;
		}
		
	 }
}
//深度优先遍历算法
void DFS(Graph *G,int i)
{
	visited[i]=true;
	cout<<G->adjList[i].data;
	
	EdgeNode *p=G->adjList[i].firstEdge;
	
	while(p)
	{
		if(!visited[p->adjvex])
		DFS(G,p->adjvex);
		p=p->next;
	}
 } 

void DFSTraverse(Graph *G)
{
	cout<<"深度优先遍历的结果为:"<<endl; 
	
	for(int i=1;i<=G->numVertexes;i++)
	visited[i]=false;       //初始化访问数组visited的元素值为false
	
	for(int i=1;i<=G->numVertexes;i++)
	if(!visited[i])     //结点尚未访问 
	{
		DFS(G,i); 
	 }
	 
	 cout<<endl; 
}
//广度优先遍历算法
void BFSTraverse(Graph *G)
{
	cout<<"广度优先遍历的结果为:"<<endl; 
	queue<int>q;
	for(int i=1;i<=G->numVertexes;i++)
	visited[i]=false;
	
	for(int i=1;i<=G->numVertexes;i++)
	{
		if(!visited[i])
		{
			visited[i]=true;
			cout<<G->adjList[i].data;
			q.push(i);
			
			while(!q.empty())
			{
				EdgeNode *p=G->adjList[q.front()].firstEdge;
				q.pop();
				while(p)
				{
					if(!visited[p->adjvex])
					{
						visited[p->adjvex]=true;
						cout<<G->adjList[p->adjvex].data;
						q.push(p->adjvex);
					}
					p=p->next;
				}
			}
		}
	}
	cout<<endl;
 } 
int main()
{
	Graph *G;
	CreateGraph(G);
	
	DFSTraverse(G);
	
	BFSTraverse(G);
}