无向图邻接多重链表实现与创建算法详解

版权申诉
0 下载量 58 浏览量 更新于2024-07-07 收藏 662KB DOCX 举报
"本篇文章是蛤蟆的数据结构笔记，主要探讨图的邻接多重链表表示实现。邻接多重表（AdjacencyMultilist）是一种常用的数据结构，特别适用于无向图的存储，因为它解决了无向图中每条边双向关联的问题。相比于邻接表，邻接多重表在处理无向图时更加高效，特别是涉及到查找、标记或删除重复边的操作。 邻接多重表的存储结构类似于十字链表，由顶点表和边表构成。顶点表中的每个结点包含两个域：vertex用于存储顶点的相关信息，firstedge则指示与该顶点相连的第一条边。边表结点则有六个域，包括mark标记域用于标记边是否被搜索过，ivex和jvex分别记录边依附的两个顶点的索引，以及ilink和jlink分别指向下一条依附于ivex和jvex顶点的边，info域则存放与边相关的额外信息。 在邻接多重表中，同一顶点的所有边都被组织成一个链表，且每条边的两个端点在它们各自所属的链表中都有对应的边结点。这样设计使得图的操作更加直观和高效。例如，创建无向图G时，函数creategraph首先打开cmnet.txt文件，读取顶点数和边数，接着为每个顶点分配节点并初始化第一条边为NULL，然后逐条读取边的信息，创建边表节点并将其插入到对应顶点的链表头部。整个过程确保了无向图的正确构建。 文章还提到，邻接多重表对于处理无向图的遍历、搜索和边的增删操作非常适用，体现了“一个人的价值在于他所做出的贡献”这一理念，即在实际问题中选择合适的数据结构能够提高算法的效率，从而实现更大的价值。通过这篇笔记，读者可以深入了解邻接多重链表的实现原理及其在无向图处理中的应用。"

40. 蛤蟆的数据结构笔记之四十图的邻接多重链表表示实现.pdf

2021-10-30 上传
40. 蛤蟆的数据结构笔记之四十图的邻接多重链表表示实现.pdf

数据结构 图的结构 邻接表的实现

2010-06-15 上传
这是我的作业。。。。希望对各位有#include <stdio.h> #include <malloc.h> #include <stdlib.h> #define SIZE (xsize*ysize+1) //一系列全局变量便于传递参数 int *location,*way, xsize,ysize,firstx,firsty, noworder; int getnum (void);//取数函数，取数成功返回1，否则返回-1 int init (void); //初始化函数，申请数组空间，以及初始化数组， //申请成功返回1，否则返回-1 int play (void); //下棋函数，下棋成功返回1，否则返回-1 int back (void); //悔棋函数，悔棋成功返回1，否则返回-1 void print (void);//输出函数，顺序输出马踩的棋盘一维坐标 //////////////////////////// void main () { int canget,caninit,canplay,canback; do canget=getnum(); while(canget==-1); caninit=init(); if(caninit==-1) exit (0);//终止程序运行 for (;noworder<SIZE-1;) { if(way[location[noworder]]>0 && way[location[noworder]]<=8) { canplay=play(); if(canplay==-1) way[location[noworder]]++;//当前方法不可行，改变方法 } else { canback=back(); if(canback==-1) { printf("不可能遍历整个棋盘！\n"); getchar();getchar(); exit (0);//当程序不能再悔棋时终止程序运行 } else way[location[noworder]]++; //当前方法不可行，改变方法 } } if(noworder==SIZE-1)//已经遍历整个棋盘 print(); getchar();getchar(); } //////////////////////////// int getnum() { printf("输入棋盘规格（假定无0点）和入口坐标：\n"); printf("输入棋盘规格xsize="); scanf("%d",&xsize); printf("输入棋盘规格ysize="); scanf("%d",&ysize); printf("输入入口坐标x="); scanf("%d",&firstx); printf("输入入口坐标y="); scanf("%d",&firsty); if (firstx>xsize || firsty>ysize || firstx<=0 || firsty<=0 || xsize <3 || ysize<3) { printf("输入有误，重新输入：\n\n\a"); return -1; } else return 1; } //////////////////////////// int init (void) { location=(int *)malloc(sizeof(int)*SIZE); way=(int *)malloc(sizeof(int)*SIZE); if(location==NULL || way==NULL) { printf("系统申请内存空间失败！程序执行终止！\a"); return -1; } for(int i=0;i<SIZE;i++)//初始化数组 { way[i]=0; location[i]=0; } noworder=1; location[1]=(firsty-1)*xsize+firstx; way[location[1]]=1; return 1; } //////////////////////////// void print(void) { printf("\n\n可以遍历，顺序如下：\n\n"); for (int i=1;i<SIZE;i++) { printf("%3d-->",location[i]); printf("OK\n"); } } //////////////////////////// int play() { int x,y,nextlocation; //一维坐标值à二维坐标值 x=location[noworder] % xsize; if(x==0) x=xsize; y=(location[noworder]-x)/xsize+1; switch (way[location[noworder]]) { case 1 : x+=2;y-=1;break; case 2 : x+=2;y+=1;break; case 3 : x+=1;y+=2;break; case 4 : x-=1;y+=2;break; case 5 : x-=2;y+=1;break; case 6 : x-=2;y-=1;break; case 7 : x-=1;y-=2;break; case 8 : x+=1;y-=2;break; } nextlocation = xsize*(y-1)+x; if (x>xsize || y>ysize || x<=0 || y<=0 || way[nextlocation]!=0)//越界或重复 return -1; else//下棋 { noworder++; location[noworder] = nextlocation; way[location[noworder]]=1; return 1; } } //////////////////////////// int back (void) { if(noworder==1)//不能再悔棋，不能遍历 return -1; else { way[location[noworder]]=0;//注意不能搞错语句顺序 location[noworder]=0; noworder--; return 1; } }用

用邻接表实现图的数据结构

2017-01-03 上传
用邻接表实现图的数据结构，链表方式实现，win32+vs2013

有向图的正邻接链表和逆邻接链表。

2023-12-31 上传
有向图的正邻接链表和逆邻接链表是用来表示有向图中节点之间关系的数据结构。 正邻接链表是指对于每个节点，记录其指向其他节点的边的信息。逆邻接链表是指对于每个节点，记录指向该节点的边的信息。 下面是一个...

十字链表和邻接多重表

2023-08-31 上传
所以，十字链表是用于表示有向图的数据结构，而邻接多重表则用于表示无向图的数据结构。它们分别在记录顶点和边之间的关系上有所不同。<span class="em">1</span><span class="em">2</span><span class="em">3 #### ...

深度优先遍历邻接矩阵邻接矩阵转化为邻接链表

2024-06-05 上传
邻接链表是另一种表示图的数据结构，它由若干个链表组成，每个链表表示一个节点以及与它相连的所有边。将邻接矩阵转化为邻接链表可以通过遍历邻接矩阵，将每个节点以及与它相连的边添加到对应的链表中。 具体步骤...

任意选用一种数据结构，编写程序将图存入内存，并实现以下的各个操作: 邻接表Q、邻接多重表之间转换，如果是有向图或有向网，在邻接矩阵.1.存储结构的转换:如果是无向图或无向网，在邻接矩阵、邻接表和逆邻接表、十字链表之间转换; 2.完成增加顶点和删除顶点的功能，删除顶点也要删除与之关联的边; 3.完成增加边和删除边的功能: 4. 完成图的深度优先遍历和广度优先遍历; 5.求图的深度优先或广度优先的生成树(或生成森林) (存储结构为孩子-兄弟链表)，并对生成树进行遍历 6.判断图的连通性，输出连通分量的个数; 7.判断图中是否存在环; 8.判断u到v是否存在路径 9.对于图 (不是网)，求顶点u到v的一条简单路径 10.对于图 (不是网)，求顶点u到v的所有简单路径 11.实现Diikstra和Flovd算法求最短路径;C++实现

2023-06-12 上传
1. 邻接表、邻接多重表、邻接矩阵、逆邻接表、十字链表之间的转换可以参考相关的算法书籍，这里不再赘述。 2. 增加顶点可以在邻接表中添加一个新节点，删除顶点需要先删除与该顶点相关的边，然后再删除该顶点节点。...

建立一个有向图的邻接链表表示，实现对图广度优先遍历

2023-05-18 上传
首先，我们需要定义一个图的数据结构，包含节点个数和邻接链表： ```python class Graph: def __init__(self, num_of_vertices): self.num_of_vertices = num_of_vertices self.adjacency_list = [[] for _ in ...

实现邻接链表和逆邻接链表两种求顶点入度的算法

2023-11-23 上传
实现邻接链表和逆邻接链表两种求顶点入度的算法： 邻接链表求顶点入度的算法： 1. 初始化一个长度为n的数组indegree，用于存储每个顶点的入度。 2. 遍历每个顶点的邻接表，将每个邻接点的入度加1。 3. 遍历indegree...

C语言代码建立一个有向图的邻接链表表示，实现对图广度优先遍历

2023-05-18 上传
以下是 C 语言代码建立有向图的邻接链表表示，以及实现对图的广度优先遍历： ```c #include <stdio.h> #include <stdlib.h> #define MAX_VERTICES 50 // 最大顶点数 /* 边节点结构体 */ typedef struct edgeNode ...
weixin_46195928
  • 粉丝: 13
  • 资源: 9万+
上传资源 快速赚钱

最新资源