當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

邻接表建立图（c语言）

發(fā)布時(shí)間：2025/3/19 编程问答 17 豆豆

生活随笔收集整理的這篇文章主要介紹了邻接表建立图（c语言）小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

鄰接表建立圖

有向圖
無(wú)向圖
鄰接表存圖進(jìn)行拓?fù)渑判?/li>

不得不說(shuō)網(wǎng)上的真的是太亂了，看得我腦殼疼
自己寫(xiě)的可以，感覺(jué)好的話(huà)可以當(dāng)成模板。

有向圖

代碼：

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<stack>using namespace std; #define maxn 200int v, e; //表結(jié)點(diǎn) typedef struct _Enode {int ivex; //該邊所指向的節(jié)點(diǎn)位置int value;//如果邊有權(quán)值的話(huà)，就對(duì)其賦值struct _Enode* next_edge; //指向下一條邊 }ENode,*PENode;//頭結(jié)點(diǎn) typedef struct _VNode {int data;ENode* fidt_edge; }VNode;//鄰接表 typedef struct _LGraph {int vex_num; //點(diǎn)的數(shù)量int edg_num; //邊的數(shù)量VNode vexs[maxn]; //一維數(shù)組存表頭節(jié)點(diǎn) }LGraph;LGraph* create() {LGraph* pG;pG = (LGraph*)malloc(sizeof(LGraph));memset(pG, 0, sizeof(LGraph));pG->vex_num = v; //頂點(diǎn)數(shù)pG->edg_num = e; //邊數(shù)for (int i = 0; i < v; ++i) //初始化定點(diǎn)表的指針域?yàn)榭?/span>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)); //為新建的邊申請(qǐng)空間p1->ivex = v2;//該邊指向的節(jié)點(diǎn)// 頭插法建立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; }

無(wú)向圖

在代碼的建立鏈表的地方變成

//建立鏈表for (int i = 0; i < e; ++i) {int v1, v2;scanf_s("%d%d", &v1, &v2);ENode* p1 = (ENode*)malloc(sizeof(ENode)); //為新建的邊申請(qǐng)空間p1->ivex = v2;//該邊指向的節(jié)點(diǎn)// 頭插法建立p1->next_edge = pG->vexs[v1].fidt_edge;pG->vexs[v1].fidt_edge = p1;//另一條邊ENode* p2 = (ENode*)malloc(sizeof(ENode)); //為新建的邊申請(qǐng)空間p2->ivex = v1;//該邊指向的節(jié)點(diǎn)// 頭插法建立p2->next_edge = pG->vexs[v2].fidt_edge;pG->vexs[v2].fidt_edge = p2;}

鄰接表存圖進(jìn)行拓?fù)渑判?/h1> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<stack>using namespace std; #define maxn 200int v, e; //表結(jié)點(diǎn) typedef struct _Enode {int ivex; //該邊所指向的節(jié)點(diǎn)位置struct _Enode* next_edge; //指向下一條邊 }ENode,PENode;//頭結(jié)點(diǎn) typedef struct _VNode {int data;int indegree;//記錄定點(diǎn)的入度ENode fidt_edge; }VNode;//鄰接表 typedef struct _LGraph {int vex_num; //點(diǎn)的數(shù)量int edg_num; //邊的數(shù)量VNode vexs[maxn]; //一維數(shù)組存表頭節(jié)點(diǎn) }LGraph;LGraph* create() {LGraph* pG;pG = (LGraph)malloc(sizeof(LGraph));memset(pG, 0, sizeof(LGraph));pG->vex_num = v; //頂點(diǎn)數(shù)pG->edg_num = e; //邊數(shù)for (int i = 0; i < v; ++i) //初始化定點(diǎn)表的指針域?yàn)榭?/span>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)); //為新建的邊申請(qǐng)空間p1->ivex = v2;//該邊指向的節(jié)點(diǎn)// 頭插法建立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) //記錄各個(gè)頂點(diǎn)的入度{//遍歷整個(gè)鄰接表，如果表結(jié)點(diǎn)的值為 i，則i對(duì)應(yīng)的頭結(jié)點(diǎn)的入度加1p = pG->vexs[i].fidt_edge; //獲得其指向的第一條邊while (p){pG->vexs[p->ivex].indegree++; //該邊表存的位置對(duì)應(yīng)的頭結(jié)點(diǎn)的入度數(shù)量加1p = p->next_edge;}}//將入度為0的壓入棧中for (int i = 0; i < v; ++i)if (pG->vexs[i].indegree == 0)s.push(i);count = 0;//對(duì)輸出的頂點(diǎn)計(jì)數(shù)while (!s.empty()){int k = s.top(); //取出s.pop();++count;//與k節(jié)點(diǎn)相鄰的節(jié)點(diǎn)的入度減1for (p = pG->vexs[k].fidt_edge; p; p = p->next_edge){int to;to = p->ivex;pG->vexs[to].indegree--;//減為0的話(huà)就壓入棧中if (pG->vexs[to].indegree == 0)s.push(to);}}if (count < pG->vex_num)printf("NO\n");elseprintf("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; }
總結(jié)

以上是生活随笔為你收集整理的邻接表建立图（c语言）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

语言