精华内容
下载资源
问答
  • 链式表表示法----【邻接表/ 邻接多重表 / 十字链表】 邻接表     将所有的顶点数据仍然存放在一维数组内。     这个一维数组比较特殊,顶点数组的每个元素都指向一个邻接点单链表。 咱们以上一个邻接矩阵...

    链式存储 (链式表示)

        上一话说的是邻接矩阵方式去存储图,这一话用链表去存储图
    链式表表示法----【邻接表/ 邻接多重表 / 十字链表】

    邻接表

        将所有的顶点数据仍然存放在一维数组内。
        这个一维数组比较特殊,顶点数组的每个元素都指向一个邻接点单链表。

    咱们以上一个邻接矩阵用到的一个有向图和无向图为例:
    在这里插入图片描述

    无向图 的邻接表

    第一个无向图的邻接表可以这样表示:

    A邻接于B->C->NULL
    B邻接于A ->C ->D ->NULL
    C邻接于A ->D ->B->NULL
    D邻接于B ->C ->NULL

        实际上邻接表是不唯一的,每一个顶点元素指向一个单链表,单链表的所有节点都是顶点元素的邻接点,顺序是可以随意更改的,比如上面的表中,A指向的单链表,B和C的顺序可以改变的。

        如果无向图n个顶点,e条边,那么用邻接表来存储这个图需要 n个头结点 和 2e个表结点。 更适合存储稀疏图。
         无向图 中顶点Vi的度为该顶点指向的单链表中的节点的个数。

    问题:上面第一个无向图,5条边在邻接表里面存了两次,一共10个节点。

    有向图 的邻接表

    咱么以上面第二个有向图为例,邻接表的表示为

    A邻接于B->NULLNULL
    B邻接于C ->D->NULL
    C邻接于A ->D->NULL
    D邻接于NULL

    特点: 该邻接表求顶点的出度容易,求入度困难。

    1. 顶点Vi的出度,就是这个顶点指向的单链表中节点的个数。
    2. 顶点Vi的入度, 必须要遍历非Vi顶点所指向的所有单链表。
    有向图 的逆邻接表

    咱们可以改变一下存储方式,上面的邻接表,每一个顶点元素指向的单链表存储的是该顶点的出度边指向的元素。 比如以第二个有向图的顶点 A 为例,他指向单链表中的元素为顶点B,为A指向B的弧尾。

    咱们可以存储以A为入度边的弧尾的元素,这种类型的邻接表叫逆邻接表

    还是以上面图中的第二个有向图为例:

    A被邻接于C->NULL
    B被邻接于A ->NULL
    C被邻接于B ->NULL
    D被邻接于B ->C->NULL

    特点: 该邻接表求顶点的 入度容易,求出度困难。

    1. 顶点Vi的入度,就是这个顶点指向的单链表中节点的个数。
    2. 顶点Vi的出度, 必须要遍历非Vi顶点所指向的所有单链表。

    邻接表的特点

    1. 很快速方便的找到某个顶点的“邻接点”
    2. 节约稀疏图(点多边少)的空间
    3. (针对无向图)求顶点的度很方便,求该顶点指向的单链表的节点个数即可
    4. (针对有向图)求顶点的出度方便,该顶点指向单链表的节点个数。【对于入度不方便,需要遍历所有单链表】
    5. (针对有向图)如果是逆邻接表,求顶点的入度方便,入度就为该顶点指向的单链表的节点个数。【对于出度不方便,需要遍历所有单链表】

    对于有向图来说,邻接表和逆邻接表只能求出度或者入度容易,不能同时求出,可以将邻接表和逆邻接表结合起来改良为十字链表(存储的边节点个数不变,只是边节点存储的内容会多一些)。

    对于无向图来说,求出度和入度容易,添加和删除麻烦,并且无向图邻接表的 边节点是存储了两份,所以改良为邻接多重表(将存储的边节点存储为一份,不会重复,边节点的内容也同样会多出来)


    邻接矩阵与邻接表的区别

    1. 对于任意一个无向图,邻接矩阵是唯一的。但是邻接表不唯一,因为顶点指向的单链表各个节点的顺序是任意的,可以用头插法,也可以用尾插法。
    2. 邻接矩阵的空间复杂度为O(n^2), 邻接表的空间复杂度O(n+e) n为顶点个数,e为边的条数(也可以理解为所有指向的单链表中节点的个数)。
    3. 邻接矩阵多适用于稠密图(点多边多),邻接表多适用于稀疏图(点多边少 )
    展开全文
  • 邻接表

    2021-05-17 10:02:56
    当一个图稀疏图时,使用邻接矩阵表示显然要浪费大量的存储空间,而图的邻接表法结合了顺序存储和链式存储方法,大大减少了这种不必要的浪费。 所谓邻接表,是指对图G中的每一个顶点vi建立一个单链表,第 i 个...

    邻接表(顺序+链式存储)

    当一个图为稀疏图时,使用邻接矩阵表示显然要浪费大量的存储空间,而图的邻接表法结合了顺序存储和链式存储方法,大大减少了这种不必要的浪费。
    在这里插入图片描述

    #define MaxVertexNum 100; //图中顶点数目的最大值
    //"边/弧"
    typedef struct ArcNode{
        int adjvex; //边/弧指向哪个结点
        struct ArcNode *next; //指向下一条弧的指针
        //InfoType info; //边权值
    }ArcNode;
    //"顶点"
    typedef struct VNode{
        VertexType data; //顶点信息
        ArcNode *first; //第一条边/弧
    }VNode, AdjList[MaxVertexNum];
    //用邻接表存储的图
    typedef struct{
        AdjList vertices; //邻接表
        int vexnum, arcnum; //图的顶点数和弧数
    }ALGraph; //ALGraph是以邻接表存储图类型
    

    在这里插入图片描述

    邻接表

    邻接表,是指对图G中的每一个顶点vi建立一个单链表,第 i 个单链表中的结点表示依附于顶点 vi 的边(对于有向图则是以顶点vi为尾的弧),这个单链表就称为顶点vi的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(成为顶点表),所以在邻接表中存在两种:顶点表结点和边表结点。

    顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc)构成,边表(邻接表)结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc)构成。
    在这里插入图片描述
    ① 若G为无向图,则所需的存储空间为O(|V|+2|E|);若G为有向图,则所需的存储空间为O(|V|+|E|)。前者的倍数2是由于无向图中,每条边在邻接表中出现了两次。
    ② 对于稀疏图,采用邻接表表示将极大地节省存储空间。
    ③ 在邻接表中,给定一顶点,能很容易地找出它的所有邻边,因为只需要读取它的邻接表。在邻接表矩阵中,相同的操作则需要扫描一行,话费花费的时间为O(n)。但是,若要确定给定的两个顶点间是否存在边,则在邻接矩阵中立刻查到,而在邻接表中则需要在相应结点对应的边表中查找另一个结点,效率较低。
    ④ 在有向图的邻接表表示中,求一个给定顶点的出度只需要计算其邻接表中的结点个数;但求其顶点的入度则需要遍历全部的邻接表。因此,也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然,这实际上与邻接表存储方式是类似的。
    ⑤ 图的邻接表表示并不唯一,因为在每个顶点对应的单链表中,各边结点的链表次序可以是任意的,它取决于建立邻接表的算法及边的输入次序。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 图的存储结构——邻接表

    千次阅读 2020-01-28 20:52:13
    图的存储结构之邻接表一、邻接表表示法无向图的邻接表有向图的邻接表有向图的逆邻接表二、图的邻接表存储表示 一、邻接表表示法 回忆在线性表时,顺序存储结构就存在预先分配内存可能造成存储空间浪费的问题,...

    一、邻接表表示法

    回忆在线性表时,顺序存储结构就存在预先分配内存可能造成存储空间浪费的问题,于是引出了链式存储结构,同样的,我们可以考虑对边或弧使用链式存储方式来避免空间浪费问题

    邻接表是图的一种链式存储结构。

    由两部分组成:表头结点表和边表

    邻接表中每个单链表的第一个结点存放有关顶点的信息,把这一结点看成链表的表头,其余结点存放有关边的信息

    (1)表头结点表:包括数据域和链域,数据域存储顶点的名称,链域用于指向链表中第一个结点(与顶点邻接的第一个顶点)

    (2)边表:包括邻接点域(指示与顶点邻接的点在图中的位置,即数组下标)、数据域(存储和边相关的信息,如权值)、链域(指示与顶点邻接的下一条边的结点)

    表头结点表:
    在这里插入图片描述
    边表:
    在这里插入图片描述

    无向图的邻接表

    在这里插入图片描述

    特点:

    1. 邻接表不唯一(边表顺序可以互换)
    2. 无向图中有n个顶点、e条边,则其邻接表需n个头结点和2e个边结点,复杂度为O(n+2e)<O(n^2),所以适合存储稀疏图
    3. 无向图中顶点Vi的度为第i个单链表中的结点数。

    有向图的邻接表

    在这里插入图片描述
    特点:

    1. 顶点vi的出度为第i个单链表中的结点个数
    2. 顶点vi的入度为整个单链表中邻接点域值是i-1的结点个数(需要遍历整个整个邻接表,较麻烦)。

    为了便于确定顶点的入度,可以建立一个有向图的逆邻接表,即对每个顶点vi建立一个链接所以进入vi的边的表

    有向图的逆邻接表

    与上图同步

    在这里插入图片描述
    特点:

    1. 顶点vi的入度为第i个单链表中的结点个数
    2. 顶点vi的出度为整个单链表中邻接点域值是i-1的结点个数

    此时我们很容易就可以算出某个顶点的入度或出度是多少,判断两顶点是否存在弧也很容易实现。

    二、图的邻接表存储表示

    //边的结点结构
    #define MVNum 100 //最大顶点数
    typedef struct ArcNode{
     	int adjvex;  //该边所指向的顶点的位置 
     	struct ArcNode *nextarc;//指向下一条边的指针 
     	Otherinfo info;  //和边相关的信息 
    }ArcNode;
    
    //顶点的结点结构 
    typedef struct VNode{
     	VerTexType data;//顶点信息、
     	ArcNode *firstarc;//指向第一条依附该顶点的边的指针 
    }VNode,AdjList[MVNum];//AdjList表示邻接表类型
    
    //图的结构定义 
    typedef struct{
     	AdjList vertices; //定义一个数组vertices,是vertex的复数形式
     	int vexnum,arcnum; //图的当前顶点数和弧数
    }ALGraph;
    
    

    三、采用邻接表表示法创建无向网

    //创建无向图G 
    bool CreateUDG(ALGraph &G){ 
     	int i,j,k,v1,v2;
     	cin>>G.vexnum>>G.arcnum;//输入总顶点数,总边数
     	for(i=0;i<G.vexnum;i++){//输入各顶点,构造表头结点表 
      	cin>>G.vertices[i].data;//输入顶点值 
      	G.vertices[i].firstarc=NULL;//初始化表头结点的指针域
     }//for
     //输入各边,构造邻接表
     	for(k=0;k<G.arcnum;k++){
     	cin>>v1>>v2;    //输入一条边依附的两个顶点 
     	i=LocateVex(G,v1);
     	j=LocateVex(G,v2); //确定顶点在G.vertices中的序号
     	ArcNode *p1=new ArcNode;  //生成一个新的边结点*p1
      	p1->adjvex=j;  //邻接点序号为j 
      //头插法将新结点*p1插入顶点vi的边表头部 
     	p1->nextarc=G.vertices[i].firstarc;
     	G.vertices[i].firstarc=p1; 
     	ArcNode *p2=new ArcNode;
     	p2->adjvex=i;  //邻接点序号为i
     	//头插法插入p2 ,因为是无向网,所以是两条 
     	p2->nextarc=G.vertices[i].firstarc;
     	G.vertices[i].firstarc=p2; 
     }//for
      return true; 
    }//CreateUDG
    

    算法时间复杂度是O(n+e);

    int LocateVex(ALGraph G,VerTexType u){
     //在图G中查找顶点u,存在则返回顶点表中的下标;否则返回-1
     	int i;
     	for(i=0;i<G.vexnum;i++)
      	if(u==G.vertices[i])
       		return i;
      	return -1;
    } 
    
    

    注意:一个图的邻接矩阵表示是唯一的,但其邻接表表示不唯一,这是因为邻接表表示中,各边表结点的链接次序取决于建立邻接表的算法,以及边的输入次序

    代码实现此邻接表:

    在这里插入图片描述

    #include<iostream>
    #include<queue>
    using namespace std; 
    #define MVNum 100 //最大顶点数
    
    typedef struct ArcNode{
     	int adjvex;  //该边所指向的顶点的位置 
     	struct ArcNode *nextarc;//指向下一条边的指针 
    }ArcNode;
    
    //顶点的结点结构 
    typedef struct VNode{
     	char data;//顶点信息、
     	ArcNode *firstarc;//指向第一条依附该顶点的边的指针 
    }VNode,AdjList[MVNum];//AdjList表示邻接表类型
    
    
    //图的结构定义 
    typedef struct{
     	AdjList vertices; //定义一个数组vertices,是vertex的复数形式
     	int vexnum,arcnum; //图的当前顶点数和弧数
    }ALGraph;
    
    int LocateVex(ALGraph G,int u){
     //在图G中查找顶点u,存在则返回顶点表中的下标;否则返回-1
     	int i;
     	for(i=1;i<=G.vexnum;i++)
      	if(u == G.vertices[i].data)
       		return i;
      	return -1;
    } 
    
    //创建无向图G 
    bool CreateUDG(ALGraph &G){ 
     	
    
     	cout << "请输入总结点数和总边数:" << endl; 
     	cin>>G.vexnum>>G.arcnum;//输入总顶点数,总边数
     	cout << " 输入各顶点值: " << endl; 
     	for(int i = 1;i <= G.vexnum;i++)
    	{//输入各顶点,构造表头结点表 
      		cin>>G.vertices[i].data;//输入顶点值 
      		G.vertices[i].firstarc=NULL;//初始化表头结点的指针域
    	}//for
    	getchar();
     	//输入各边,构造邻接表
     
     	cout << "输入一条边依附的两个顶点值"<<endl; 
     	for(int k=1;k<=G.arcnum;k++){
     	char v1,v2;
     	cin>>v1>>v2;    //输入一条边依附的两个顶点 
     	getchar();
     	
     	int i=LocateVex(G,v1);
     	int j=LocateVex(G,v2); //确定顶点在G.vertices中的序号
     	ArcNode *p1=new ArcNode;  //生成一个新的边结点*p1
      	p1->adjvex=j;  //邻接点序号为j 
      //头插法将新结点*p1插入顶点vi的边表头部 
     	p1->nextarc=G.vertices[i].firstarc;
     	G.vertices[i].firstarc=p1; 
     	ArcNode *p2=new ArcNode;
     	p2->adjvex=i;  //邻接点序号为i
     	//头插法插入p2 ,因为是无向网,所以是两条 
     	p2->nextarc=G.vertices[j].firstarc;
     	G.vertices[j].firstarc=p2; 
     }//for
      return true; 
    }//CreateUDG
    
    
    
    int main()
    {
    	ALGraph G;
    	ArcNode *p;
    	CreateUDG(G);
    	
    	cout << "输出邻接表: " <<endl;
    	
    	for(int i = 1; i<= G.vexnum; i++)
    	{
    		cout << G.vertices[i].data;
    		for(p = G.vertices[i].firstarc; p != NULL; p = p->nextarc)
    			printf("->%d", p->adjvex);
    		cout << endl; 
    	} 
    		return 0;
    }
    
    

    在这里插入图片描述

    邻接表表示法优缺点:
    (1)优点

    1. 便于增加和删除顶点。
    2. 便于统计边的数目,时间复杂度是O(n+e)
    3. 空间效率高

    (2)缺点

    1. 不便于判断顶点之间是否有边
    2. 不便于计算有向图各顶点的度
    展开全文
  • 邻接表的定义 肝动了睡觉去了。。。 邻接表的优缺点 邻接表的存储结构 邻接表的代码实现

    邻接表表示法(链式)

    存储定义:

    • 顶点:按编号顺序将顶点数据存储在一维数组中
    • 关联同一顶点的边(以顶点为尾的弧):用线性链表存储

    无向图的邻接表

    例如,如下无向图

    请添加图片描述

    则它的邻接表为

    请添加图片描述

    无向图邻接表的特点:

    • 邻接表不唯一
    • 若无向图中有 n 个顶点,e 条边,则其邻接表需要 n 个头结点和 2e 个表节点,适宜存稀疏图。
    • 无向图中顶点 Vi 的度为第 i 个单链表中的节点数。
    • 存储空间 n + 2e

    有向图的邻接表

    如下有向图

    请添加图片描述
    则它的邻接矩阵为

    请添加图片描述

    它的逆邻接矩阵为

    请添加图片描述
    有向图邻接表的特点:

    • 顶点 Vi 的出度为第 i 个单链表中结点个数
    • 顶点 Vi 的入度为整个单链表中邻接点域值是 i - 1 的节点个数
    • 找出度易,找入度难

    有向图逆邻接表的特点:

    • 顶点 Vi 的入度为第 i 个单链表中结点个数
    • 顶点 Vi 的出度为整个单链表中邻接点域值是 i - 1 的节点个数
    • 找入度易,找出度难

    邻接表的特点

    • 方便找任一顶点的所有邻接点
    • 节约稀疏图的空间
      • 需要 N 个头指针 + 2E 个结点(每个结点至少2个域)
    • 计算任一顶点的度
      • 无向图:方便
      • 有向图:只能计算 出度;需要构造 逆邻接表 来方便计算 入度
    • 不方便检查任意一对顶点间是否存在边

    邻接矩阵和邻接表的关系

    联系:

    • 邻接表中每个链表对应邻接矩阵中的一行,链表中结点个数等于一行中非零元素的个数

    区别:

    • 对于任意确定的无向图,邻接矩阵是唯一的(行列号与顶点编号一致),但邻接表不唯一(链接次序与顶点编号无关)

    • 邻接矩阵的空间复杂度为O(n²),而邻接表的空间复杂度为 O(n+e)

    用途:

    • 邻接矩阵多用于稠密图;而邻接表多用于稀疏图。

    邻接表的存储方式

    
    typedef int InfoType;              // 网的权值类型
    typedef char VertexType[MAX_NAME]; // 顶点类型为字符串
    
    enum GraphKind
    {
        DG,
        DN,
        UDG,
        UDN
    }; // {有向图,有向网,无向图,无向网}
    
    struct ElemType
    {
        int adjvex;     // 该弧所指向的顶点的位置
        InfoType *info; // 网的权值指针
    };
    
    struct ArcNode
    {
        struct ElemType data;    // 除指针以外的部分都属于ElemType
        struct ArcNode *nextarc; // 指向下一条弧的指针
    };                           // 表结点
    typedef struct
    {
        VertexType data;              // 顶点信息
        struct ArcNode *firstarc;     // 第一个表结点的地址,指向第一条依附该顶点的弧的指针
    } VNode, AdjList[MAX_VERTEX_NUM]; // 头结点
    
    struct ALGraph
    {
        AdjList vertices;
        int vexnum, arcnum;  // 图的当前顶点数和弧数
        enum GraphKind kind; // 图的种类标志
    };
    
    

    邻接表的代码实现

    main.c

    /*
     * Change Logs:
     * Date           Author       Notes
     * 2021-08.03     tyustli      first version
     */
    
    #include "graph.h"
    
    void visit(VertexType i)
    {
        printf("%s ", i);
    }
    
    int main(int argc, char *argv[])
    {
        int i, j, k, n;
        struct ALGraph g;
        VertexType v1, v2;
        printf("请顺序选择有向图,有向网,无向图,无向网\n");
    
        printf("this is graph\r\n");
    
        CreateGraphF(&g);
        Display(g);
        DFSTraverse(g, visit);
        BFSTraverse(g, visit);
    
        return 1;
    }
    /*
    编译:make
    运行:./obj
    结果:
    请顺序选择有向图,有向网,无向图,无向网
    this is graph
    请输入数据文件名(f7-1.txt或f7-2.txt):graph.txt
    请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): 2
    无向图
    8个顶点:
    a b c d e f g h
    14条弧(边):
    a→h a→g a→f a→e a→c a→b
    b→h b→e b→d
    c→h c→g
    d→h
    e→f
    f→g
    
    
    a h d b e f g c
    a h g f e c b d
    */
    /************************ end of file **************************/
    
    

    makefile

    objects  = main.o graph.o
    obj: $(objects)
    	cc -o obj $(objects) -lm
    
    main.o : graph.h
    graph.o : graph.h
    
    .PHONY : clean
    clean :
    	-rm obj $(objects)
    
    

    graph.h

    /*
     * Change Logs:
     * Date           Author       Notes
     * 2021-08.03     tyustli      first version
     */
    
    #include <string.h>
    #include <ctype.h>
    #include <malloc.h> // malloc()等
    #include <limits.h> // INT_MAX等
    #include <stdio.h>  // EOF(=^Z或F6),NULL
    #include <stdlib.h> // atoi()
    
    // 函数结果状态代码
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1
    #define OVERFLOW -2
    typedef int Status;  // Status是函数的类型,其值是函数结果状态代码,如OK等
    typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
    
    #define MAX_VERTEX_NUM 20
    #define MAX_NAME 3 // 顶点字符串的最大长度+1
    
    typedef int InfoType;              // 网的权值类型
    typedef char VertexType[MAX_NAME]; // 顶点类型为字符串
    
    enum GraphKind
    {
        DG,
        DN,
        UDG,
        UDN
    }; // {有向图,有向网,无向图,无向网}
    
    struct ElemType
    {
        int adjvex;     // 该弧所指向的顶点的位置
        InfoType *info; // 网的权值指针
    };
    
    struct ArcNode
    {
        struct ElemType data;    // 除指针以外的部分都属于ElemType
        struct ArcNode *nextarc; // 指向下一条弧的指针
    };                           // 表结点
    typedef struct
    {
        VertexType data;              // 顶点信息
        struct ArcNode *firstarc;     // 第一个表结点的地址,指向第一条依附该顶点的弧的指针
    } VNode, AdjList[MAX_VERTEX_NUM]; // 头结点
    
    struct ALGraph
    {
        AdjList vertices;
        int vexnum, arcnum;  // 图的当前顶点数和弧数
        enum GraphKind kind; // 图的种类标志
    };
    
    #define LNode struct ArcNode      // 定义单链表的结点类型是图的表结点的类型
    #define next nextarc              // 定义单链表结点的指针域是表结点指向下一条弧的指针域
    typedef struct ArcNode *LinkList; // 定义指向单链表结点的指针是指向图的表结点的指针
    
    void CreateGraph(struct ALGraph *G);
    void CreateGraphF(struct ALGraph *G);
    void Display(struct ALGraph G);
    void DFSTraverse(struct ALGraph G, void (*Visit)(char *));
    void BFSTraverse(struct ALGraph G, void (*Visit)(char *));
    
    /************************ end of file **************************/
    
    

    graph.c

    /*
     * Change Logs:
     * Date           Author       Notes
     * 2021-08.03     tyustli      first version
     */
    
    #include "graph.h"
    
    #if 1
    // 不带头结点的单链表的部分基本操作 邻接表中会用到链表的插入等操作
    #define DestroyList ClearList // DestroyList()和ClearList()的操作是一样的
    void InitList(LinkList *L)
    {
        *L = NULL; // 指针为空
    }
    void ClearList(LinkList *L)
    { // 初始条件:线性表L已存在。操作结果:将L重置为空表
        LinkList p;
        while (*L) // L不空
        {
            p = *L;          // p指向首元结点
            *L = (*L)->next; // L指向第2个结点(新首元结点)
            free(p);         // 释放首元结点
        }
    }
    Status ListEmpty(LinkList L)
    { // 初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE
        if (L)
            return FALSE;
        else
            return TRUE;
    }
    int ListLength(LinkList L)
    { // 初始条件:线性表L已存在。操作结果:返回L中数据元素个数
        int i = 0;
        LinkList p = L;
        while (p) // p指向结点(没到表尾)
        {
            p = p->next; // p指向下一个结点
            i++;
        }
        return i;
    }
    Status GetElem(LinkList L, int i, struct ElemType *e)
    {
        int j = 1;
        LinkList p = L;
        if (i < 1) // i值不合法
            return ERROR;
        while (j < i && p) // 没到第i个元素,也没到表尾
        {
            j++;
            p = p->next;
        }
        if (j == i) // 存在第i个元素
        {
            *e = p->data;
            return OK;
        }
        else
            return ERROR;
    }
    int LocateElem(LinkList L, struct ElemType e, Status (*compare)(struct ElemType, struct ElemType))
    {
        int i = 0;
        LinkList p = L;
        while (p)
        {
            i++;
            if (compare(p->data, e)) // 找到这样的数据元素
                return i;
            p = p->next;
        }
        return 0;
    }
    
    Status ListInsert(LinkList *L, int i, struct ElemType e)
    { // 在不带头结点的单链线性表L中第i个位置之前插入元素e
        int j = 1;
        LinkList p = *L, s;
        if (i < 1) // i值不合法
            return ERROR;
        s = (LinkList)malloc(sizeof(LNode)); // 生成新结点
        s->data = e;                         // 给s的data域赋值
        if (i == 1)                          // 插在表头
        {
            s->next = *L;
            *L = s; // 改变L
        }
        else
        {                          // 插在表的其余处
            while (p && j < i - 1) // 寻找第i-1个结点
            {
                p = p->next;
                j++;
            }
            if (!p) // i大于表长+1
                return ERROR;
            s->next = p->next;
            p->next = s;
        }
        return OK;
    }
    Status ListDelete(LinkList *L, int i, struct ElemType *e)
    { // 在不带头结点的单链线性表L中,删除第i个元素,并由e返回其值
        int j = 1;
        LinkList p = *L, q;
        if (i == 1) // 删除第1个结点
        {
            *L = p->next; // L由第2个结点开始
            *e = p->data;
            free(p); // 删除并释放第1个结点
        }
        else
        {
            while (p->next && j < i - 1) // 寻找第i个结点,并令p指向其前趋
            {
                p = p->next;
                j++;
            }
            if (!p->next || j > i - 1) // 删除位置不合理
                return ERROR;
            q = p->next; // 删除并释放结点
            p->next = q->next;
            *e = q->data;
            free(q);
        }
        return OK;
    }
    
    LinkList Point(LinkList L, struct ElemType e, Status (*equal)(struct ElemType, struct ElemType), LinkList *p)
    { // 查找表L中满足条件的结点。如找到,返回指向该结点的指针,p指向该结点的前驱(若该结点是
        // 首元结点,则p=NULL)。如表L中无满足条件的结点,则返回NULL,p无定义。
        // 函数equal()的两形参的关键字相等,返回OK;否则返回ERROR
        int i, j;
        i = LocateElem(L, e, equal);
        if (i) // 找到
        {
            if (i == 1) // 是首元结点
            {
                *p = NULL;
                return L;
            }
            *p = L;
            for (j = 2; j < i; j++)
                *p = (*p)->next;
            return (*p)->next;
        }
        return NULL; // 没找到
    }
    
    Status DeleteElem(LinkList *L, struct ElemType *e, Status (*equal)(struct ElemType, struct ElemType))
    { // 删除表L中满足条件的结点,并返回TRUE;如无此结点,则返回FALSE。
        // 函数equal()的两形参的关键字相等,返回OK;否则返回ERROR
        LinkList p, q;
        q = Point(*L, *e, equal, &p);
        if (q) // 找到此结点,且q指向该结点
        {
            if (p)                    // 该结点不是首元结点,p指向其前驱
                ListDelete(&p, 2, e); // 将p作为头指针,删除第2个结点
            else                      // 该结点是首元结点
                ListDelete(L, 1, e);
            return TRUE;
        }
        return FALSE;
    }
    
    void ListTraverse(LinkList L, void (*vi)(struct ElemType))
    { // 初始条件:线性表L已存在。操作结果:依次对L的每个数据元素调用函数vi()
        LinkList p = L;
        while (p)
        {
            vi(p->data);
            p = p->next;
        }
        printf("\n");
    }
    #endif
    
    // 图的邻接表存储的基本操作
    
    // 初始条件:图 G 存在,u 和 G 中顶点有相同特征
    // 操作结果:若 G 中存在顶点 u,则返回该顶点在图中位置;否则返回 -1
    int LocateVex(struct ALGraph G, VertexType u)
    {
        int i;
        for (i = 0; i < G.vexnum; ++i)
            if (strcmp(u, G.vertices[i].data) == 0)
                return i;
        return -1;
    }
    
    // 采用邻接表存储结构,构造没有相关信息图或网G(用一个函数构造4种图)
    
    void CreateGraph(struct ALGraph *G)
    {                      // 采用邻接表存储结构,构造没有相关信息图或网G(用一个函数构造4种图)
        int i, j, k, w;    // w是权值
        VertexType va, vb; // 连接边或弧的2顶点
        struct ElemType e;
        printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
        scanf("%d", (int *)&G->kind);
        printf("请输入图的顶点数,边数: ");
        scanf("%d,%d", &G->vexnum, &G->arcnum);
        printf("请输入%d个顶点的值(<%d个字符):\n", G->vexnum, MAX_NAME);
        for (i = 0; i < G->vexnum; ++i) // 构造顶点向量
        {
            scanf("%s", G->vertices[i].data);
            G->vertices[i].firstarc = NULL; // 初始化与该顶点有关的出弧链表
        }
        if (G->kind % 2) // 网
            printf("请输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
        else // 图
            printf("请输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
        for (k = 0; k < G->arcnum; ++k) // 构造相关弧链表
        {
            if (G->kind % 2) // 网
                scanf("%d%s%s", &w, va, vb);
            else // 图
                scanf("%s%s", va, vb);
            i = LocateVex(*G, va); // 弧尾
            j = LocateVex(*G, vb); // 弧头
            e.info = NULL;         // 给待插表结点e赋值,图无权
            e.adjvex = j;          // 弧头
            if (G->kind % 2)       // 网
            {
                e.info = (int *)malloc(sizeof(int)); // 动态生成存放权值的空间
                *(e.info) = w;
            }
            ListInsert(&G->vertices[i].firstarc, 1, e); // 插在第i个元素(出弧)的表头,在bo2-8.cpp中
            if (G->kind >= 2)                           // 无向图或网,产生第2个表结点,并插在第j个元素(入弧)的表头
            {
                e.adjvex = i;                               // e.info不变,不必再赋值
                ListInsert(&G->vertices[j].firstarc, 1, e); // 插在第j个元素的表头,在bo2-8.cpp中
            }
        }
    }
    
    // 采用邻接表存储结构,由文件构造没有相关信息图或网G(用一个函数构造4种图)
    void CreateGraphF(struct ALGraph *G)
    {
        int i, j, k, w;    // w是权值
        VertexType va, vb; // 连接边或弧的2顶点
        struct ElemType e;
        char filename[13];
        FILE *graphlist;
        printf("请输入数据文件名(f7-1.txt或f7-2.txt):");
        scanf("%s", filename);
        printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
        scanf("%d", (int *)&G->kind);
        graphlist = fopen(filename, "r"); // 以读的方式打开数据文件,并以graphlist表示
        fscanf(graphlist, "%d", &G->vexnum);
        fscanf(graphlist, "%d", &G->arcnum);
        for (i = 0; i < G->vexnum; ++i) // 构造顶点向量
        {
            fscanf(graphlist, "%s", G->vertices[i].data);
            G->vertices[i].firstarc = NULL; // 初始化与该顶点有关的出弧链表
        }
        for (k = 0; k < G->arcnum; ++k) // 构造相关弧链表
        {
            if (G->kind % 2) // 网
                fscanf(graphlist, "%d%s%s", &w, va, vb);
            else // 图
                fscanf(graphlist, "%s%s", va, vb);
            i = LocateVex(*G, va); // 弧尾
            j = LocateVex(*G, vb); // 弧头
            e.info = NULL;         // 给待插表结点e赋值,图无权
            e.adjvex = j;          // 弧头
            if (G->kind % 2)       // 网
            {
                e.info = (int *)malloc(sizeof(int)); // 动态生成存放权值的空间
                *(e.info) = w;
            }
            ListInsert(&G->vertices[i].firstarc, 1, e); // 插在第i个元素(出弧)的表头,在bo2-8.cpp中
            if (G->kind >= 2)                           // 无向图或网,产生第2个表结点,并插在第j个元素(入弧)的表头
            {
                e.adjvex = i;                               // e.info不变,不必再赋值
                ListInsert(&G->vertices[j].firstarc, 1, e); // 插在第j个元素的表头,在bo2-8.cpp中
            }
        }
        fclose(graphlist); // 关闭数据文件
    }
    
    void DestroyGraph(struct ALGraph *G)
    { // 初始条件:图G存在。操作结果:销毁图G
        int i;
        struct ElemType e;
        for (i = 0; i < G->vexnum; ++i)         // 对于所有顶点
            if (G->kind % 2)                    // 网
                while (G->vertices[i].firstarc) // 对应的弧或边链表不空
                {
                    ListDelete(&G->vertices[i].firstarc, 1, &e); // 删除链表的第1个结点,并将值赋给e
                    if (e.adjvex > i)                            // 顶点序号>i(保证动态生成的权值空间只释放1次)
                        free(e.info);
                }
            else                                       // 图
                DestroyList(&G->vertices[i].firstarc); // 销毁弧或边链表,在bo2-8.cpp中
        G->vexnum = 0;                                 // 顶点数为0
        G->arcnum = 0;                                 // 边或弧数为0
    }
    
    // 初始条件:图G存在,v是G中某个顶点的序号。操作结果:返回v的值
    VertexType *GetVex(struct ALGraph G, int v)
    {
        if (v >= G.vexnum || v < 0)
            exit(ERROR);
        return G.vertices[v].data;
    }
    
    // 初始条件:图G存在,v是G中某个顶点。操作结果:对v赋新值value
    Status PutVex(struct ALGraph *G, VertexType v, VertexType value)
    {
        int i;
        i = LocateVex(*G, v);
        if (i > -1) // v是G的顶点
        {
            strcpy(G->vertices[i].data, value);
            return OK;
        }
        return ERROR;
    }
    
    // 初始条件:图G存在,v是G中某个顶点
    // 操作结果:返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1
    int FirstAdjVex(struct ALGraph G, VertexType v)
    {
        struct ArcNode *p;
        int v1;
        v1 = LocateVex(G, v); // v1为顶点v在图G中的序号
        p = G.vertices[v1].firstarc;
        if (p)
            return p->data.adjvex;
        else
            return -1;
    }
    
    // DeleteArc()、DeleteVex()和NextAdjVex()要调用的函数
    Status equalvex(struct ElemType a, struct ElemType b)
    {
        if (a.adjvex == b.adjvex)
            return OK;
        else
            return ERROR;
    }
    
    // 初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点
    // 操作结果:返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个邻接点,则返回-1
    int NextAdjVex(struct ALGraph G, VertexType v, VertexType w)
    {
        LinkList p, p1; // p1在Point()中用作辅助指针,Point()在func2-1.cpp中
        struct ElemType e;
        int v1;
        v1 = LocateVex(G, v);                                 // v1为顶点v在图G中的序号
        e.adjvex = LocateVex(G, w);                           // e.adjvex为顶点w在图G中的序号
        p = Point(G.vertices[v1].firstarc, e, equalvex, &p1); // p指向顶点v的链表中邻接顶点为w的结点
        if (!p || !p->next)                                   // 没找到w或w是最后一个邻接点
            return -1;
        else                             // p->data.adjvex==w
            return p->next->data.adjvex; // 返回v的(相对于w的)下一个邻接顶点的序号
    }
    
    // 初始条件:图G存在,v和图中顶点有相同特征
    // 操作结果:在图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做)
    void InsertVex(struct ALGraph *G, VertexType v)
    {
        strcpy(G->vertices[G->vexnum].data, v); // 构造新顶点向量
        G->vertices[G->vexnum].firstarc = NULL;
        G->vexnum++; // 图G的顶点数加1
    }
    
    // 初始条件:图G存在,v是G中某个顶点。操作结果:删除G中顶点v及其相关的弧
    Status DeleteVex(struct ALGraph *G, VertexType v)
    {
        int i, j, k;
        struct ElemType e;
        LinkList p, p1;
        j = LocateVex(*G, v); // j是顶点v的序号
        if (j < 0)            // v不是图G的顶点
            return ERROR;
        i = ListLength(G->vertices[j].firstarc); // 以v为出度的弧或边数,在bo2-8.cpp中
        G->arcnum -= i;                          // 边或弧数-i
        if (G->kind % 2)                         // 网
            while (G->vertices[j].firstarc)      // 对应的弧或边链表不空
            {
                ListDelete(&G->vertices[j].firstarc, 1, &e); // 删除链表的第1个结点,并将值赋给e
                free(e.info);                                // 释放动态生成的权值空间
            }
        else                                       // 图
            DestroyList(&G->vertices[j].firstarc); // 销毁弧或边链表,在bo2-8.cpp中
        G->vexnum--;                               // 顶点数减1
        for (i = j; i < G->vexnum; i++)            // 顶点v后面的顶点前移
            G->vertices[i] = G->vertices[i + 1];
        for (i = 0; i < G->vexnum; i++) // 删除以v为入度的弧或边且必要时修改表结点的顶点位置值
        {
            e.adjvex = j;
            p = Point(G->vertices[i].firstarc, e, equalvex, &p1); // Point()在func2-1.cpp中
            if (p)                                                // 顶点i的邻接表上有v为入度的结点
            {
                if (p1)                                // p1指向p所指结点的前驱
                    p1->next = p->next;                // 从链表中删除p所指结点
                else                                   // p指向首元结点
                    G->vertices[i].firstarc = p->next; // 头指针指向下一结点
                if (G->kind < 2)                       // 有向
                {
                    G->arcnum--;            // 边或弧数-1
                    if (G->kind == 1)       // 有向网
                        free(p->data.info); // 释放动态生成的权值空间
                }
                free(p); // 释放v为入度的结点
            }
            for (k = j + 1; k <= G->vexnum; k++) // 对于adjvex域>j的结点,其序号-1
            {
                e.adjvex = k;
                p = Point(G->vertices[i].firstarc, e, equalvex, &p1); // Point()在func2-1.cpp中
                if (p)
                    p->data.adjvex--; // 序号-1(因为前移)
            }
        }
        return OK;
    }
    
    // 初始条件:图G存在,v和w是G中两个顶点
    // 操作结果:在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v>
    Status InsertArc(struct ALGraph *G, VertexType v, VertexType w)
    {
        struct ElemType e;
        int i, j;
        i = LocateVex(*G, v); // 弧尾或边的序号
        j = LocateVex(*G, w); // 弧头或边的序号
        if (i < 0 || j < 0)
            return ERROR;
        G->arcnum++; // 图G的弧或边的数目加1
        e.adjvex = j;
        e.info = NULL;   // 初值
        if (G->kind % 2) // 网
        {
            e.info = (int *)malloc(sizeof(int)); // 动态生成存放权值的空间
            printf("请输入弧(边)%s→%s的权值: ", v, w);
            scanf("%d", e.info);
        }
        ListInsert(&G->vertices[i].firstarc, 1, e); // 将e插在弧尾的表头,在bo2-8.cpp中
        if (G->kind >= 2)                           // 无向,生成另一个表结点
        {
            e.adjvex = i;                               // e.info不变
            ListInsert(&G->vertices[j].firstarc, 1, e); // 将e插在弧头的表头
        }
        return OK;
    }
    
    // 初始条件:图G存在,v和w是G中两个顶点
    // 操作结果:在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v>
    Status DeleteArc(struct ALGraph *G, VertexType v, VertexType w)
    {
        int i, j;
        Status k;
        struct ElemType e;
        i = LocateVex(*G, v); // i是顶点v(弧尾)的序号
        j = LocateVex(*G, w); // j是顶点w(弧头)的序号
        if (i < 0 || j < 0 || i == j)
            return ERROR;
        e.adjvex = j;
        k = DeleteElem(&G->vertices[i].firstarc, &e, equalvex); // 在func2-1.cpp中
        if (k)                                                  // 删除成功
        {
            G->arcnum--;     // 弧或边数减1
            if (G->kind % 2) // 网
                free(e.info);
            if (G->kind >= 2) // 无向,删除对称弧<w,v>
            {
                e.adjvex = i;
                DeleteElem(&G->vertices[j].firstarc, &e, equalvex);
            }
            return OK;
        }
        else // 没找到待删除的弧
        {
            return ERROR;
        }
    }
    
    Boolean visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)
    void (*VisitFunc)(char *v);      // 函数变量(全局量)
    // 从第v个顶点出发递归地深度优先遍历图G。算法7.5
    void DFS(struct ALGraph G, int v)
    {
        int w;
        visited[v] = TRUE;             // 设置访问标志为TRUE(已访问)
        VisitFunc(G.vertices[v].data); // 访问第v个顶点
        for (w = FirstAdjVex(G, G.vertices[v].data); w >= 0; w = NextAdjVex(G, G.vertices[v].data, G.vertices[w].data))
            if (!visited[w])
                DFS(G, w); // 对v的尚未访问的邻接点w递归调用DFS
    }
    
    // 对图G作深度优先遍历。算法7.4
    void DFSTraverse(struct ALGraph G, void (*Visit)(char *))
    {
        int v;
        VisitFunc = Visit; // 使用全局变量VisitFunc,使DFS不必设函数指针参数
        for (v = 0; v < G.vexnum; v++)
            visited[v] = FALSE; // 访问标志数组初始化
        for (v = 0; v < G.vexnum; v++)
            if (!visited[v])
                DFS(G, v); // 对尚未访问的顶点调用DFS
        printf("\n");
    }
    
    typedef int QElemType; // 队列元素类型
    
    #if 1
    typedef struct QNode
    {
        QElemType data;     /* 数据域 */
        struct QNode *next; /* 指针域 */
    } QNode, *QueuePtr;
    typedef struct LinkQueue
    {
        QueuePtr front; // 队头指针
        QueuePtr rear;  // 队尾指针
    } LinkQueue;
    void InitQueue(LinkQueue *Q);
    void DestroyQueue(LinkQueue *Q);
    void ClearQueue(LinkQueue *Q);
    Status QueueEmpty(LinkQueue Q);
    int QueueLength(LinkQueue Q);
    Status GetHead(LinkQueue Q, QElemType *e);
    void EnQueue(LinkQueue *Q, QElemType e);
    Status DeQueue(LinkQueue *Q, QElemType *e);
    void QueueTraverse(LinkQueue Q, void (*vi)(QElemType));
    void print(QElemType i);
    void InitQueue(LinkQueue *Q)
    {                                                         // 构造一个空队列 Q
        Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode)); /* 单链表的头结点 */
    
        if (Q->front == NULL)
            exit(-1);
        Q->front->next = NULL;
    }
    void DestroyQueue(LinkQueue *Q)
    {
        while (Q->front)
        {
            Q->rear = Q->front->next;
            free(Q->front);
            Q->front = Q->rear;
        }
    }
    void ClearQueue(LinkQueue *Q)
    {
        QueuePtr p, q;
        Q->rear = Q->front;
        p = Q->front->next;
        Q->front->next = NULL;
        while (p)
        {
            q = p;
            p = p->next;
            free(q);
        }
    }
    Status QueueEmpty(LinkQueue Q)
    {
        if (Q.front->next == NULL)
            return TRUE;
        else
            return FALSE;
    }
    int QueueLength(LinkQueue Q)
    {
        int i = 0;
        QueuePtr p;
        p = Q.front;
        while (Q.rear != p)
        {
            i++;
            p = p->next;
        }
        return i;
    }
    Status GetHead(LinkQueue Q, QElemType *e)
    {
        QueuePtr p;
        if (Q.front == Q.rear)
            return ERROR;
        p = Q.front->next;
        *e = p->data;
    
        return OK;
    }
    void EnQueue(LinkQueue *Q, QElemType e)
    {
        QueuePtr p;
        if (!(p = (QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败
            exit(-1);
        p->data = e;
        p->next = NULL;    /* 新结点的 next 为空 */
        Q->rear->next = p; /* 上一次的尾指针指向新的结点 */
        Q->rear = p;       /* 新的尾指针 */
    }
    Status DeQueue(LinkQueue *Q, QElemType *e)
    {
        QueuePtr p;
        if (Q->front == Q->rear)
            return ERROR;
        p = Q->front->next;
        *e = p->data;
        Q->front->next = p->next;
        if (Q->rear == p)
            Q->rear = Q->front;
        free(p);
    
        return OK;
    }
    void QueueTraverse(LinkQueue Q, void (*vi)(QElemType))
    {
        QueuePtr p;
        p = Q.front->next;
        while (p)
        {
            vi(p->data);
            p = p->next;
        }
        printf("\n");
    }
    
    void print(QElemType i)
    {
        // printf("%s ", i);
    }
    #endif
    
    //按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。算法7.6
    void BFSTraverse(struct ALGraph G, void (*Visit)(char *))
    {
        int v, u, w;
        LinkQueue Q;
        for (v = 0; v < G.vexnum; ++v)
            visited[v] = FALSE;        // 置初值
        InitQueue(&Q);                 // 置空的辅助队列Q
        for (v = 0; v < G.vexnum; v++) // 如果是连通图,只v=0就遍历全图
            if (!visited[v])           // v尚未访问
            {
                visited[v] = TRUE;
                Visit(G.vertices[v].data);
                EnQueue(&Q, v);        // v入队列
                while (!QueueEmpty(Q)) // 队列不空
                {
                    DeQueue(&Q, &u); // 队头元素出队并置为u
                    for (w = FirstAdjVex(G, G.vertices[u].data); w >= 0; w = NextAdjVex(G, G.vertices[u].data, G.vertices[w].data))
                        if (!visited[w]) // w为u的尚未访问的邻接顶点
                        {
                            visited[w] = TRUE;
                            Visit(G.vertices[w].data);
                            EnQueue(&Q, w); // w入队
                        }
                }
            }
        printf("\n");
    }
    
    // 从第v个顶点出发递归地深度优先遍历图G。仅适用于邻接表存储结构
    void DFS1(struct ALGraph G, int v, void (*Visit)(char *))
    {
        struct ArcNode *p;                               // p指向表结点
        visited[v] = TRUE;                               // 设置访问标志为TRUE(已访问)
        Visit(G.vertices[v].data);                       // 访问该顶点
        for (p = G.vertices[v].firstarc; p; p = p->next) // p依次指向v的邻接顶点
            if (!visited[p->data.adjvex])
                DFS1(G, p->data.adjvex, Visit); // 对v的尚未访问的邻接点递归调用DFS1
    }
    
    // 对图G作深度优先遍历。DFS1设函数指针参数
    void DFSTraverse1(struct ALGraph G, void (*Visit)(char *))
    {
        int v;
        for (v = 0; v < G.vexnum; v++)
            visited[v] = FALSE;        // 访问标志数组初始化,置初值为未被访问
        for (v = 0; v < G.vexnum; v++) // 如果是连通图,只v=0就遍历全图
            if (!visited[v])           // v尚未被访问
                DFS1(G, v, Visit);     // 对v调用DFS1
        printf("\n");
    }
    
    // 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。仅适用于邻接表结构
    void BFSTraverse1(struct ALGraph G, void (*Visit)(char *))
    {
        int v, u;
        struct ArcNode *p; // p指向表结点
        LinkQueue Q;       // 链队列类型
        for (v = 0; v < G.vexnum; ++v)
            visited[v] = FALSE;        // 置初值为未被访问
        InitQueue(&Q);                 // 初始化辅助队列Q
        for (v = 0; v < G.vexnum; v++) // 如果是连通图,只v=0就遍历全图
            if (!visited[v])           // v尚未被访问
            {
                visited[v] = TRUE;         // 设v为已被访问
                Visit(G.vertices[v].data); // 访问v
                EnQueue(&Q, v);            // v入队列
                while (!QueueEmpty(Q))     // 队列不空
                {
                    DeQueue(&Q, &u);                                 // 队头元素出队并置为u
                    for (p = G.vertices[u].firstarc; p; p = p->next) // p依次指向u的邻接顶点
                        if (!visited[p->data.adjvex])                // u的邻接顶点尚未被访问
                        {
                            visited[p->data.adjvex] = TRUE;         // 该邻接顶点设为已被访问
                            Visit(G.vertices[p->data.adjvex].data); // 访问该邻接顶点
                            EnQueue(&Q, p->data.adjvex);            // 入队该邻接顶点序号
                        }
                }
            }
        printf("\n");
    }
    
    // 输出图的邻接矩阵G
    void Display(struct ALGraph G)
    {
        int i;
        struct ArcNode *p;
        switch (G.kind)
        {
        case DG:
            printf("有向图\n");
            break;
        case DN:
            printf("有向网\n");
            break;
        case UDG:
            printf("无向图\n");
            break;
        case UDN:
            printf("无向网\n");
        }
        printf("%d个顶点:\n", G.vexnum);
        for (i = 0; i < G.vexnum; ++i)
            printf("%s ", G.vertices[i].data);
        printf("\n%d条弧(边):\n", G.arcnum);
        for (i = 0; i < G.vexnum; i++)
        {
            p = G.vertices[i].firstarc;
            while (p)
            {
                if (G.kind <= 1 || i < p->data.adjvex) // 有向或无向两次中的一次
                {
                    printf("%s→%s ", G.vertices[i].data, G.vertices[p->data.adjvex].data);
                    if (G.kind % 2) // 网
                        printf(":%d ", *(p->data.info));
                }
                p = p->nextarc;
            }
            printf("\n");
        }
    }
    
    /************************ end of file **************************/
    
    
    展开全文
  • 注意:一个图所对应的邻接矩阵唯一,所对应的邻接表不唯一 一、邻接矩阵 邻接矩阵以矩阵的形式存储图所有顶点间的关系。邻接矩阵具有以下特点: 1.邻接矩阵是正矩阵,即横纵维数相等。 2.矩阵的每一行或一列代表一...
  • 图存储之邻接表

    2020-10-17 10:56:47
    当一个图稀疏图时,使用邻接矩阵法显然要让费大量的存储空间,而图的邻接表法结合了顺序存储和链式存储方法,大大减少了这种不必要的浪费。 二 邻接表 邻接表,是指对图G中的每个顶点vi建立一个单链表,第i个...
  • 邻接表法 图的邻接表(adjacency list)是一种顺序与链式存储相结合的存储方法。 对于含有n个顶点的图,每个顶点建立一个单链表,第i(0≤n-1)个单链表中的结点表示关联于顶点i的边(对有向图是以顶点i起点的边),也...
  • 上篇博客讲到,图状结构是非常复杂的结构,图也是非常复杂的,所以图的存储就是一个非常重要的部分,因为我们不仅要表示顶点集...邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。 设G=(V,E)是一个图,其中V={v1,v2...
  • 每个链表都配有头结点,头结点的数据域不为NULL,而是用于存储顶点本身的数据;后续链表中的各个结点存储的是当前顶点的所有邻接点。 所以,采用邻接表存储图时,有多少顶点就会构建多少个链表,为了便于管理这些...
  • 拓扑习惯用邻接表写,第一次用邻接矩阵,参照大神的思想   #include #include int n,k,flag; int in[30],ans[30],map[30][30]; void top_sort() { int mark,rec[30]; k=0;flag=2; for(int i=0;i;++i) rec...
  • 文章目录邻接表1、邻接表表示法2、无向图的邻接表3、有向图的邻接表4、练习5、邻接表的结构类型定义6、采用邻接表表示法创建无向网7、邻接表特点8、邻接矩阵与邻接表表示法的关系十字链表邻接多重表 邻接表 1、邻接...
  • 构造邻接表

    2017-10-15 22:50:47
    //构造邻接表 /* 1.如果G无向图,则所需存储空间O(|V|+2|E|); 2.如果G有向图,则所需存储空间O(|V|+|E|); 3.因为在邻接表中,无向图的每条边出现了两次(无向图的每...6.邻接表的表示不唯一,因为在构造某个
  • 图和树的存储方式:邻接矩阵和邻接表

    千次阅读 多人点赞 2020-02-17 02:28:17
    邻接矩阵和邻接表摘要无向图和有向图的区别稀疏图和稠密图邻接矩阵邻接矩阵的初始化邻接矩阵的读入邻接表 基础算法和数据结构合集: https://blog.csdn.net/GD_ONE/article/details/104061907 摘要 本文主要介绍邻接...
  • 假设图G=(V,E)有n 个确定的顶点,即V={v0,v1,…,vn-1},则表示G 中各顶点相邻关系一个n×n 的矩阵,矩阵的元素:   下面举个栗子: 代码实现如下: #include&lt;iostream&gt; using n...
  • 图是对象和对象之间存在的关系的有限集合。如果将对象表示顶点(或节点),将关系表示边,则可以得到以下两种图形: ...邻接表 邻接矩阵 让我们考虑一个图,其中有从0到N-1编号的N个顶点和(i,j)形式的E...
  • 前言 因为工作的需要深刻认识到了数据结构的重要性,故现在重新学习...邻接表(无向图/有向图) 是顺序存储和链式存储相结合的一种存储方式,使用于稀疏图,表删方式不唯一,时间复杂度低 邻接多重表(无向图) 十字.
  • 数据结构之图(三)——邻接表

    千次阅读 多人点赞 2019-08-06 19:25:38
    邻接表表示法(链式) ...邻接表不唯一 若无向图中有n个顶点、e条边,则其邻接表需要n个头结点和2e个表结点。适宜存储稀疏图。 无向图中顶点viv_ivi​的度第i个单链表中的结点数。 有向图的邻接表 ...
  •   我们知道图的存储结构有邻接矩阵存储方法和邻接表存储方法,而对于邻接矩阵我们已经学习过了,本篇将主要介绍图的邻接表存储结构。 图1-图的邻接表存储结构 1. 邻接表存储有向图 图2-邻接表存储有向图 ...
  • 首先明确邻接表的存储方式:邻接表中存在两种结构:顶点表节点和边表节点。顶点表节点是存储当前节点,其后的一串边表节点是此点的邻接点。#include&lt;iostream&gt; #include&lt;stdlib.h&gt; #...
  • /*拓扑排序*/ #include<stdio.h> #include<stdlib.h> #define max 105 typedef struct edge{ int adjvex; int weight; struct edge* next;...以上为邻接表常规操作 int temp[max][max];
  • 有向图邻接表

    千次阅读 2019-01-11 18:18:09
    邻接表有向图是指通过邻接表表示的有向图。 有向图可以理解一种数据结构,处理特定场景的问题会比较简单 对于java来说,用map实现有向图比较便于进行查找操作。 实现有向图这种数据结构并困难,难的是如何...
  • 深度优先遍历类似于树的前序遍历,深度优先遍历...而结点和邻接点的关系则用邻接表表示。 先定义我们需要的结构体类型 typedef struct k { int data;//邻接点的下标 struct k * next;//用于连接下一个邻接点 }node...
  • 图的逻辑结构:多对多。 图的存储结构: 图没有顺序存储结构,但可以...v1与v1本身之间无边,无邻接关系,所以0 v1与v2之间有边,有邻接关系,所以1 v1与v3之间无边,无邻接关系,所以0 v1与v4之间有边...
  • 使用邻接表进行拓扑排序的算法说明

    千次阅读 多人点赞 2016-12-30 15:03:09
    以上面的邻接表为例: 算法开始时: 1、从纵表开始,找到前继0的点,压栈,此时栈里只有1, 2、从栈顶取一个节点(弹栈),此时就是1,输出节点值1。 3、将其横表所对应的节点count值减1,凡是...
  • 邻接表 对比邻接矩阵与邻接表 十字链表 邻接多重表   前言 在线性表中,数据元素之间仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继; 在树形结构中,数据元素之间有明显的层次关系,并且每一层...
  • 邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 三、实现提示 设图的结点超过30个,每个结点用一个编号表示(如果...
  • 我们叫顺序存储结构了,叫邻接矩阵,邻接表和我们十字链有异曲同工之处,只不过邻接表的链表要多一点,好了话多说我们开始学习吧!!! 每日一遍,防止颓废 1.邻接矩阵 官方术语: 邻接矩阵(Adjacency Matrix...
  • 上一篇文章中讲述了用邻接矩阵存储的图的拓扑排序,下面本文介绍用邻接表存储的...而利用邻接表会使入度0的顶点的操作简化,从而提高算法的效率。 在邻接表存储结构中,为了便于检查每个顶点的入度,可在顶点表中增加
  • 上一节介绍了如何使用顺序存储...使用链式存储结构表示图的常用方法有 3 种:邻接表、邻接多重表和十字链表。 邻接的意思是顶点之间有边或者弧存在,通过当前顶点,可以直接找到下一个顶点。 邻接表 使用邻接表存...
  • 邻接表存储图的广度优先遍历 试实现邻接表存储图的广度优先遍历。 函数接口定义: void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) ); 其中LGraph是邻接表存储的图,定义如下: /* 邻接点的定义...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,220
精华内容 4,488
关键字:

邻接表为什么不唯一