图的创建之邻接表法（C语言描述）

淩亂°似流年 2021-12-05 14:57 210阅读 0赞

邻接矩阵创建图的方法可以看这个链接https://blog.csdn.net/qq\_44614524/article/details/96138200  
邻接表创建图的方法和邻接矩阵的方法大致相同。邻接表创建图的步骤如下图：邻接表，G【N】为指针数组，每个指针对应矩阵每行一个链表，只存非零元素。如下图，第一行就表示的是从0-1，从0-3，如果我们说的是无向图的话，那么一条边会被存储两次。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]  
首先我们对邻接表的结构体进行定义，从上图我们不难看出邻接表创建图需要一个一维数组，数组中包含的是指针，指针用来向后指。

struct Gnode{
    	int NV;         //顶点数
    	int Ne;         //边数
    	adjlist G;       //邻接表（实际上是一个数组）
    };
    
    typedef struct Gnode *ptrtoGnode;
    typedef ptrtoGnode Lgraph;          //以邻接表的方式存储图的类型

数组的定义如下

typedef struct Vnode{
    	ptrtoadjvnode firstedge;        //第一个节点的指针，指向链表的第一条边
    	datatype data;          //存储顶点数据
    }adjlist[maxvertexnum]; 	//adjlist是邻接表类型

每一个节点也应该包含一个指针，如果存在权重的话我们还要考虑权重的存储，因此节点的结构体定义如下：

struct  adjvnode{
    	vertex adjv;            //邻接点下标
    	weighttype weight;          //权重
    	ptrtoadjvnode next;         //指向下一节点的指针
    };
    
    typedef struct adjvnode *ptrtoadjvnode;

初始化一个包含所有顶点但是没有边的图

//初始化一个包含所有顶点但是没有边的图，首先我们建立一个空的图，然后对没有边的情况进行处理，根据最开始的那个图，我们直接将一维数组的每一个元素里面的指针置空，这样就不会有边了，这个图里面只包含顶点。
    Lgraph creatgraph(int vertexnum)
    {
    	vertex V, W;
    	Lgraph graph;
    	
    	graph = (Lgraph)malloc(sizeof(struct Gnode));
    	graph -> NV = vertexnum;
    	graph -> Ne = 0;
    	
    	//下面我们处理没有边的情况
    	for(V = 0;v < graph;V++)
    		graph -> G[V].firstedge = NULL;     //初始化链表（链表没有边，所以后继指针指向NULL）
        return graph;
    }

然后我们将边进行插入，如果需要进行无向图中边的插入的话还要在进行一次边的插入，因为无向图中两个顶点决定一条边即，从<v1,v2>和<v2,v1>之间的边只有一条但是要存储两次。

//插入一条边
    void insertedge(Lgraph graph, edge E)
    {
    	//插入边<v1, v2>
    	newnode = (ptrtoadjvnode)malloc(sizeof(struct adjvnode));
    	newnode -> adjv = E -> v2;
    	newnode -> weight = E -> weight;
    	
    	//将v2插入到v1的表头
    	newnode -> next = graph -> G[E -> v1].firstedge;
    	graph -> G[E -> v1].firstedge = newnode;
    	
    	//若为无向图，还要插入边<v2, v1>
    	newnode = (ptrtoadjvnode)malloc(sizeof(struct adjvnode));
    	newnode -> adjv = E -> v1;
    	newnode -> weight = E -> weight;
    	
    	//将v1插入到v2的表头
    	newnode -> next = graph -> G[E -> v2].firstedge;
    	graph -> G[E -> v2].firstedge = newnode;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]: /images/20211205/658987ab47bc47cbb5791a677e3db7b3.png