无向图G的广度优先搜索和深度优先搜索以及完整程序

news/2024/7/20 20:13:57 标签: 深度优先, 算法, 宽度优先, 数据结构

图的遍历算法有两种：广度优先搜索和深度优先搜索

一.广度优先搜索类似于层次遍历，需要借助辅助队列

空间复杂度为O(|V|);空间复杂度由辅助队列大小决定

时间复杂度为O(|V|+|E|)

为避免同一顶点被多次访问，设计visited[]来标记顶点

二.深度优先搜索类似于树的先序遍历，递归算法

空间复杂度：最好O(1),最坏O(|V|);

时间复杂度：O(|V|+|E|);

时间复杂度 = 访问各结点所需时间+探索各条边所需时间

对于无向图进行BFS/DFS遍历：调用BFS/DFS函数的次数 = 连通分量数；对于连通图只需要调用1次BFS/DFS函数。

对于有向图进行BFS/DFS遍历：调用BFS/DFS函数的次数要具体问题具体分析；若起始顶点到其他顶点都有路径，只需要调用1次BFS/DFS函数；对于强连通图，从任一顶点出发都只需要调用1次BFS/DFS函数。

三.邻接矩阵存储图进行广度优先搜索和深度优先搜索

权值设置的都为1，可自行设置

圆圈内为顶点的值，上面为其序号；一该图为例进行邻接矩阵存储 

1.先创造邻接矩阵存储图

1.1图的结构体构造

typedef char VerTexType;//顶点的数据类型
typedef int EdgeType;//带权图中边上权值数据类型
typedef struct
{
  VerTexType Vex[MaxVertexNum];//顶点表
  EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表
  int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph;

1.2无向图邻接矩阵构造

//1.无向网的建立
void CreatMGraph(MGraph &G)
{
  printf("请输入图的顶点数和边数：");
  int m,n;
  scanf_s("%d %d",&m,&n);
  G.vexnum = m;
  G.arcnum = n;
  char val;
  for(int i = 0; i < G.vexnum; ++i)
  {
	  printf("第%d个顶点值为:",i);
	  scanf_s("%*c%c",&val);
	  G.Vex[i] = val;
  }
  for(int i = 0; i < G.vexnum; ++i)
  { 
	  for(int j = 0; j < G.vexnum; ++j)
	  {
		  G.Edge[i][j] = Max;
	  }
  }
  int i,j,w;
  for(int k = 0; k < G.arcnum; ++k)
  {
	printf("请输入顶点和权值\n");
	scanf_s("%d %d %d",&i,&j,&w);
    printf("(Vi,Vj)下表为(%d,%d)的权值为%d:\n",i,j,w);
	G.Edge[i][j] = w;
	G.Edge[j][i] = G.Edge[i][j];
  }

}

1.3FirstNeighbor函数构造

//2.求图G中顶点编号x的第一个邻接点
int FirstNeighbor(MGraph G, int x)
{

	for(int j = 0; j < G.vexnum; ++j)
	{
		if(G.Edge[x][j] != -1)
			return j;
	}
	return -1;
}

1.4NextNeighbor函数构造

//3.假设图G中顶点y是顶点x的一个邻近点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
int NextNeighbor(MGraph G, int x, int y)
{
  for(int j = y+1; j < G.vexnum; ++j)
  {
	  if(G.Edge[x][j] != -1)
		  return j;
  }
  return -1;
}

2.广度优先搜索的构造辅助队列

2.1辅助队列结构体

//定义队列的结构体
typedef struct LinkNode
{
  int data;//队列的数据域
  LinkNode *next;//指针域
}LinkNode;

typedef struct
{
  LinkNode *front;//队列对头指针
  LinkNode *rear;//队列队尾指针
}LinkQueue;

2.1初始化队列

//1.初始化
void InitQueue(LinkQueue &Q)
{
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q.rear->next = NULL;
}

2.2入队函数

//2.入队
void EnQueue(LinkQueue &Q, int x)
{
  LinkNode *p = (LinkNode*)malloc(sizeof(LinkNode));
  if(p == NULL)
  {
    printf("动态内存分配失败！");
	exit(-1);
  }
  p->data = x;
  //通过尾插法入队
  p->next = NULL;
  Q.rear->next = p;
  Q.rear = p;
}

2.3出队函数

//3.出队
int DeQueue(LinkQueue &Q,int &x)
{
  if(IsEmpty(Q))
	  return -1;
  else
  {
	  LinkNode *p = Q.front->next;
	  x = p->data;
	  Q.front->next = p->next;
	  if(Q.rear == p)
		  Q.rear = Q.front;
	  free(p);
  }
  return x;
}

2.4判断队列为空

//4.判断空
bool IsEmpty(LinkQueue Q)
{
	if(Q.front == Q.rear)
	{
	  return true;
	}
	else
	{
	  return false;
	}
}

3.广度优先搜索

权值设置的都为1，可自行设置

以该例子进行邻接表存储 

3.1广度优先遍历图G

//广度优先搜索
//1.对图G进行广度优先遍历
void BFSTraverse(MGraph G)
{
	int *visited;
	visited = (int *)malloc(sizeof(int)*G.vexnum);
	for(int i = 0; i < G.vexnum; ++i)
	{
	  visited[i] = 0;
	}
	for(int i = 0; i < G.vexnum; ++i)
	{//从0号顶点遍历
	  if(!visited[i])//如果visited[i] == 0表示该点还未被访问
		  BFS(G,visited,i);//每个连通分量调用一次BFS函数
	}
	printf("\n");
}

3.2广度优先遍历

//2.广度优先遍历
void BFS(MGraph G,int *visited,int v)
{
	printf("%c ",G.Vex[v]);//打印输出初始顶点
	visited[v] = 1;//将打印过的顶点标记为true
	LinkQueue Q;
	InitQueue(Q);
	EnQueue(Q,v);//将顶点入队
	while(!IsEmpty(Q))//判断队列是否为空
	{
	  int u = DeQueue(Q,v);//不为空则出队
	  for(int w = FirstNeighbor(G,u); w >= 0; w = NextNeighbor(G,u,w))
	  {//检查序号v所有的邻接点
	    if(!visited[w])//如果序号为w的顶点还未被访问
		{
			printf("%c ",G.Vex[w]);
			visited[w] = 1;//将打印输出顶点的序号标记为1表示已经被访问
			EnQueue(Q,w);//将顶点入队
		}
	  }
	}

}

4.深度优先搜索

4.1深度优先遍历图G

//1.对图G进行深度优先遍历
void DFSTraverse(MGraph G)
{
	int *visited = (int *)malloc(sizeof(int)*G.vexnum);//创造标记组
	for(int i = 0; i < G.vexnum; ++i)
	{
	  visited[i] = 0;//等于0表示还未被访问，以免因为图中环的存在导致重复遍历
	}
	for(int i = 0; i < G.vexnum; ++i)//如果图中不止一个连通分量，可以将其全部遍历输出
	{
	  if(!visited[i])
		  DFS(G,visited,i);
	}
}

4.2深度优先遍历

//2.深度优先遍历
void DFS(MGraph G, int *visited, int v)
{
	printf("%c ",G.Vex[v]);//遍历输出顶点的值
	visited[v] = 1;//将该顶点的标记值改为1，表示该顶点已经被访问
	for(int w = FirstNeighbor(G,v); w >= 0; w = NextNeighbor(G,v,w))
	{
	  if(!visited[w])
		  DFS(G,visited,w);
	}

}

5.运行结果

四.无向图G邻接矩阵存储广度优先搜索和深度优先搜索

1.先创造邻接表 

1.1邻接表的结构体

#define MaxVertexNum 10//图中顶点数目的最大值
typedef char VertexType;
//邻接表的结构体
//定义边表结点
typedef struct ArcNode
{
  int adjvex;//该弧所指向的顶点的位置
  struct ArcNode *next;//指向下一条弧的指针
  int info;//网的边权值
}ArcNode;

//顶点表信息，用顺序结构存储顶点表的信息
typedef struct VNode
{
  VertexType data;//顶点信息
  ArcNode *first;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];

//邻接表
typedef struct
{
  AdjList vertices;//邻接表
  int vexnum,arcnum;//图的顶点数和弧数
}ALGraph;//ALGraph是以邻接表存储图的类型

 1.2创造邻接表

//创建邻接表
void CreatALGraph(ALGraph &G)
{
  printf("请输入图G的顶点数和边数：\n");
  scanf_s("%d %d",&(G.vexnum),&(G.arcnum));
  //输入结点
  char val;
  for(int i = 0; i < G.vexnum; ++i)
  {
    printf("请输入第%d个结点的值：\n",i);
	scanf_s("%*c%c",&val);
	G.vertices[i].data = val;
	G.vertices[i].first = NULL;//最开始令每个顶点的第一条依附顶点的弧的指针为空
  }
  //输入边
  int i,j,w;
  for(int k = 0; k < G.arcnum; ++k)
  {
	ArcNode *m = (ArcNode*)malloc(sizeof(ArcNode));
	printf("请输入顶点的序号和权值\n");
	scanf_s("%d %d %d",&i,&j,&w);
    printf("(Vi,Vj)下表为(%d,%d)的权值为%d:\n",i,j,w);
	m->adjvex = j;
	m->info = w;
	//用头插法创造边表
	m->next = G.vertices[i].first;
	G.vertices[i].first = m;
	//这个是无向图，而且令k<G.arcnum，因为一个弧对应两个顶点，两个顶点都是顶点表中的，所以要同时将两个顶点表的边表都弄好
	ArcNode *n = (ArcNode*)malloc(sizeof(ArcNode));
	n->adjvex = i;
	n->info = w;
	//用头插法创建边表
	n->next = G.vertices[j].first;
	G.vertices[j].first = n;
  }

}

1.3FirstNeighbor函数

//求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1.
int FirstNeighbor(ALGraph G, int x)
{
	if(x >= G.vexnum)
	{
	  return -1;
	}
	else if(G.vertices[x].first == NULL)
	{	
	  return -1;
	}
	else
	{
		ArcNode *p = G.vertices[x].first;//指向图G的顶点x的邻接点的指针
		int i = p->adjvex;//邻接点的序号
		return i;
	}

}

1.4NextNeighbor函数

//假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
int NextNeighbor(ALGraph G,int x,int y)
{
	ArcNode *p = G.vertices[x].first;
	while(p->adjvex != y)
	{
		p = p->next;
	}
	if(p->next == NULL)
	{
		return -1;
	}
	else
	{
		p = p->next;
		int j = p->adjvex;
		return j;
	}
}

2.队列和上面一致，这里就不在展示代码

3.广度优先搜素和深度优先搜素和上面也是一致的，结尾有完整代码可以观看

4.运行结果：

 五.完整程序

1.以邻接矩阵存储进行广度优先和深度优先搜索

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define Max -1//这里以-1代表最大值
#define MaxVertexNum 15


typedef char VerTexType;//顶点的数据类型
typedef int EdgeType;//带权图中边上权值数据类型
typedef struct
{
  VerTexType Vex[MaxVertexNum];//顶点表
  EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表
  int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph;


//定义队列的结构体
typedef struct LinkNode
{
  int data;//队列的数据域
  LinkNode *next;//指针域
}LinkNode;

typedef struct
{
  LinkNode *front;//队列对头指针
  LinkNode *rear;//队列队尾指针
}LinkQueue;



//图G的函数说明
void CreatMGraph(MGraph &G);
int FirstNeighbor(MGraph G, int x);
int NextNeighbor(MGraph G, int x, int y);


//队列的函数说明
void InitQueue(LinkQueue &Q);
void EnQueue(LinkQueue &Q, int x);
int DeQueue(LinkQueue &Q,int &x);
bool IsEmpty(LinkQueue Q);


//广度优先遍历的函数说明
void BFSTraverse(MGraph G);
void BFS(MGraph G,int *visited,int v);

//深度优先遍历
void DFSTraverse(MGraph G);
void DFS(MGraph G, int *visited, int v);


int main(void)
{
  MGraph G;//定义变量图
  CreatMGraph(G);
  printf("广度优先遍历的结果:\n");
  BFSTraverse(G);
  printf("深度优先遍历的结果：\n");
  DFSTraverse(G);
  return 0;
}


//图G函数
//1.无向网的建立
void CreatMGraph(MGraph &G)
{
  printf("请输入图的顶点数和边数：");
  int m,n;
  scanf_s("%d %d",&m,&n);
  G.vexnum = m;
  G.arcnum = n;
  char val;
  for(int i = 0; i < G.vexnum; ++i)
  {
	  printf("第%d个顶点值为:",i);
	  scanf_s("%*c%c",&val);
	  G.Vex[i] = val;
  }
  for(int i = 0; i < G.vexnum; ++i)
  { 
	  for(int j = 0; j < G.vexnum; ++j)
	  {
		  G.Edge[i][j] = Max;
	  }
  }
  int i,j,w;
  for(int k = 0; k < G.arcnum; ++k)
  {
	printf("请输入顶点和权值\n");
	scanf_s("%d %d %d",&i,&j,&w);
    printf("(Vi,Vj)下表为(%d,%d)的权值为%d:\n",i,j,w);
	G.Edge[i][j] = w;
	G.Edge[j][i] = G.Edge[i][j];
  }

}

//2.求图G中顶点编号x的第一个邻接点
int FirstNeighbor(MGraph G, int x)
{

	for(int j = 0; j < G.vexnum; ++j)
	{
		if(G.Edge[x][j] != -1)
			return j;
	}
	return -1;
}

//3.假设图G中顶点y是顶点x的一个邻近点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
int NextNeighbor(MGraph G, int x, int y)
{
  for(int j = y+1; j < G.vexnum; ++j)
  {
	  if(G.Edge[x][j] != -1)
		  return j;
  }
  return -1;
}


//队列的函数

//1.初始化
void InitQueue(LinkQueue &Q)
{
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q.rear->next = NULL;
}

//2.入队
void EnQueue(LinkQueue &Q, int x)
{
  LinkNode *p = (LinkNode*)malloc(sizeof(LinkNode));
  if(p == NULL)
  {
    printf("动态内存分配失败！");
	exit(-1);
  }
  p->data = x;
  //通过尾插法入队
  p->next = NULL;
  Q.rear->next = p;
  Q.rear = p;
}

//3.出队
int DeQueue(LinkQueue &Q,int &x)
{
  if(IsEmpty(Q))
	  return -1;
  else
  {
	  LinkNode *p = Q.front->next;
	  x = p->data;
	  Q.front->next = p->next;
	  if(Q.rear == p)
		  Q.rear = Q.front;
	  free(p);
  }
  return x;
}

//4.判断空
bool IsEmpty(LinkQueue Q)
{
	if(Q.front == Q.rear)
	{
	  return true;
	}
	else
	{
	  return false;
	}
}

//广度优先搜索
//1.对图G进行广度优先遍历
void BFSTraverse(MGraph G)
{
	int *visited;
	visited = (int *)malloc(sizeof(int)*G.vexnum);
	for(int i = 0; i < G.vexnum; ++i)
	{
	  visited[i] = 0;
	}
	for(int i = 0; i < G.vexnum; ++i)
	{//从0号顶点遍历
	  if(!visited[i])//如果visited[i] == 0表示该点还未被访问
		  BFS(G,visited,i);//每个连通分量调用一次BFS函数
	}
	printf("\n");
}

//2.广度优先遍历
void BFS(MGraph G,int *visited,int v)
{
	printf("%c ",G.Vex[v]);//打印输出初始顶点
	visited[v] = 1;//将打印过的顶点标记为true
	LinkQueue Q;
	InitQueue(Q);
	EnQueue(Q,v);//将顶点入队
	while(!IsEmpty(Q))//判断队列是否为空
	{
	  int u = DeQueue(Q,v);//不为空则出队
	  for(int w = FirstNeighbor(G,u); w >= 0; w = NextNeighbor(G,u,w))
	  {//检查序号v所有的邻接点
	    if(!visited[w])//如果序号为w的顶点还未被访问
		{
			printf("%c ",G.Vex[w]);
			visited[w] = 1;//将打印输出顶点的序号标记为1表示已经被访问
			EnQueue(Q,w);//将顶点入队
		}
	  }
	}

}


//深度优先遍历，类似于树的先序遍历

//1.对图G进行深度优先遍历
void DFSTraverse(MGraph G)
{
	int *visited = (int *)malloc(sizeof(int)*G.vexnum);//创造标记组
	for(int i = 0; i < G.vexnum; ++i)
	{
	  visited[i] = 0;//等于0表示还未被访问，以免因为图中环的存在导致重复遍历
	}
	for(int i = 0; i < G.vexnum; ++i)//如果图中不止一个连通分量，可以将其全部遍历输出
	{
	  if(!visited[i])
		  DFS(G,visited,i);
	}
}

//2.深度优先遍历
void DFS(MGraph G, int *visited, int v)
{
	printf("%c ",G.Vex[v]);//遍历输出顶点的值
	visited[v] = 1;//将该顶点的标记值改为1，表示该顶点已经被访问
	for(int w = FirstNeighbor(G,v); w >= 0; w = NextNeighbor(G,v,w))
	{
	  if(!visited[w])
		  DFS(G,visited,w);
	}

}

2.邻接表存储进行广度优先和深度优先搜索

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

#define MaxVertexNum 10//图中顶点数目的最大值
typedef char VertexType;
//邻接表的结构体
//定义边表结点
typedef struct ArcNode
{
  int adjvex;//该弧所指向的顶点的位置
  struct ArcNode *next;//指向下一条弧的指针
  int info;//网的边权值
}ArcNode;

//顶点表信息，用顺序结构存储顶点表的信息
typedef struct VNode
{
  VertexType data;//顶点信息
  ArcNode *first;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];

//邻接表
typedef struct
{
  AdjList vertices;//邻接表
  int vexnum,arcnum;//图的顶点数和弧数
}ALGraph;//ALGraph是以邻接表存储图的类型


//定义队列的结构体
typedef struct LinkNode
{
  int data;//队列的数据域
  LinkNode *next;//指针域
}LinkNode;

typedef struct
{
  LinkNode *front;//队列对头指针
  LinkNode *rear;//队列队尾指针
}LinkQueue;



//图的函数说明
void CreatALGraph(ALGraph &G);
int FirstNeighbor(ALGraph G, int x);
int NextNeighbor(ALGraph G,int x,int y);


//队列的函数说明
void InitQueue(LinkQueue &Q);
void EnQueue(LinkQueue &Q, int x);
int DeQueue(LinkQueue &Q,int &x);
bool IsEmpty(LinkQueue Q);


//广度优先遍历函数说明
void BFSTraverse(ALGraph G);
void BFS(ALGraph G, int *visited, int v);

//深度优先遍历函数说明
void DFSTraverse(ALGraph G);
void DFS(ALGraph G, int *visited, int v);


int main(void)
{
  ALGraph G;
  CreatALGraph(G);//以邻接表法存储图
  printf("广度优先遍历结果：\n");
  BFSTraverse(G);
  printf("深度优先遍历结果：\n");
  DFSTraverse(G);
  return 0;
}


//创建邻接表
void CreatALGraph(ALGraph &G)
{
  printf("请输入图G的顶点数和边数：\n");
  scanf_s("%d %d",&(G.vexnum),&(G.arcnum));
  //输入结点
  char val;
  for(int i = 0; i < G.vexnum; ++i)
  {
    printf("请输入第%d个结点的值：\n",i);
	scanf_s("%*c%c",&val);
	G.vertices[i].data = val;
	G.vertices[i].first = NULL;//最开始令每个顶点的第一条依附顶点的弧的指针为空
  }
  //输入边
  int i,j,w;
  for(int k = 0; k < G.arcnum; ++k)
  {
	ArcNode *m = (ArcNode*)malloc(sizeof(ArcNode));
	printf("请输入顶点的序号和权值\n");
	scanf_s("%d %d %d",&i,&j,&w);
    printf("(Vi,Vj)下表为(%d,%d)的权值为%d:\n",i,j,w);
	m->adjvex = j;
	m->info = w;
	//用头插法创造边表
	m->next = G.vertices[i].first;
	G.vertices[i].first = m;
	//这个是无向图，而且令k<G.arcnum，因为一个弧对应两个顶点，两个顶点都是顶点表中的，所以要同时将两个顶点表的边表都弄好
	ArcNode *n = (ArcNode*)malloc(sizeof(ArcNode));
	n->adjvex = i;
	n->info = w;
	//用头插法创建边表
	n->next = G.vertices[j].first;
	G.vertices[j].first = n;
  }

}

//求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1.
int FirstNeighbor(ALGraph G, int x)
{
	if(x >= G.vexnum)
	{
	  return -1;
	}
	else if(G.vertices[x].first == NULL)
	{	
	  return -1;
	}
	else
	{
		ArcNode *p = G.vertices[x].first;//指向图G的顶点x的邻接点的指针
		int i = p->adjvex;//邻接点的序号
		return i;
	}

}

//假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
int NextNeighbor(ALGraph G,int x,int y)
{
	ArcNode *p = G.vertices[x].first;
	while(p->adjvex != y)
	{
		p = p->next;
	}
	if(p->next == NULL)
	{
		return -1;
	}
	else
	{
		p = p->next;
		int j = p->adjvex;
		return j;
	}
}


//队列的函数

//1.初始化
void InitQueue(LinkQueue &Q)
{
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q.rear->next = NULL;
}

//2.入队
void EnQueue(LinkQueue &Q, int x)
{
  LinkNode *p = (LinkNode*)malloc(sizeof(LinkNode));
  if(p == NULL)
  {
    printf("动态内存分配失败！");
	exit(-1);
  }
  p->data = x;
  //通过尾插法入队
  p->next = NULL;
  Q.rear->next = p;
  Q.rear = p;
}

//3.出队
int DeQueue(LinkQueue &Q,int &x)
{
  if(IsEmpty(Q))
	  return -1;
  else
  {
	  LinkNode *p = Q.front->next;
	  x = p->data;
	  Q.front->next = p->next;
	  if(Q.rear == p)
		  Q.rear = Q.front;
	  free(p);
  }
  return x;
}

//4.判断空
bool IsEmpty(LinkQueue Q)
{
	if(Q.front == Q.rear)
	{
	  return true;
	}
	else
	{
	  return false;
	}
}


//广度优先遍历
//1.对图G进行广度优先遍历
void BFSTraverse(ALGraph G)
{
	int *visited = (int *)malloc(sizeof(int)*G.vexnum);
	for(int i = 0; i < G.vexnum; ++i)
	{
	  visited[i] = 0;//标记数组，等于0表示顶点还未被访问
	}
	for(int i = 0; i < G.vexnum; ++i)
	{
	  if(visited[i] == 0)
	     BFS(G,visited,i);
	}
	printf("\n");
}

//2.广度优先遍历
void BFS(ALGraph G, int *visited, int v)
{
	printf("%c ",G.vertices[v].data);
	visited[v] = 1;//改成1表示该顶点已经被访问
	LinkQueue Q;//定义队列变量
	InitQueue(Q);//初始化队列
	EnQueue(Q,v);//入队
	while(!IsEmpty(Q))
	{
	  DeQueue(Q,v);//出队
	  for(int w = FirstNeighbor(G,v); w >= 0; w = NextNeighbor(G,v,w))
	  {
	    if(visited[w] == 0)
		{
			printf("%c ",G.vertices[w].data);//将第一个邻接点打印输出
			visited[w] = 1;//将该顶点标记为已经访问
			EnQueue(Q,w);//将顶点入队
		}
	  }
	}
}


//1.对图G进行深度优先遍历
void DFSTraverse(ALGraph G)
{
  	int *visited = (int *)malloc(sizeof(int)*G.vexnum);
	for(int i = 0; i < G.vexnum; ++i)
	{
	  visited[i] = 0;//标记数组，等于0表示顶点还未被访问
	}
	for(int i = 0; i < G.vexnum; ++i)
	{
      if(visited[i] == 0)
	     DFS(G,visited,i);
	}
	printf("\n");
}

//2.深度优先遍历
void DFS(ALGraph G, int *visited, int v)
{
	printf("%c ",G.vertices[v].data);
	visited[v] = 1;
	for(int w = FirstNeighbor(G,v); w >= 0; w = NextNeighbor(G,v,w))
	{
		if(visited[w] == 0)
		{
			visited[w] = 1;
			DFS(G,visited,w);//进行递归
		}
	}
}


http://www.niftyadmin.cn/n/474129.html

相关文章

项目引入 mqtt 报错 Uncaught ReferenceError: Buffer is not defined

项目引入 mqtt 报错 Uncaught ReferenceError: Buffer is not defined

项目引入 mqtt 报错 Uncaught ReferenceError: Buffer is not defined 最近在做一个 vite4.x react18 的项目,需要引入 mqtt.js , 基操直接引入 import mqtt from mqtt结果浏览器直接报错 Uncaught ReferenceError: Buffer is not defined. 首先想到的是不是 mqtt.js 库不能…
阅读更多...
kubernetes核心概念 controller

kubernetes核心概念 controller

kubernetes核心概念 Controller 一、pod控制器controller 1.1 Controller作用及分类 controller用于控制pod 参考: https://kubernetes.io/zh/docs/concepts/workloads/controllers/ 控制器主要分为: Deployments 部署无状态应用&#xff0c;控制pod升级,回退ReplicaSet 副…
阅读更多...
什么是微服务自动化测试？

什么是微服务自动化测试？

什么是微服务&#xff1f; 微服务 - 也称为微服务架构 - 是一种构建方式&#xff0c;它将应用程序构建为松散耦合服务的集合&#xff0c;具有完整的业务功能。微服务架构允许连续交付/部署大型复杂应用程序。本文将概述自动微服务测试工具和最佳实践。 它还使组织能够发展其技…
阅读更多...
mac docker desktop 无法docker login

mac docker desktop 无法docker login

mac docker desktop 无法docker login &#xff0c;报错 Error saving credentials: error storing credentials - err: exit status 1, out: Post "http://ipc/registry/credstore-updated": context deadline exceeded (Client.Timeout exceeded while awaiting h…
阅读更多...
018、数据库管理之TiDB升级

018、数据库管理之TiDB升级

升级 使用TiUP进行补丁升级(HotFix)版本升级流程升级准备-更新TiUP升级准备- 编辑TiUP Cluster升级准备- 集群监控状态检查升级TiDB 集群验证TiDB集群升级结果升级常见问题 使用TiUP进行补丁升级(HotFix) -R &#xff1a; 所有 -N : 指定的节点 升级集群上的所有TiDB实例&…
阅读更多...
颜色聚合向量 Color Co-ccurrence Vector 介绍以及MATLAB代码实现

颜色聚合向量 Color Co-ccurrence Vector 介绍以及MATLAB代码实现

这件事情的起因是我想复习一下我在亚太杯数学建模当中使用过的CCV这种方法&#xff0c;但是CSDN平台上找了半天都没有&#xff0c;所以后来决定Google一下&#xff0c;终于找到了&#xff0c;甚至还有实现的代码&#xff0c;因此放上来。原文见Dr. Mahmoud Attia的博客。 一、…
阅读更多...
java Predicate接口

java Predicate接口

Predicate是Java中的一个函数式接口,它代表一个判断逻辑,接收一个输入参数,返回一个布尔值。 接口定义 FunctionalInterface public interface Predicate<T> {boolean test(T t); } 它接收泛型T的输入,返回true或false。 Predicate接口通常用来: 1. 过滤集合中的元…
阅读更多...
求职——star method题库

求职——star method题库

这两天读了另维的《每一天梦想练习》&#xff0c;提到了星星四步法&#xff0c;以及作者给出了STAR Method题库 参考&#xff1a; 微信推送 - STAR Method题库 https://mp.weixin.qq.com/s/64UUvLJxGDNBuj7j-Iqkow 1. 什么是STAR Method STAR方法是一种结构化的方式&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023