图的邻接表的实现C语言详解

àì夳堔傛蜴生んèń 2023-05-28 05:03 16阅读 0赞

**实现如图邻接表：**  
![图片来源于百度][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]  
共4个顶点，v0,v1,v2,v3;  
共5条边：arc\[0\]\[1\],arc\[0\]\[2\],arc\[0\]\[3\],arc\[2\]\[1\],arc\[2\]\[3\]。  
令4个顶点值分别为，a,b,c,d;

**编译环境vc6.0,代码如下**

/* 顶点数据类型为char,边上权值类型为int */
    #include <stdio.h>
    #include <stdlib.h>
    #define MAXVEX 100 //最大顶点数
    #define INFINITY 99999 //用99999表示无限大
    
    //****************************边表结点****************************
    typedef struct EdgeNode
    { 
    	int adjvex;							//邻接点域，储存该顶点对应的下标
    	//int weight; //用于储存权值，非网图不需要
    	struct EdgeNode* next;				//链域，指向下一个邻接结点
    }EdgeNode;
    
    //****************************顶点表结点****************************
    typedef struct VertexNode
    { 
    	char data;								//顶点域存放顶点信息
    	EdgeNode* firstedge;					 //边表头指针
    }VertexNode, AdjList[MAXVEX];
    
    
    //****************************邻接表结构****************************
    typedef struct GraphAdjList
    { 
    	AdjList adjlist;							//顶点表结点数组
    	int numVertexes, numEdges;					//图中当前顶点数和边数
    }GraphAdjList;
    
    //**************************无向图邻接表的创建*************************
    void CreateALGraph(GraphAdjList* G)
    { 
    	int i, j, k;
    	EdgeNode* e;
    	printf("输入顶点数和边数\n");
    	scanf("%d%d", &G->numVertexes, &G->numEdges);
    	getchar();													//获取缓冲区的 回车符
    
    	for (i = 0; i < G->numVertexes; i++)								//读入顶点信息，建立顶点表
    	{ 
    		printf("输入第%d个顶点值\n", i + 1);
    		scanf("%c", &G->adjlist[i].data);							//输入顶点信息
    		getchar();													//获取缓冲区的 回车符
    		G->adjlist[i].firstedge = NULL;								//将边表置为空表
    	}
    	for (k = 0; k < G->numEdges; k++)								//建立边表
    	{ 
    		printf("输入第%d条边（vi,vj）的下标：\n",k+1);
    		scanf("%d%d", &i, &j);
    		e = (EdgeNode*)malloc(sizeof(EdgeNode));				//向内存申请空间
    		if (e == NULL)
    		{ 
    			printf("内存申请失败\n");
    			exit(0);
    		}
    
    		e->adjvex = j;									//这三步，类似于单链表的头插法
    		e->next = G->adjlist[i].firstedge;
    		G->adjlist[i].firstedge = e;
    
    		e = (EdgeNode*)malloc(sizeof(EdgeNode));
    		if (e == NULL)
    		{ 
    			printf("内存申请失败\n");
    			exit(0);
    		}
    		e->adjvex = i;
    		e->next = G->adjlist[j].firstedge;
    		G->adjlist[j].firstedge = e;
    	}
    }
    
    //********************邻接矩阵的输出********************
    void prt(GraphAdjList G)
    { 
    	EdgeNode* p;
    	int i;
    	for (i = 0; i < G.numVertexes; i++)			//i小于当前顶点数
    	{ 
    		p = G.adjlist[i].firstedge;				//p指向第一个边表结点
    		while (p != NULL)
    		{ 
    			printf("边%c-%c\t", G.adjlist[i].data, G.adjlist[p->adjvex].data);
    			p = p->next;						//p指向下一个边表结点
    		}
    		printf("\n");
    	}
    }
    
    int main()
    { 
    	GraphAdjList G;
    	CreateALGraph(&G);
    	prt(G);
    	return 0;
    }

**输出结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]: /images/20230528/1d85f77888924d65b46b814f1056b603.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/f9421dd586fb413a9fe3e1878f91d517.png