C语言如何邻接表建立图

这篇文章主要介绍C语言如何邻接表建立图，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！

有向图

代码：

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<stack> using namespace std; #define maxn 200 int v, e; //表结点 typedef struct _Enode {	int ivex; //该边所指向的节点位置	int value;//如果边有权值的话，就对其赋值	struct _Enode* next_edge; //指向下一条边 }ENode,*PENode; //头结点 typedef struct _VNode {	int data;	ENode* fidt_edge; }VNode; //邻接表 typedef struct _LGraph {	int vex_num; //点的数量	int edg_num; //边的数量	VNode vexs[maxn]; //一维数组存表头节点 }LGraph; LGraph* create() {	LGraph* pG;	pG = (LGraph*)malloc(sizeof(LGraph));	memset(pG, 0, sizeof(LGraph));	pG->vex_num = v;  //顶点数	pG->edg_num = e; //边数	for (int i = 0; i < v; ++i) //初始化定点表的指针域为空	pG->vexs[i].fidt_edge = NULL;	//建立链表	for (int i = 0; i < e; ++i) 	{	int v1, v2;	scanf_s("%d%d", &v1, &v2);	ENode* p1 = (ENode*)malloc(sizeof(ENode));  //为新建的边申请空间	p1->ivex = v2;//该边指向的节点	// 头插法建立	p1->next_edge = pG->vexs[v1].fidt_edge;	pG->vexs[v1].fidt_edge = p1;	}	return pG; } int main() {	while (~scanf_s("%d%d", &v, &e))	{	if (v == 0 && e == 0)	break;	LGraph* pG;	pG = create();	}	return 0; }

无向图

在代码的建立链表的地方变成

//建立链表	for (int i = 0; i < e; ++i) 	{	int v1, v2;	scanf_s("%d%d", &v1, &v2);	ENode* p1 = (ENode*)malloc(sizeof(ENode));  //为新建的边申请空间	p1->ivex = v2;//该边指向的节点	// 头插法建立	p1->next_edge = pG->vexs[v1].fidt_edge;	pG->vexs[v1].fidt_edge = p1;	//另一条边	ENode* p2 = (ENode*)malloc(sizeof(ENode));  //为新建的边申请空间	p2->ivex = v1;//该边指向的节点	// 头插法建立	p2->next_edge = pG->vexs[v2].fidt_edge;	pG->vexs[v2].fidt_edge = p2;	}

邻接表存图进行拓扑排序

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<stack> using namespace std; #define maxn 200 int v, e; //表结点 typedef struct _Enode {	int ivex; //该边所指向的节点位置	struct _Enode* next_edge; //指向下一条边 }ENode,*PENode; //头结点 typedef struct _VNode {	int data;	int indegree;//记录定点的入度	ENode* fidt_edge; }VNode; //邻接表 typedef struct _LGraph {	int vex_num; //点的数量	int edg_num; //边的数量	VNode vexs[maxn]; //一维数组存表头节点 }LGraph; LGraph* create() {	LGraph* pG;	pG = (LGraph*)malloc(sizeof(LGraph));	memset(pG, 0, sizeof(LGraph));	pG->vex_num = v;  //顶点数	pG->edg_num = e; //边数	for (int i = 0; i < v; ++i) //初始化定点表的指针域为空	pG->vexs[i].fidt_edge = NULL;	for (int i = 0; i < e; ++i)	{	int v1, v2;	scanf_s("%d%d", &v1, &v2);	ENode* p1 = (ENode*)malloc(sizeof(ENode));  //为新建的边申请空间	p1->ivex = v2;//该边指向的节点	// 头插法建立	p1->next_edge = pG->vexs[v1].fidt_edge;	pG->vexs[v1].fidt_edge = p1;	}	return pG; } void TopSort(LGraph* pG) {	stack<int>s;	int count, k, i;	ENode* p;	for (int i = 0; i < v; ++i) //记录各个顶点的入度	{	//遍历整个邻接表，如果表结点的值为 i，则i对应的头结点的入度加1	p = pG->vexs[i].fidt_edge; //获得其指向的第一条边	while (p)	{	pG->vexs[p->ivex].indegree++; //该边表存的位置对应的头结点的入度数量加1	p = p->next_edge;	}	}	//将入度为0的压入栈中	for (int i = 0; i < v; ++i)	if (pG->vexs[i].indegree == 0)s.push(i);	count = 0;//对输出的顶点计数	while (!s.empty())	{	int k = s.top(); //取出	s.pop();	++count;	//与k节点相邻的节点的入度减1	for (p = pG->vexs[k].fidt_edge; p; p = p->next_edge)	{	int to;	to = p->ivex;	pG->vexs[to].indegree--;	//减为0的话就压入栈中	if (pG->vexs[to].indegree == 0)	s.push(to);	}	}	if (count < pG->vex_num)	printf("NO\n");	else	printf("YES\n"); } int main() {	while (~scanf_s("%d%d", &v, &e))	{	if (v == 0 && e == 0)	break;	LGraph* pG;	pG = create();	TopSort(pG);	}	return 0; }

以上是“C语言如何邻接表建立图”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注亿速云行业资讯频道！