图的广度优先遍历实现

文章目录

- 题目描述
- 输入
- 输出
- 样例输入
- 样例输出
- 代码实现
- - (1)、图的创建输出销毁
  - (2)、含广度优先遍历实现代码（c++）
  - (3)、含广度优先遍历实现代码（C）
- 运行结果

题目描述

图的广度优先遍历实现
要求：
1、以邻接表形式构造图；
2、打印输出邻接表；
3、输出：广度优先遍历序列；

输入：
顶点数、边数目。
点、边集合表示（1代表存在边，0代表不存在边）
输出：
（1）边逻辑正确，则输出：“输入正确！”
（2）边逻辑不正确，则输出：“输入边数不对！程序退出！！“
（3）输出邻接表存储；
（4）输出广义遍历结果。

输入

5 8 // 5代表顶点数， 8 代表边数目
0 1 0 1 1

1 0 1 1 0

0 1 0 1 1

1 1 1 0 1

1 0 1 1 0

输出

输入正确！
图G的邻接表:
0: 1[1]→ 3[1]→ 4[1]→∧
1: 0[1]→ 2[1]→ 3[1]→∧
2: 1[1]→ 3[1]→ 4[1]→∧
3: 0[1]→ 1[1]→ 2[1]→ 4[1]→∧
4: 0[1]→ 2[1]→ 3[1]→∧
广度优先序列: 2 1 3 4 0

样例输入

5 8
0 1 0 1 1

1 0 1 1 0

0 1 0 1 1

1 1 1 0 1

1 0 1 1 1

样例输出

输入边数不对！程序退出！！

代码实现 (1)、图的创建输出销毁

#include 
#include 

using namespace std;

#define MAXV 100
#define INF 32767   //定义无穷

typedef int InfoType;

//边
typedef struct ANode
{
    int adjvex;
    struct ANode *nextarc;
    int weight;
} ArcNode;

//顶点
typedef struct Vnode
{
    InfoType info;
    ArcNode *firstarc;
} VNode;

//图
typedef struct
{
    VNode adjlist[MAXV];
    int n, e;
}AdjGraph;


//创建图运算算法
void GreateAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e)
{
    int i, j;
    ArcNode *p;
    G = (AdjGraph *)malloc(sizeof(AdjGraph));
    //给邻接表中所有头结点的指针域置初值
    for(i = 0; i < n; i++)
    {
        G->adjlist[i].firstarc = NULL;
    }
    //检查邻接矩阵中的每个元素
    for(i = 0; i < n; i++)
    {
        for(j = n-1; j >= 0; j--)
        {
            //存在一条边
            if(A[i][j] != 0 && A[i][j] != INF)
            {
                //创建一个结点p
                p = (ArcNode *)malloc(sizeof(ArcNode));
                //存放邻接结点
                p->adjvex = j;
                //存放权
                p->weight = A[i][j];
                //采用头插法插入结点p
                p->nextarc = G->adjlist[i].firstarc;
                G->adjlist[i].firstarc = p;
            }
        }
    }
    G->n = n;
    G->e = e;
}


//输出图的运算算法
void DispAdj(AdjGraph *G)
{
    int i;
    ArcNode *p;

    for(i = 0; i < G->n; i++)
    {
        p = G->adjlist[i].firstarc;
        cout<adjvex<<"["<weight<<"]"<<"-> ";
            p = p->nextarc;
        }
        cout<<"^"<n; i++)
    {
        //p指向第i个单链表的头结点
        pre = G->adjlist[i].firstarc;
        if(pre != NULL)
        {
            p = pre->nextarc;
            //释放第i个单链表的所有边结点
            while(p != NULL)
            {
                free(pre);
                pre = p;
                p = p->nextarc;
            }
            free(pre);
        }
    }
    //释放头结点数组
    free(G);
}



int main()
{
    AdjGraph *G;
    int A[MAXV][MAXV];
    int n;
    int e;
    int sum = 0;

    //输入顶点数
    cin>>n;
    //输入边的个数
    cin>>e;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cin>>A[i][j];
            if(A[i][j] == 1)
            {
                sum++;
            }
        }
    }
    
    if(sum != 2*e)
    {
        cout<<"输入边数不对！程序退出！！"< 
(2)、含广度优先遍历实现代码（c++） 
#include 
#include 

using namespace std;

#define MAXV 100
#define MaxSize 10
#define INF 32767   //定义无穷

typedef int InfoType;
typedef int ElemType;


//边
typedef struct ANode
{
    int adjvex;
    struct ANode *nextarc;
    int weight;
} ArcNode;

//顶点
typedef struct Vnode
{
    InfoType info;
    ArcNode *firstarc;
} VNode;

//图
typedef struct
{
    VNode adjlist[MAXV];
    int n, e;
}AdjGraph;

typedef struct
{
    ElemType data[MaxSize];
    int front, rear;
} SqQueue;


//创建图运算算法
void GreateAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e)
{
    int i, j;
    ArcNode *p;
    G = (AdjGraph *)malloc(sizeof(AdjGraph));
    //给邻接表中所有头结点的指针域置初值
    for(i = 0; i < n; i++)
    {
        G->adjlist[i].firstarc = NULL;
    }
    //检查邻接矩阵中的每个元素
    for(i = 0; i < n; i++)
    {
        for(j = n-1; j >= 0; j--)
        {
            //存在一条边
            if(A[i][j] != 0 && A[i][j] != INF)
            {
                //创建一个结点p
                p = (ArcNode *)malloc(sizeof(ArcNode));
                //存放邻接结点
                p->adjvex = j;
                //存放权
                p->weight = A[i][j];
                //采用头插法插入结点p
                p->nextarc = G->adjlist[i].firstarc;
                G->adjlist[i].firstarc = p;
            }
        }
    }
    G->n = n;
    G->e = e;
}


//输出图的运算算法
void DispAdj(AdjGraph *G)
{
    int i;
    ArcNode *p;

    for(i = 0; i < G->n; i++)
    {
        p = G->adjlist[i].firstarc;
        cout<<" "<adjvex<<"["<weight<<"]"<<"→";
            p = p->nextarc;
        }
        cout<<"^"<n; i++)
    {
        //p指向第i个单链表的头结点
        pre = G->adjlist[i].firstarc;
        if(pre != NULL)
        {
            p = pre->nextarc;
            //释放第i个单链表的所有边结点
            while(p != NULL)
            {
                free(pre);
                pre = p;
                p = p->nextarc;
            }
            free(pre);
        }
    }
    //释放头结点数组
    free(G);
}

void InitQueue(SqQueue *&q)
{
    q = (SqQueue *)malloc(sizeof(SqQueue));
    q->front = q->rear = 0;
}


void DestroyQueue(SqQueue *&q)
{
    free(q);
}

bool QueueEmpty(SqQueue *q)
{
    return (q->front == q->rear);
}

bool enQueue(SqQueue *&q, ElemType e)
{
    if((q->rear+1)%MaxSize == q->front)
    {
        //printf("队列已满，%d进队不成功！n", e);
        cout<<"队列已满，%d进队不成功！n"<rear = (q->rear+1)%MaxSize;
    q->data[q->rear] = e;
    return true;

}

bool deQueue(SqQueue *&q, ElemType &e)
{
    if(q->front == q->rear)
        return false;
    q->front = (q->front + 1)%MaxSize;
    e = q->data[q->front];
    return true;
}

//广度优先序列
void BFS(AdjGraph *G, int v)
{
    int w, i;
    ArcNode *p;
    SqQueue *qu;
    InitQueue(qu);
    int visited[MAXV];
    for(i = 0; i < G->n; i++)
    {
        visited[i] = 0;
    }
    cout<<"广度优先序列:"<adjlist[w].firstarc;
        while(p != NULL)
        {
            if(visited[p->adjvex] == 0)
            {
                cout<<" "<adjvex;
                visited[p->adjvex] = 1;
                enQueue(qu, p->adjvex);
            }
            p = p->nextarc;
        }

    }
    cout<>n;
    //输入边的个数
    cin>>e;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cin>>A[i][j];
            if(A[i][j] == 1)
            {
                sum++;
            }
        }
    }

    if(sum != 2*e)
    {
        cout<<"输入边数不对！程序退出！！"< 
(3)、含广度优先遍历实现代码（C） 
//广度优先遍历算法

#define MaxSize 100

//图的基本运算算法
#include 
#include 
//图的两种存储结构
#define INF 32767				//定义∞
#define	MAXV 100				//最大顶点个数
typedef char InfoType;
#include
using namespace std;
//以下定义邻接矩阵类型
typedef struct
{	int no;						//顶点编号
	InfoType info;				//顶点其他信息
} VertexType;					//顶点类型
typedef struct
{	int edges[MAXV][MAXV];		//邻接矩阵数组
	int n,e;					//顶点数，边数
	VertexType vexs[MAXV];		//存放顶点信息
} MatGraph;						//完整的图邻接矩阵类型

//以下定义邻接表类型
typedef struct ANode
{	int adjvex;					//该边的邻接点编号
	struct ANode *nextarc;		//指向下一条边的指针
	int weight;					//该边的相关信息，如权值（用整型表示）
} ArcNode;						//边结点类型
typedef struct Vnode
{	InfoType info;				//顶点其他信息
	int count;					//存放顶点入度,仅仅用于拓扑排序
	ArcNode *firstarc;			//指向第一条边
} VNode;						//邻接表头结点类型
typedef struct 
{	VNode adjlist[MAXV];		//邻接表头结点数组
	int n,e;					//图中顶点数n和边数e
} AdjGraph;						//完整的图邻接表类型

void CreateMat(MatGraph &g,int A[MAXV][MAXV],int n,int e) //创建图的邻接矩阵
{
	int i,j;
	g.n=n; g.e=e;
	for (i=0;iadjlist[i].firstarc=NULL;
	for (i=0;i=0;j--)
			if (A[i][j]!=0 && A[i][j]!=INF)			//存在一条边
			{	p=(ArcNode *)malloc(sizeof(ArcNode));	//创建一个结点p
				p->adjvex=j;
				p->weight=A[i][j];
				p->nextarc=G->adjlist[i].firstarc;	//采用头插法插入结点p
				G->adjlist[i].firstarc=p;
			}
	G->n=n; G->e=n;
}
void DispAdj(AdjGraph *G)	//输出邻接表G
{
	int i;
	ArcNode *p;
	for (i=0;in;i++)
	{
		p=G->adjlist[i].firstarc;
		printf("%3d: ",i);//"  0:   "
		while (p!=NULL)
		{
			printf("%3d[%d]→",p->adjvex,p->weight);
			p=p->nextarc;
		}
		printf("∧n");
	}
}
void DestroyAdj(AdjGraph *&G)		//销毁图的邻接表
{	int i;
	ArcNode *pre,*p;
	for (i=0;in;i++)			//扫描所有的单链表
	{	pre=G->adjlist[i].firstarc;	//p指向第i个单链表的首结点
		if (pre!=NULL)
		{	p=pre->nextarc;
			while (p!=NULL)			//释放第i个单链表的所有边结点
			{	free(pre);
				pre=p; p=p->nextarc;
			}
			free(pre);
		}
	}
	free(G);						//释放头结点数组
}

typedef int ElemType;
typedef struct 
{	
	ElemType data[MaxSize];
	int front,rear;		//队首和队尾指针
} SqQueue;
void InitQueue(SqQueue *&q)
{	q=(SqQueue *)malloc (sizeof(SqQueue));
	q->front=q->rear=0;
}
void DestroyQueue(SqQueue *&q)
{
	free(q);
}
bool QueueEmpty(SqQueue *q)
{
	return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e)
{	if ((q->rear+1)%MaxSize==q->front)	//队满上溢出
		return false;
	q->rear=(q->rear+1)%MaxSize;
	q->data[q->rear]=e;
	return true;
}
bool deQueue(SqQueue *&q,ElemType &e)
{	if (q->front==q->rear)				//队空下溢出
		return false;
	q->front=(q->front+1)%MaxSize;
	e=q->data[q->front];
	return true;
}


void BFS(AdjGraph *G,int v)  
{
	int w,i;
	ArcNode *p;
	SqQueue *qu;							//定义环形队列指针
	InitQueue(qu);							//初始化队列
	int visited[MAXV];            			//定义顶点访问标志数组
	for (i=0;in;i++) visited[i]=0;		//访问标志数组初始化
	printf("%2d",v); 						//输出被访问顶点的编号
	visited[v]=1;              				//置已访问标记
	enQueue(qu,v);
	while (!QueueEmpty(qu))       			//队不空循环
	{	
		deQueue(qu,w);						//出队一个顶点w
		p=G->adjlist[w].firstarc; 			//指向w的第一个邻接点
		while (p!=NULL)						//查找w的所有邻接点
		{	
			if (visited[p->adjvex]==0) 		//若当前邻接点未被访问
			{
				printf("%2d",p->adjvex);  	//访问该邻接点
				visited[p->adjvex]=1;		//置已访问标记
				enQueue(qu,p->adjvex);		//该顶点进队
           	}
           	p=p->nextarc;              		//找下一个邻接点
		}
	}
	printf("n");
}

int main()
{	int sum1=0;
	int sum0=0;
	AdjGraph *G;
	int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},
			{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};
	int n=5, e=8;
	cin>>n>>e;
	for(int i=0;i>A[i][j];
		}
	}
	for(int i1=0;i1 
运行结果

图的广度优先遍历实现

C/C++/C#相关栏目本月热门文章