C語言鄰接表建立圖詳解

更新時間：2021年08月25日 11:38:59 作者：落春只在無意間

這篇文章主要介紹了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; //該邊所指向的節(jié)點位置
	int value;//如果邊有權值的話，就對其賦值
	struct _Enode* next_edge; //指向下一條邊
}ENode,*PENode;
//頭結點
typedef struct _VNode
{
	int data;
	ENode* fidt_edge;
}VNode;

//鄰接表
typedef struct _LGraph
{
	int vex_num; //點的數(shù)量
	int edg_num; //邊的數(shù)量
	VNode vexs[maxn]; //一維數(shù)組存表頭節(jié)點
}LGraph;

LGraph* create()
{
	LGraph* pG;
	pG = (LGraph*)malloc(sizeof(LGraph));
	memset(pG, 0, sizeof(LGraph));
	pG->vex_num = v;  //頂點數(shù)
	pG->edg_num = e; //邊數(shù)
	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;//該邊指向的節(jié)點
		// 頭插法建立
		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;//該邊指向的節(jié)點
		// 頭插法建立
		p1->next_edge = pG->vexs[v1].fidt_edge;
		pG->vexs[v1].fidt_edge = p1;
		//另一條邊
		ENode* p2 = (ENode*)malloc(sizeof(ENode));  //為新建的邊申請空間
		p2->ivex = v1;//該邊指向的節(jié)點
		// 頭插法建立
		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; //該邊所指向的節(jié)點位置
	struct _Enode* next_edge; //指向下一條邊
}ENode,*PENode;
//頭結點
typedef struct _VNode
{
	int data;
	int indegree;//記錄定點的入度
	ENode* fidt_edge;
}VNode;

//鄰接表
typedef struct _LGraph
{
	int vex_num; //點的數(shù)量
	int edg_num; //邊的數(shù)量
	VNode vexs[maxn]; //一維數(shù)組存表頭節(jié)點
}LGraph;

LGraph* create()
{
	LGraph* pG;
	pG = (LGraph*)malloc(sizeof(LGraph));
	memset(pG, 0, sizeof(LGraph));
	pG->vex_num = v;  //頂點數(shù)
	pG->edg_num = e; //邊數(shù)
	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;//該邊指向的節(jié)點
		// 頭插法建立
		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++; //該邊表存的位置對應的頭結點的入度數(shù)量加1
			p = p->next_edge;
		}
	}
	//將入度為0的壓入棧中
	for (int i = 0; i < v; ++i)
		if (pG->vexs[i].indegree == 0)s.push(i);
	count = 0;//對輸出的頂點計數(shù)
	while (!s.empty())
	{
		int k = s.top(); //取出
		s.pop();
		++count;
		//與k節(jié)點相鄰的節(jié)點的入度減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;
}