精华内容
下载资源
问答
  • 数据结构——无向图创建邻接表以及深度遍历广度遍历一、邻接表概念二、创建邻接表 一、邻接表概念 在无向图中,顶点存储在顶点表中,以一个顶点为标记,指向边链表,两者组合在一起,称为 邻接表 对无向图每...

    一、邻接表概念

    在无向图中,顶点存储在顶点表中,以一个顶点为标记,指向边链表,两者组合在一起,称为 邻接表

    1. 对无向图的每个顶点vi建立一个单链表,第i个单链表中的结点表示依附于顶点vi的边(对于有向图则是以顶点vi为尾的弧)。这个单链表就称为顶点vi的边表(对于有向图则称为出边表)
    2. 边表的头指针和顶点的数据信息采用顺序存储(称为顶点表)
    3. 邻接表中存在两种结点:顶点表结点和边表结点
    4. 顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc)构成
    5. 边表(邻接表)结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc)构成

    如图:

    在这里插入图片描述

    在这里插入图片描述

    二、邻接表实现

    具体样例

    在这里插入图片描述

    基本每一步,都有注释!!可认真看并理解!!!

    (1)准备前提——结构体定义

    #define MAXSIZE 100
    
    //深度遍历标记数组 
    int DfsVist[MAXSIZE]; 
    //广度遍历标记数组 
    int BfsVist[MAXSIZE];
    
    //	边链表 
    typedef struct EdgeLink{
    	
    	int Local;					//	存放该顶点对应边链表中数据 						 
    	
    	struct EdgeLink *next;		//	边链表节点指针  
    	
    }Edge,*ELINK;
    
    //	顶点表 
    typedef struct VertexLink{
    	
    	int Vertex;					//	存放一条边链表对应的顶点 
    	ELINK FirstNode;			//	指向该顶点对应边链表的头节点 
    	
    }Vertex[MAXSIZE],*VLINK;
    
    //	存放顶点和边,指向顶点表结构体数组 
    typedef struct MyGraph{
    	
    	int Vnum;	//	存放顶点数 
    	int Enum;	//	存放边数 
    	
    	Vertex List;	//	边链表对应的顶点表中顶点结构体 
    	
    }MyGraph;
    
    

    (2)创建边链表

    //	创建边链表
    void CreateLink(MyGraph *T)
    {
    	int i,j;
    	int v1,v2;
    	ELINK p;		//	边链表指针 
    	ELINK q;
    	
    	printf("请输入顶点数和边数(空格隔开):\n");
    	
    	scanf("%d%d",&(T->Vnum),&(T->Enum));
    	
    	
    	//	初始化顶点表结构体数组 
    	for(i=0;i<T->Vnum;i++)
    	{
    		printf("请输入第%d个顶点的信息:\n",i+1);
    		
    		scanf("%d",&(T->List[i].Vertex));		//	存放顶点在顶点表中 
    		
    		T->List[i].FirstNode = NULL; 		//	让每个顶点表第一个指向边链表的指针为NULL 
    	}
    	
    	//	打印顶点坐标和顶点表中顶点数据 
    	printf("---------------------------\n"); 
    	for(i=0;i<T->Vnum;i++)
    	{
    		printf("顶点下标为:%d   顶点数据为: %d\n",i,T->List[i].Vertex); 	
    	}
    	printf("---------------------------\n");
    	
    	//	插入边链表数据	
    	for(i=0;i<T->Enum;i++)
    	{
    		//	因为顶点表为顺序表,所以要按顶点顺序输入相连边 
    		printf("请输入两个连接顶点下标(空格隔开):\n");
    		
    		scanf("%d%d",&v1,&v2);
    		getchar(); 
    		
    		q = (ELINK)malloc(sizeof(Edge));	//	创建边链表节点,分配内存 
    				
    		q->Local = v2;	//	记录与该顶点连接边的顶点坐标
    				
    		q->next = NULL;						//	让尾巴指向NULL 
    				
    		if(!T->List[v1].FirstNode){	//	判断是否为这个顶点第一个指向的数据 
    					
    			T->List[v1].FirstNode = q;
    					
    		}else{
    				//	这个顶点已经指向了一条边,以这条边为头节点,尾插法 
    			p = T->List[v1].FirstNode;	//	临时存放头节点 
    			while(p->next)	//	让节点指针遍历到尾巴上 
    			{
    				p = p->next;
    			}
    			p->next = q;	//	让新插的节点连接到之前边节点的尾巴上 
    		}
    			
    		q = (ELINK)malloc(sizeof(Edge));	//	创建边链表节点,分配内存 
    				
    		q->Local = v1;	//	记录与该顶点连接边的顶点坐标
    			
    		q->next = NULL;						//	让尾巴指向NULL 
    				
    		if(!T->List[v2].FirstNode){	//	判断是否为这个顶点第一个指向的数据 
    					
    			T->List[v2].FirstNode = q;
    					
    		}else{
    					//	这个顶点已经指向了一条边,以这条边为头节点,尾插法 
    			p = T->List[v2].FirstNode;	//	临时存放头节点 
    			while(p->next)	//	让节点指针遍历到尾巴上 
    			{
    				p = p->next;
    			}
    			p->next = q;	//	让新插的节点连接到之前边节点的尾巴上 
    		}
    			
    	} 
    	
    }
    

    (3)打印边链表

    //	打印邻接表 
    void PrintLink(MyGraph *S) 
    {
    	MyGraph *T = S;
    	ELINK Q;			//	防止边链表指针指到NULL ,用临时指针代替遍历打印 
    		
    	int i;
    	printf("打印邻接表结果如下:\n");
    	for(i=0;i<T->Vnum;i++)
    	{
    		Q = T->List[i].FirstNode;	//	接受每个顶点指向对应边链表的头节点指针 
    		printf("%d--->",i);
    		
    		while(1)
    		{
    			if(Q == NULL)	//	指针指到尾巴 NULL
    			{
    				putchar('\n');
    				break;
    			}
    			printf("------->%3d",Q->Local);
    			
    			Q = Q->next;	
    		}
    	}
    	putchar('\n');
    }
    
    

    (4)深度优先遍历

    //*****************	深度优先遍历算法—邻接表 *****************//
    void DFS_Link(MyGraph *T,int n)
    {	
    	int i,j;
    	ELINK q;	//	指向边链表节点指针 
    	
    	if(n<0 || n>=T->Vnum)
    	{
    		printf("输入有误\n");
    		return;	
    	}
    		DfsVist[n] = 1;		//	遍历一个顶点,做下标记 1  
    
    		printf(" %d",T->List[n].Vertex);
    		
    		q = T->List[n].FirstNode;	//q指向下标为i所对顶点 对应的边链表的第一个边结点	
    		
    		while(q!=NULL)	
    		{	
    			if(DfsVist[q->Local]!=1)
    			{
    			
    				j = q->Local;
    				DFS_Link(T,j);
    			} 
    			
    			q = q->next;
    		}
    	
    	
    	 
    } 
    //	初始化深度遍历—邻接表 
    void Init_DFSLINK(MyGraph *Q)
    {
    	int i;
    	for(i=0;i<Q->Vnum;i++)
    	{
    		DfsVist[i] = 0;
    	}
    		
    	for(i=0;i<Q->Vnum;i++)
    	{
    		if(!DfsVist[i])
    		{
    		 DFS_Link(Q,i);	//	此顶点没有被标记,开始递归遍历
    		}
    	}
    	putchar('\n'); 
    	
    }
    
    

    (5)广度优先搜索

    //	广度遍历 
    void BFS(MyGraph *S,int t)
    {
    	ELINK P; 			//	指向顶点所对应的边链表中 
    	
    	int i;
    	int v;		//	用来接收边链表对应的顶点
    	
    	
    	//	创建一个数组队列 
    	int Queue[MAXSIZE];
    	int front = 0;			//	队头 
    	int rear = 0;			//	队尾 
    		
    	printf("%d ",S->List[t].Vertex);	//	输出当前遍历边链表的顶点 
    	BfsVist[t] = 1;		//	将该顶点作标记
    	
    	rear = (rear+1)%MAXSIZE;	//	入队一个让队尾指向后移一位
    	Queue[rear] = t;	 		//	将该顶点入队 
    
    	while(front != rear)	//	若front == rear,表明这个顶点在边链表上连接的顶点已经遍历完毕 
    	{
    		front = (front+1)%MAXSIZE;		//	出队 
    	
    		v = Queue[front];			//	得到此时遍历到顶点坐标 
    		
    		P = S->List[v].FirstNode;	//	遍历当前顶点指向边链表中连接的其他顶点
    									//	也就是换个顶点的边链表继续遍历查找剩余顶点 
    		while(P!=NULL)
    		{
    			
    			if(BfsVist[P->Local] == 0)
    			{			
    				printf("%d ",P->Local+1);	//	输出连接边顶点 
    				
    				BfsVist[P->Local] = 1;		//	作标记,表示这个顶点已经搜索过 
    				
    				rear = (rear+1)%MAXSIZE;		//	将该下标入队 
    				
    				Queue[rear] = P->Local;	//	把遍历到新的边链表对应的顶点坐标入队 
    			}
    			
    			P = P->next;	//	遍历这个顶点的边链表 
    		}	
    	} 
    } 
    
    //	BFS广度遍历初始化
    void Init_BFS(MyGraph *S)
    {
    	int i;
    	
    	for(i=0;i<S->Vnum;i++)
    	{
    		BfsVist[i] = 0;	//	初始化标记符 
    	}
    	
    	for(i=0;i<S->Vnum;i++)
    	{
    		if(BfsVist[i]==0)
    			BFS(S,i);
    	}
    	
    } 
    

    (6)全部代码

    #include<stdio.h>
    #include<stdlib.h>
    
    #define MAXSIZE 100
    
    //深度遍历标记数组 
    int DfsVist[MAXSIZE]; 
    //广度遍历标记数组 
    int BfsVist[MAXSIZE];
    
    //	边链表 
    typedef struct EdgeLink{
    	
    	int Local;					//	存放该顶点对应边链表中数据 						 
    	
    	struct EdgeLink *next;		//	边链表节点指针  
    	
    }Edge,*ELINK;
    
    //	顶点表 
    typedef struct VertexLink{
    	
    	int Vertex;					//	存放一条边链表对应的顶点 
    	ELINK FirstNode;			//	指向该顶点对应边链表的头节点 
    	
    }Vertex[MAXSIZE],*VLINK;
    
    //	存放顶点和边,指向顶点表结构体数组 
    typedef struct MyGraph{
    	
    	int Vnum;	//	存放顶点数 
    	int Enum;	//	存放边数 
    	
    	Vertex List;	//	边链表对应的顶点表中顶点结构体 
    	
    }MyGraph;
    
    //	创建边链表
    void CreateLink(MyGraph *T)
    {
    	int i,j;
    	int v1,v2;
    	ELINK p;		//	边链表指针 
    	ELINK q;
    	
    	printf("请输入顶点数和边数(空格隔开):\n");
    	
    	scanf("%d%d",&(T->Vnum),&(T->Enum));
    	
    	
    	//	初始化顶点表结构体数组 
    	for(i=0;i<T->Vnum;i++)
    	{
    		printf("请输入第%d个顶点的信息:\n",i+1);
    		
    		scanf("%d",&(T->List[i].Vertex));		//	存放顶点在顶点表中 
    		
    		T->List[i].FirstNode = NULL; 		//	让每个顶点表第一个指向边链表的指针为NULL 
    	}
    	
    	//	打印顶点坐标和顶点表中顶点数据 
    	printf("---------------------------\n"); 
    	for(i=0;i<T->Vnum;i++)
    	{
    		printf("顶点下标为:%d   顶点数据为: %d\n",i,T->List[i].Vertex); 	
    	}
    	printf("---------------------------\n");
    	
    	//	插入边链表数据	
    	for(i=0;i<T->Enum;i++)
    	{
    		//	因为顶点表为顺序表,所以要按顶点顺序输入相连边 
    		printf("请输入两个连接顶点下标(空格隔开):\n");
    		
    		scanf("%d%d",&v1,&v2);
    		getchar(); 
    		
    		q = (ELINK)malloc(sizeof(Edge));	//	创建边链表节点,分配内存 
    				
    		q->Local = v2;	//	记录与该顶点连接边的顶点坐标
    				
    		q->next = NULL;						//	让尾巴指向NULL 
    				
    		if(!T->List[v1].FirstNode){	//	判断是否为这个顶点第一个指向的数据 
    					
    			T->List[v1].FirstNode = q;
    					
    		}else{
    				//	这个顶点已经指向了一条边,以这条边为头节点,尾插法 
    			p = T->List[v1].FirstNode;	//	临时存放头节点 
    			while(p->next)	//	让节点指针遍历到尾巴上 
    			{
    				p = p->next;
    			}
    			p->next = q;	//	让新插的节点连接到之前边节点的尾巴上 
    		}
    			
    		q = (ELINK)malloc(sizeof(Edge));	//	创建边链表节点,分配内存 
    				
    		q->Local = v1;	//	记录与该顶点连接边的顶点坐标
    			
    		q->next = NULL;						//	让尾巴指向NULL 
    				
    		if(!T->List[v2].FirstNode){	//	判断是否为这个顶点第一个指向的数据 
    					
    			T->List[v2].FirstNode = q;
    					
    		}else{
    					//	这个顶点已经指向了一条边,以这条边为头节点,尾插法 
    			p = T->List[v2].FirstNode;	//	临时存放头节点 
    			while(p->next)	//	让节点指针遍历到尾巴上 
    			{
    				p = p->next;
    			}
    			p->next = q;	//	让新插的节点连接到之前边节点的尾巴上 
    		}
    			
    	} 
    	
    }
    
    //	打印邻接表 
    void PrintLink(MyGraph *S) 
    {
    	MyGraph *T = S;
    	ELINK Q;			//	防止边链表指针指到NULL ,用临时指针代替遍历打印 
    		
    	int i;
    	printf("打印邻接表结果如下:\n");
    	for(i=0;i<T->Vnum;i++)
    	{
    		Q = T->List[i].FirstNode;	//	接受每个顶点指向对应边链表的头节点指针 
    		printf("%d--->",i);
    		
    		while(1)
    		{
    			if(Q == NULL)
    			{
    				putchar('\n');
    				break;
    			}
    			printf("------->%3d",Q->Local);
    			
    			Q = Q->next;	//!!BUG 
    		}
    	}
    	putchar('\n');
    }
    
    //*****************	深度优先遍历算法—邻接表 *****************//
    void DFS_Link(MyGraph *T,int n)
    {	
    	int i,j;
    	ELINK q;	//	指向边链表节点指针 
    	
    	if(n<0 || n>=T->Vnum)
    	{
    		printf("输入有误\n");
    		return;	
    	}
    		DfsVist[n] = 1;		//	遍历一个顶点,做下标记 1  
    
    		printf(" %d",T->List[n].Vertex);
    		
    		q = T->List[n].FirstNode;	//q指向下标为i所对顶点 对应的边链表的第一个边结点	
    		
    		while(q!=NULL)	
    		{	
    			if(DfsVist[q->Local]!=1)
    			{
    			
    				j = q->Local;
    				DFS_Link(T,j);
    			} 
    			
    			q = q->next;
    		}
    	
    	
    	 
    } 
    //	初始化深度遍历—邻接表 
    void Init_DFSLINK(MyGraph *Q)
    {
    	int i;
    	for(i=0;i<Q->Vnum;i++)
    	{
    		DfsVist[i] = 0;
    	}
    		
    	for(i=0;i<Q->Vnum;i++)
    	{
    		if(!DfsVist[i])
    		{
    		 DFS_Link(Q,i);	//	此顶点没有被标记,开始递归遍历
    		}
    	}
    	putchar('\n'); 
    	
    }
    
    
    //	广度遍历 
    void BFS(MyGraph *S,int t)
    {
    	ELINK P; 			//	指向顶点所对应的边链表中 
    	
    	int i;
    	int v;		//	用来接收边链表对应的顶点
    	
    	//	为了不和广度搜素—邻接矩阵冲突
    	//	创建一个数组队列 
    	int Queue[MAXSIZE];
    	int front = 0;			//	队头 
    	int rear = 0;			//	队尾 
    		
    	printf("%d ",S->List[t].Vertex);	//	输出当前遍历边链表的顶点 
    	BfsVist[t] = 1;		//	将该顶点作标记
    	
    	rear = (rear+1)%MAXSIZE;	//	入队一个让队尾指向后移一位
    	Queue[rear] = t;	 		//	将该顶点入队 
    
    	while(front != rear)	//	若front == rear,表明这个顶点在边链表上连接的顶点已经遍历完毕 
    	{
    		front = (front+1)%MAXSIZE;		//	出队 
    	
    		v = Queue[front];			//	得到此时遍历到顶点坐标 
    		
    		P = S->List[v].FirstNode;	//	遍历当前顶点指向边链表中连接的其他顶点
    									//	也就是换个顶点的边链表继续遍历查找剩余顶点 
    		while(P!=NULL)
    		{
    			
    			if(BfsVist[P->Local] == 0)
    			{			
    				printf("%d ",P->Local+1);	//	输出连接边顶点 
    				
    				BfsVist[P->Local] = 1;		//	作标记,表示这个顶点已经搜索过 
    				
    				rear = (rear+1)%MAXSIZE;		//	将该下标入队 
    				
    				Queue[rear] = P->Local;	//	把遍历到新的边链表对应的顶点坐标入队 
    			}
    			
    			P = P->next;	//	遍历这个顶点的边链表 
    		}	
    	} 
    } 
    
    //	BFS广度遍历初始化
    void Init_BFS(MyGraph *S)
    {
    	int i;
    	
    	for(i=0;i<S->Vnum;i++)
    	{
    		BfsVist[i] = 0;	//	初始化标记符 
    	}
    	
    	for(i=0;i<S->Vnum;i++)
    	{
    		if(BfsVist[i]==0)
    			BFS(S,i);
    	}
    	
    } 
    
    int main()
    {
    	MyGraph *S;
    	S = (MyGraph *)malloc(sizeof(MyGraph));
    	
    	//	创建边链表 
    	CreateLink(S);
    	
    	//	打印边链表 
    	PrintLink(S);
    	
    	//	深度遍历
    	Init_DFSLINK(S); 
    	
    	//	广度遍历 
    	Init_BFS(S);
    	 
    	return 0;	
    } 
    
    

    运行结果:
    在这里插入图片描述

    展开全文
  • 这里写目录标题图图表示结论:图导航-最短路径算法A*算法 图 在计算机科学中,一个图...地图导航 - 起点、终点分叉口(包括十字路口·、T 字路口等)都是顶点,导航经过两顶点路径就是边! 我们导航从一

    1. 在计算机科学中,一个图就是一些顶点的集合,这些顶点通过一系列边结对(连接)。顶点用圆圈表示,边就 是这些圆圈之间的连线。顶点之间通过边连接。注意:顶点有时也称为节点或者交点,边有时也称为链接。
    2. 社交网络,每一个人就是一个顶点,互相认识的人之间通过边联系在一起, 边表示彼此的关系。这种关系可以 是单向的,也可以是双向的!
      在这里插入图片描述
      地图导航 - 起点、终点和分叉口(包括十字路口·、T 字路口等)都是顶点,导航经过的两顶点的路径就是边!

    我们导航从一个点到另外一个点可以有条路径,路径不同,路况就不同,拥堵程度不同,所以导 致不同路径所花的时间也不一样,这种不同我们可以使用边的权重来表示,即根据每条边的实际情况给每一条 边分配一个正数或者负数值。

    的树和链表都是图的特例!
    在这里插入图片描述
    在这里插入图片描述

    图的表示

    邻接列表:

    在邻接列表实现中,每一个顶点会存储一个从它这里开始的相邻边的列表。比如,如果顶点 B 有一条边到 A、 C 和 E,那么 A 的列表中会有 3 条边
    在这里插入图片描述
    邻接矩阵:
    在这里插入图片描述

    由二维数组对应的行和列都表示顶点,由两个顶点所决定的矩阵对应元素数值表示这里两个顶点是否相连(如, 0 表示不相连,非 0 表示相连和权值)、如果相连这个值表示的是相连边的权重。

    结论:

    大多数时候,选择邻接列表是正确的。(在图比较稀疏的情况下,每一个顶点都只会和少数几个顶点相 连,这种情况下邻接列表是最佳选择。如果这个图比较密集,每一个顶点都和大多数其他顶点相连,那么邻接 矩阵更合适。)

    图的导航-最短路径算法

    从起点开始访问所有路径,则到达终点节点的路径有多条,其中路径权值最短的一条则为最短路径。最短路径算法有 深度优先遍历、广度优先遍历
    在这里插入图片描述

    A*算法

    随着 3D 游戏的日趋流行,在复杂的 3D 游戏环境中如何能使非玩家控制角色准确实现自动寻路功能成为了 3D 游戏开发技术中一大研究热点。其中 A算法得到了大量的运用,A算法较之传统的路径规划算法,实时性更高、灵活性更强,寻路 结果更加接近人工选择的路径结果. A*寻路算法并不是找到最优路径,只是找到相对近的路径,因为找最优要把所有可行 路径都找出来进行对比,消耗性能太大,寻路效果只要相对近路径就行了。

    A* 算法的原理
    我们假设在推箱子游戏中人要从站里的地方移动到右侧的箱子目的地,但是这两点之间被一堵墙隔开。
    在这里插入图片描述
    我们下一步要做的便是查找最短路径。既然是 AI 算法, A* 算法和人寻找路径的做法十分类似当我们离目标较远时我们的目标方向是朝向目的点直线移动但是在近距离上因为各种障碍需要绕行(走弯路)!且已走过的地方就无须再次尝试。

    在这里插入图片描述
    G 表示从起点移动到网格上指定方格的移动距离 (暂时不考虑沿斜向移动,只考虑上下左右移动)。

    H 表示从指定的方格移动到终点的预计移动距离,只计算直线距离 (H 有很多计算方法, 这里我们设定只可以上 下左右移动,即该点与终点的直线距离)。

    令 F = G + H ,F 即表示从起点经过此点预计到终点的总移动距离

    寻路步骤:

    1. . 从起点开始, 把它作为待处理的方格存入一个预测可达的节点列表,简称 openList, 即把起点放入“预测可达节点列表”, 可达节点列表 openList 就是一个等待检查方格的列表。
    2. . 寻找 openList 中 F 值最小的点 min(一开始只有起点)周围可以到达的方格(可到达的意思是其不是障碍物,也不存 在关闭列表中的方格,即不是已走过的方格)。计算 min 周围可到达的方格的 F 值。将还没在 openList 中点放入其中, 并 设置它们的"父方格"为点 min,表示他们的上一步是经过 min 到达的。如果 min 下一步某个可到达的方格已经在 openList 列表那么并且经 min 点它的 F 值更优,则修改 F 值并把其"父方格"设为点 min。
    3. 把 2 中的点 min 从"开启列表"中删除并存入"关闭列表"closeList 中, closeList 中存放的都是不需要再次检查的方格。如 果 2 中点 min 不是终点并且开启列表的数量大于零,那么继续从第 2 步开始。如果是终点执行第 4 步,如果 openList 列 表数量为零,那么就是找不到有效路径
    4. 如果第 3 步中 min 是终点,则结束查找,直接追溯父节点到起点的路径即为所选路径。
    展开全文
  • 邻接表的深度遍历 #include <iostream> using namespace std; const int v = 10; int record[v]; //用来记录节点是否被访问过 char Ding[v]; // 用来记录顶点数据 struct Print { int date; ...

    邻接表的深度遍历

    #include <iostream>
    using namespace std;
    const int v = 10;
    int record[v];                      //用来记录节点是否被访问过
    char Ding[v];                     // 用来记录顶点数据
    
    struct Print
    {
       int date;                      //用来存放角标
       struct Print *next;
    };
    
    Print *Array[v];             
    
    void Depth(int p)
    {
        cout<<Ding[Array[p]->date];                           //将节点输出
        record[p] = 0;                                                //将输出的节点的标志变为0。(主函数里会将record全部初始化为1,1表示还未访问,0表示已访问).
        Print *q = new Print;
        q = Array[p]->next;
        while(q!=NULL)                       //一直找到尾
        {
            if(record[q->date]!=0)        //如果这个节点没被访问过,就递归这个函数
            {
              Depth(q->date);
            }
            else                                //否则看与我这个节点有关的下一个边
            {
             q = q->next;
            }
        }
    }
    
    int main()
    {
        int n,e,i,j,k;
        cout << "顶点数和边数:";
        
        cin>>n>>e;
        Print *p,*q;
        cout<<"输入顶点信息:";
        for(i=0;i<n;i++)
        {
          cin>>Ding[i];
        }
        for(i=0;i<n;i++)                               //初始化
        {
           record[i] = 1;                              
           Array[i] = new Print;
           Array[i]->date = i;
           Array[i]->next = NULL;
        }
        cout<<"请输入相临边:"<<endl;
        for(i=0;i<e;i++)                                                           //构建邻接表
        {
    
           cin>>j>>k;
           p = new Print;
           p->date = Array[j]->date;
           p->next = Array[k]->next;
           Array[k]->next = p;
           
           q = new Print;
           q->date = Array[k]->date;
           q->next = Array[j]->next;
           Array[j]->next = q;
        }
        Depth(0);
        return 0;
    }
    

    邻接表的广度遍历:

    #include <iostream>
    #include <queue>
    
    using namespace std;
    const int v = 10;
    int record[v];                               //和上面的作用一样
    char Ding[v];
    struct Print
    {
       int date;
       struct Print *next;
    };
    
    Print *Array[v];
    
    void Wedth(int p,int n)
    {
        queue<int> x;                              //用来存放节点角标
    
        cout<<Ding[Array[p]->date];
        record[p] = 0;
        x.push(p);              //让该节点入队
        Print *q;
        while(!x.empty())        
        {
            p = x.front();
            x.pop();
            q = Array[p]->next;
            while(q!=NULL)           // 这步就是为了让与该节点有关的所有节点的角标入队
            {
              if(record[q->date]!=0)            //如果没被访问过,就输出,然后把标志变为0,并入队
              {
               cout<<Ding[q->date];
               record[q->date]=0;
               x.push(q->date);
              }
              q = q->next;                       //如果不满足就看下一个节点
            }
    
        }
    }
    
    int main()
    {
        int n,e,i,j,k;
        cout << "顶点数和边数:";
        cin>>n>>e;
    
        Print *p,*q;
        cout<<"输入顶点信息:";
        for(i=0;i<n;i++)
        {
          cin>>Ding[i];
        }
        for(i=0;i<n;i++)
        {
           record[i] = 1;
           Array[i] = new Print;
           Array[i]->date = i;
           Array[i]->next = NULL;
        }
        cout<<"请输入相临边:"<<endl;
        for(i=0;i<e;i++)
        {
    
           cin>>j>>k;
           p = new Print;
           p->date = Array[j]->date;
           p->next = Array[k]->next;
           Array[k]->next = p;
           
           q = new Print;
           q->date = Array[k]->date;
           q->next = Array[j]->next;
           Array[j]->next = q;
        }
       Wedth(0,n);
        return 0;
    }
    

    我定义了很多全局变量,就是为了使用方便,但我不太清楚会不会影响程序。
    由于刚学c++,只会一些简单的方法,所有要是方法可以改进或者代码有什么不对的地方,希望指出!

    展开全文
  • "ALG.h"头文件 定义图及其各种操作 #pragma once #include <iostream> #include <string> using namespace std; const int MVNum = 100;... //该边所指向顶点在表头结点数组...

    思维导图(房子的主梁架构)

    在这里插入图片描述

    (房子的成品外观)

    程序测试图1

    在这里插入图片描述

    广度遍历图结果

    请输入总的顶点的数 :(请输入0 - 100的整数)
    6
    请输入总的边数 :(请输入0 - 100的整数)
    6
    请输入第 1 个顶点的名字 :v1
    请输入第 2 个顶点的名字 :v2
    请输入第 3 个顶点的名字 :v3
    请输入第 4 个顶点的名字 :v4
    请输入第 5 个顶点的名字 :v5
    请输入第 6 个顶点的名字 :v6
    请输入一条边所依附的第一个顶点 :
    v1
    请输入一条边所依附的第二个顶点 :
    v2
    请输入边的权值(整数) :1
    请输入一条边所依附的第一个顶点 :
    v1
    请输入一条边所依附的第二个顶点 :
    v3
    请输入边的权值(整数) :2
    请输入一条边所依附的第一个顶点 :
    v1
    请输入一条边所依附的第二个顶点 :
    v4
    请输入边的权值(整数) :3
    请输入一条边所依附的第一个顶点 :
    v2
    请输入一条边所依附的第二个顶点 :
    v5
    请输入边的权值(整数) :4
    请输入一条边所依附的第一个顶点 :
    v3
    请输入一条边所依附的第二个顶点 :
    v5
    请输入边的权值(整数) :5
    请输入一条边所依附的第一个顶点 :
    v4
    请输入一条边所依附的第二个顶点 :
    v6
    请输入边的权值(整数) :6
    请输入开始遍历的顶点:2
    广度遍历结果 :
    v2 v5 v1 v3 v4 v6

    深度遍历图结果

    请输入总的顶点的数 :(请输入0 - 100的整数)
    6
    请输入总的边数 :(请输入0 - 100的整数)
    6
    请输入第 1 个顶点的名字 :v1
    请输入第 2 个顶点的名字 :v2
    请输入第 3 个顶点的名字 :v3
    请输入第 4 个顶点的名字 :v4
    请输入第 5 个顶点的名字 :v5
    请输入第 6 个顶点的名字 :v6
    请输入一条边所依附的第一个顶点 :
    v1
    请输入一条边所依附的第二个顶点 :
    v2
    请输入边的权值(整数) :1
    请输入一条边所依附的第一个顶点 :
    v1
    请输入一条边所依附的第二个顶点 :
    v3
    请输入边的权值(整数) :2
    请输入一条边所依附的第一个顶点 :
    v1
    请输入一条边所依附的第二个顶点 :
    v4
    请输入边的权值(整数) :3
    请输入一条边所依附的第一个顶点 :
    v2
    请输入一条边所依附的第二个顶点 :
    v5
    请输入边的权值(整数) :4
    请输入一条边所依附的第一个顶点 :
    v3
    请输入一条边所依附的第二个顶点 :
    v5
    请输入边的权值(整数) :5
    请输入一条边所依附的第一个顶点 :
    v4
    请输入一条边所依附的第二个顶点 :
    v6
    请输入边的权值(整数) :6
    请输入开始遍历的顶点:2
    深度遍历结果 :
    v2 v5 v3 v1 v4 v6

    程序测试图2

    在这里插入图片描述

    深度遍历图结果

    请输入总的顶点的数 :(请输入0 - 100的整数)
    8
    请输入总的边数 :(请输入0 - 100的整数)
    8
    请输入第 1 个顶点的名字 :v1
    请输入第 2 个顶点的名字 :v2
    请输入第 3 个顶点的名字 :v3
    请输入第 4 个顶点的名字 :v4
    请输入第 5 个顶点的名字 :v5
    请输入第 6 个顶点的名字 :v6
    请输入第 7 个顶点的名字 :v7
    请输入第 8 个顶点的名字 :v8
    请输入一条边所依附的第一个顶点 :
    v1
    请输入一条边所依附的第二个顶点 :
    v2
    请输入边的权值(整数) :1
    请输入一条边所依附的第一个顶点 :
    v1
    请输入一条边所依附的第二个顶点 :
    v3
    请输入边的权值(整数) :2
    请输入一条边所依附的第一个顶点 :
    v2
    请输入一条边所依附的第二个顶点 :
    v4
    请输入边的权值(整数) :3
    请输入一条边所依附的第一个顶点 :
    v2
    请输入一条边所依附的第二个顶点 :
    v5
    请输入边的权值(整数) :4
    请输入一条边所依附的第一个顶点 :
    v3
    请输入一条边所依附的第二个顶点 :
    v6
    请输入边的权值(整数) :5
    请输入一条边所依附的第一个顶点 :
    v3
    请输入一条边所依附的第二个顶点 :
    v7
    请输入边的权值(整数) :6
    请输入一条边所依附的第一个顶点 :
    v4
    请输入一条边所依附的第二个顶点 :
    v8
    请输入边的权值(整数) :7
    请输入一条边所依附的第一个顶点 :
    v5
    请输入一条边所依附的第二个顶点 :
    v8
    请输入边的权值(整数) :8
    请输入开始遍历的顶点:1
    深度遍历结果 :
    v1 v3 v7 v6 v2 v5 v8 v4

    广度遍历图结果

    请输入总的顶点的数 :(请输入0 - 100的整数)
    8
    请输入总的边数 :(请输入0 - 100的整数)
    8
    请输入第 1 个顶点的名字 :v1
    请输入第 2 个顶点的名字 :v2
    请输入第 3 个顶点的名字 :v3
    请输入第 4 个顶点的名字 :v4
    请输入第 5 个顶点的名字 :v5
    请输入第 6 个顶点的名字 :v6
    请输入第 7 个顶点的名字 :v7
    请输入第 8 个顶点的名字 :v8
    请输入一条边所依附的第一个顶点 :
    v1
    请输入一条边所依附的第二个顶点 :
    v2
    请输入边的权值(整数) :1
    请输入一条边所依附的第一个顶点 :
    v1
    请输入一条边所依附的第二个顶点 :
    v3
    请输入边的权值(整数) :2
    请输入一条边所依附的第一个顶点 :
    v2
    请输入一条边所依附的第二个顶点 :
    v4
    请输入边的权值(整数) :3
    请输入一条边所依附的第一个顶点 :
    v2
    请输入一条边所依附的第二个顶点 :
    v5
    请输入边的权值(整数) :4
    请输入一条边所依附的第一个顶点 :
    v4
    请输入一条边所依附的第二个顶点 :
    v8
    请输入边的权值(整数) :5
    请输入一条边所依附的第一个顶点 :
    v5
    请输入一条边所依附的第二个顶点 :
    v8
    请输入边的权值(整数) :6
    请输入一条边所依附的第一个顶点 :
    v3
    请输入一条边所依附的第二个顶点 :
    v6
    请输入边的权值(整数) :7
    请输入一条边所依附的第一个顶点 :
    v3
    请输入一条边所依附的第二个顶点 :
    v7
    请输入边的权值(整数) :8
    请输入开始遍历的顶点:1
    广度遍历结果 :
    v1 v3 v2 v7 v6 v5 v4 v8

    (房子的砖头部分)

    "ALG.h"头文件

    定义图及其各种操作

    #pragma once
    #include <iostream>
    #include <string>
    using namespace std;
    const int  MVNum = 100;
    
    //边结点定义
    typedef struct ArcNode {
    	int adjvex;					//该边所指向的顶点在表头结点表数组的下标
    	struct  ArcNode* nextarc;	//该边指向下一条边的指针
    	int info;					 //边的权值
    }ArcNode;
    
    //顶点和顶点表的定义
    typedef struct VNode {
    	string data;				 //顶点的名称
    	ArcNode* firstarc;			//指向第一条依附在该顶点的第一条边
    } VNode, AdjList[MVNum];			//定义一个表头结点表的数组类型
    
    								//邻接表的定义
    typedef struct {
    	AdjList vertices;			//表头结点表
    	int vexnum, arcnum;			//图的顶点数和边数
    }ALgraph;
    
    //获取输入结点在表头结点表的数组下标
    int LocateVex(ALgraph G, VNode* p) {
     	for (int i = 0; i <= G.vexnum; i++) {
    		if (G.vertices[i].data == p->data)
    			return i;
    	}
    	return -1;
    }
    //构造邻接表表示无向图
    /*  需求:
    	1,表头结点存储图的各个顶点的名字,相应边链表的头结点的指针域
    	分析:
    	1,接收键盘录入的总顶点数,总边数
    	2,for循环,逐个录入图的每一个结点信息(名,指针域初始化未NULL),构造表头结点表
    	3,for循环,输入 图的各边信息(边的依附顶点),通过依附顶点在表头结点的值获取顶点在表头结点的数组的下标值,
    	根据获取的下标,生成新的边界点,为结点的各个属性赋值,用链表前插法链入顶点的边链表中
    */
    void CreateUDG(ALgraph &G) {
    	//1,接收键盘录入的总顶点数,总边数
    	//while (true) {
    	cout << "请输入总的顶点的数 :(请输入0 - 100的整数)" << endl;
    	cin >> G.vexnum;
    	cout << "请输入总的边数 :(请输入0 - 100的整数)" << endl;
    	cin >> G.arcnum;
    	//if ((G.vexnum >= 0 && G.vexnum < 100) && (G.arcnum >= 0 && G.arcnum <= 100)) {
    	//	cout << "录入成功!\n";
    	//	break;
    //	}
    	//else {
    	//	cout << "你的输入有误,请从新输入。" << endl;
    	//}
    //}
    	cout << G.vexnum << G.arcnum;
    
    	//2,for循环,逐个录入图的每一个结点信息(名,指针域初始化未NULL),构造表头结点表
    	for (int i = 0; i < G.vexnum; i++) {
    		cout << "请输入第 " << i + 1 << " 个顶点的名字 :";
    		cin >> G.vertices[i].data;
    		G.vertices[i].firstarc = NULL;
    	}
    	//3,for循环,输入 图的各边信息(边的依附顶点),通过依附顶点在表头结点的值获取顶点在表头结点的数组的下标值,
    	//	根据获取的下标,生成新的边界点,为结点的各个属性赋值,用链表前插法链入顶点的边链表中,构造邻接边表
    	VNode* v1 = new VNode;
    	VNode* v2 = new VNode;
    	for (int k = 0; k < G.arcnum; k++) {
    		cout << "请输入一条边所依附的第一个顶点 :" << endl;
    		cin >> v1->data;
    		cout << "请输入一条边所依附的第二个顶点 :" << endl;
    		cin >> v2->data;
    		int i = LocateVex(G, v1);
    		int j = LocateVex(G, v2);
    		//头插法为Vi插入新的边结点
    		ArcNode * p1 = new ArcNode;
    		cout << "请输入边的权值(整数) :";
    		cin >> p1->info;
    		p1->adjvex = j; //邻接结点在头结点表的下标
    		p1->nextarc = G.vertices[i].firstarc;
    		G.vertices[i].firstarc = p1;
    		//头插法为Vj插入新的边结点
    		ArcNode * p2 = new ArcNode;
    		p2->info = p1->info;
    		p2->adjvex = i;
    		p2->nextarc = G.vertices[j].firstarc;
    		G.vertices[j].firstarc = p2;
    	}
    }
    void Opertion_Create()
    {
    	ALgraph G;
    	CreateUDG(G);
    }
    //定义辅助数组
    bool visited[MVNum];
    
    

    "DFS.h"头文件

    实现深度遍历算法

    #pragma once
    #include"ALG.h"
    
    
    
    //深度遍历核心函数
    void DFS(ALgraph G, int v) { //从第V个顶点开始遍历
    	//1,访问第V个顶点
    	cout << G.vertices[v].data << " ";
    	visited[v] = true; //置访问标志数组相应的分量值为true
    	ArcNode * p = G.vertices[v].firstarc; //获取被访问顶点的边链表的首元结点的指针
    	while (p) {
    		int w = p->adjvex; //获取v顶点的邻接顶点
    		if (visited[w]== false) //判断该顶点是否被访问过
    			DFS(G, w);
    		p = p->nextarc; //指向下一个边结点
    	}
    }
    //深度遍历测试函数
    void DFS_Traverse(ALgraph G) {
    	//访问标志辅助数组初始化
     	for (int i = 0; i < MVNum; i++)
    	{
    		visited[i] = false;
    	}
    	//连通图遍历
    	int v;
    	cout << "请输入开始遍历的顶点:";
    	cin >> v;
    	DFS(G, v-1);
    	//非连通图遍历
    	/*
    	for (int v = 0; v < G.vexnum; v++) {
    		if (visited[v] == false)
    			DFS(G, v);
    	}
    	*/
    }
    void Opreation_DFS() {
    	//2,创建图的邻接表
    	ALgraph G;
    	CreateUDG(G);
    	//3,对图进行深度遍历
    	DFS_Traverse(G);
    }
    

    "BFS.h"头文件

    #pragma once
    #include"ALG.h"
    
    //队列结点的结构
    typedef struct Qnode {
    	int data;
    	struct Qnode * next;
    }Qnode, *QueuePtr;
    
    //链表队列结构
    typedef struct {
    	QueuePtr front; //队头指针
    	QueuePtr rear;	//队尾指针
    }LinkQueue;
    
    //初始化队列
    void InitQueue(LinkQueue &Q) {
    	Q.front = Q.rear = new Qnode;	//生成新的结点作为头结点,初始化队头队尾指针
    	Q.front->next = NULL;	//头结点的指针域为空
    }
    
    //链队入队
    bool EnQueue(LinkQueue &Q, int e) {
    	Qnode * p = new Qnode; //创建一个新的结点
    	p->data = e;
    	p->next = Q.front->next;
    	Q.rear->next = p; //插入新节点到队尾
    	Q.rear = p; //修改队尾指针
    	return true;
    }
    
    //链队出队
    bool DeQueue(LinkQueue &Q, int &e) {
    	if (Q.front == Q.rear)
    		return false;
    	Qnode * p; //保存头结点指针,用于释放空间
    	p = Q.front->next; //指向队头结点
    	e = p->data; //获取队头结点的元素的值
    	Q.front->next = p->next; //修改头指针
    	if (Q.rear == p)  //判断删除的元素是否为最后一个元素,避免空指针异常,将队尾指针重新指向队头指针
    		Q.rear = Q.front;
    	Q.rear->next = Q.front->next; //最后一个结点指向首元结点
    	delete p;
    	return true;
    }
    
    //销毁队列
    void DeleteQueue(LinkQueue &Q) {
    	while (Q.front)
    	{
    		Q.rear = Q.front->next;
    		delete Q.front;
    		Q.front = Q.rear;
    	}
    }
    
    //ALG.h头文件声明辅助数组
    
    //广度遍历核心函数
    void BFS(ALgraph G, int v) {
    	LinkQueue Q;
    	InitQueue(Q);
    	cout << G.vertices[v].data << " ";
    	visited[v] = true;
    	EnQueue(Q,v);
    	while (Q.front != Q.rear) {
    		int u;
    		DeQueue(Q, u);
    		ArcNode * p = G.vertices[u].firstarc; //获取被访问顶点的边链表的首元结点的指针
    		while (p) { // 先输入一个顶点的所有临界点
    			int w = p->adjvex; //获取v顶点的邻接顶点
    			if (visited[w] == false) {//判断该顶点是否被访问过
    				cout << G.vertices[w].data << " ";  
    				visited[w] = true;  //修改辅助表
    				EnQueue(Q, w); //已经输出的邻接点入队
    			}
    			p = p->nextarc; //指向顶点的下一个邻接点
    		}
    		
    	}
    	
    	
    }
    
    //广度遍历操作函数
    void BFS_Traverse(ALgraph G) {
    	//访问标志辅助数组初始化
    	for (int i = 0; i < MVNum; i++)
    	{
    		visited[i] = false;
    	}
    	//连通图遍历
    	int v;
    	cout << "请输入开始遍历的顶点:";
    	cin >> v;
    	BFS(G, v - 1);
    }
    void Opreation_BFS() {
    	//2,创建图的邻接表
    	ALgraph G;
    	CreateUDG(G);
    	//3,对图进行深度遍历
    	BFS_Traverse(G);
    }
    

    photos.cpp 主函数

    用于测试和实现头文件中的各种算法操作函数

    // photos.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
    
    
    #include "pch.h"
    #include"ALG.h"
    #include"DFS.h"
    #include"BFS.h"
    int main()
    {
    	//Opertion_Create();
    	//Opreation_DFS();
    	Opreation_BFS();
    }
    
    
    
    展开全文
  • 线性表是一种线性结构,除了头结点尾节点,线性表每个元素都只有一个前取节点一个后继节点。而树结构则相较于线性表更加复杂,它描述关系为数据元素之间父子关系,也是现实世界父子关系缩影, 一个父亲...
  • 先贴程序,明天再写详细原理过程 #include #include #include using namespace std; const int MAXVEX = 100; typedef char VertexType; typedef int EdgeType; //邻接矩阵 typedef struct { int num; ...
  • 邻接表实现代码:.../** 邻接表深度优先遍历和广度优先遍历 **/ #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #define MaxVex 255 #define TRUE 1 #defin...
  • 的邻接表创建及深度优先遍历和广度优先遍历

    万次阅读 多人点赞 2019-01-17 20:09:36
    创建一般有邻接矩阵和邻接表两种方法,邻接矩阵对于边数相对于顶点较少图会有极大浪费,所以用邻接表,用数组与链表相配合 顶点用一维数组储存 所有顶点邻接点构成一个线性表,因为邻接点个数不确定,...
  • printf("请输入该图顶点个数,以及边个数:\n"); scanf("%d%d",&G.vexnum,&G.arcnum); getchar(); printf("请依次输入图顶点:\n"); for(i=0;i;i++) { scanf("%c",&G.vertices[i].data); G....
  • 邻接表介绍邻接矩阵是不错的一种图存储结构,但是我们也发现,对于边数相对顶点较少的图...关于邻接矩阵的详细介绍请看:图:图的邻接矩阵创建、深度优先遍历和广度优先遍历详解 。邻接表创建图我们创建边表的单链...
  • 可以用邻接表邻接矩阵求最短路径 实现图的邻接矩阵邻接表存储结构;...完成基于邻接矩阵或邻接表的深度优先搜索遍历广度优先搜索遍历; 实现从键盘输入任意一对顶点,求出顶点间的最短路径。
  • } //->1图邻接表的深度遍历 int AdjListDepthFirstRecursion(AdjListGraph *alg,int i) { if(visited[i]) return OK; printf("%s ",alg->vlist[i].vertex.c_str());//打印顶点 visited[i]=true; AdjListGraph...
  • //LinkList.h #ifndef _LINKLIST_H_ #define _LINKLIST_H_ typedef void LinkList; typedef struct _tag_LinkListNode LinkListNode; struct _tag_LinkListNode { LinkListNode* next;...LinkList* LinkList_
  • /*(1)输入一组顶点,建立有向图的邻接表,进行DFS(深度优先遍历BFS(广度优先遍历)。 写出深度优先遍历的递归非递归算法。 (2)根据建立有向图,判断该图是否是有向无环图,若是,则输出其一种拓扑有序...
  • * 广度遍历,用队列实现,需要布尔map判断是否访问过 */ public static void BroadFirstTravel(GraphNode graph){ if(graph == null)return; Map,Boolean> map = new HashMap,Boolean>(); Queue...
  • 前面的博客已经写了关于邻接表的源代码,下面简单讨论下邻接表存储的特点,方便下面讨论遍历的方式, 邻接表是图的一种链式存储结构,顶点表是顺序存储,每个顶点及其邻接点组成一条链表,即n个顶点共有n条链表,...
  • /**************************... *功 能:利用邻接表存储图,实现其递归与非递归的深度遍历和广度遍历  *作 者:JarvisChu  *时 间:2011-04-30  *********************************************************
  • 存储有邻接矩阵和邻接表这几种方式,邻接矩阵是个二维数组,邻接表是一个点集加链表形式,这里我们想用vector来实现邻接表。 为什么vector可以实现邻接表,注意邻接表是点集加链表,为什么加链表是因为链表...
  • import java.io.*; import java.util.*; class task1{ ... public static void main(String[] args) throws Exception{ ... BufferedReader bR = new BufferedReader(new ...有向图实现大概是这样吧,用一层ArrayList...
  • 邻接表的方式建立一个无向图,并且对图进行深度优先遍历和广度优先遍历 1.无向图的建立 需要两种节点: 头结点,表结点 2.深度优先遍历dfs 是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽...
  • 从图中某个顶点v出发,访问此顶点,然后从v未被访问到的邻接点进行遍历,直到图中所有v有路径相通顶点都被访问到(注:优先访问外层节点,访问到无新顶点时,会进行回退,访问未被访问过分支顶点)。...
  • import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Stack;...//该弧指向节点名 int weight;//权重 Edge nextEd...
  • 数据结构目前学习基本大概已经完成了,图讲解也基本结束,本次试验就是图的遍历。   将常用头文件放在t11.h中   #include"stdio.h" #include"string.h" #include"ctype.h" #include"malloc.h" #...
  • 利用邻接表对无向连通图进行深度遍历和广度遍历 文章目录利用邻接表对无向连通图进行深度遍历和广度遍历1.深度遍历过程详解2.广度遍历过程详解3.代码实现4.一点注意5.End 1.深度遍历过程详解  1.过程详解:首先选择...
  • 本程序通过java使用邻接表对图进行深度和广度优先遍历,其中包括图和节点数据结构实现

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 897
精华内容 358
关键字:

邻接表的深度遍历和广度遍历