數(shù)據(jù)結(jié)構(gòu)之圖的基本概念中了解了圖的基本概念，接下來對圖的代碼實現(xiàn)進行詳解。

鄰接無向圖

1. 鄰接表無向圖介紹

　　鄰接表無向圖是指通過鄰接表表示的無向圖。

　　上面的圖G1包含了"A,B,C,D,E,F,G"共7個頂點，而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7條邊。

　　上圖右邊的矩陣是G1在內(nèi)存中的鄰接表示意圖。每一個頂點都包含一條鏈表，該鏈表記錄了"該頂點的鄰接點的序號"。例如，第2個頂點(頂點C)包含的鏈表所包含的節(jié)點的數(shù)據(jù)分別是"0,1,3"；而這"0,1,3"分別對應(yīng)"A,B,D"的序號，"A,B,D"都是C的鄰接點。就是通過這種方式記錄圖的信息的。

2. 鄰接表無向圖代碼實現(xiàn)

（1）數(shù)據(jù)結(jié)構(gòu)

struct ENode {int nVindex; // 該邊所指的頂點的位置ENode *pNext; // 指向下一個邊的指針 };struct VNode {char data; // 頂點信息ENode *pFirstEdge; // 指向第一條依附該頂點的邊 };

（2）圖的創(chuàng)建

listUDG(char *vexs, int vlen, char edges[][2], int elen) {m_nVexNum = vlen;m_nEdgNum = elen;// 初始化"鄰接表"的頂點for (int i = 0; i < vlen; i ++){m_mVexs[i].data = vexs[i];m_mVexs[i].pFirstEdge = NULL;}char c1,c2;int p1,p2;ENode *node1, *node2;// 初始化"鄰接表"的邊for (int j = 0; j < elen; j ++){// 讀取邊的起始頂點和結(jié)束頂點c1 = edges[j][0];c2 = edges[j][1];p1 = GetVIndex(c1);p2 = GetVIndex(c2);node1 = new ENode();node1->nVindex = p2;if (m_mVexs[p1].pFirstEdge == NULL){m_mVexs[p1].pFirstEdge = node1;}else{LinkLast(m_mVexs[p1].pFirstEdge, node1);}node2 = new ENode();node2->nVindex = p1;if (m_mVexs[p2].pFirstEdge == NULL){m_mVexs[p2].pFirstEdge = node2;}else{LinkLast(m_mVexs[p2].pFirstEdge, node2);}}}

（3）完整代碼

#include "stdio.h" #include <iostream> using namespace std;#define MAX 100// 邊 struct ENode {int nVindex; // 該邊所指的頂點的位置ENode *pNext; // 指向下一個邊的指針 };struct VNode {char data; // 頂點信息ENode *pFirstEdge; // 指向第一條依附該頂點的邊 };// 無向鄰接表 class listUDG { public:listUDG(){};listUDG(char *vexs, int vlen, char edges[][2], int elen){m_nVexNum = vlen;m_nEdgNum = elen;// 初始化"鄰接表"的頂點for (int i = 0; i < vlen; i ++){m_mVexs[i].data = vexs[i];m_mVexs[i].pFirstEdge = NULL;}char c1,c2;int p1,p2;ENode *node1, *node2;// 初始化"鄰接表"的邊for (int j = 0; j < elen; j ++){// 讀取邊的起始頂點和結(jié)束頂點c1 = edges[j][0];c2 = edges[j][1];p1 = GetVIndex(c1);p2 = GetVIndex(c2);node1 = new ENode();node1->nVindex = p2;if (m_mVexs[p1].pFirstEdge == NULL){m_mVexs[p1].pFirstEdge = node1;}else{LinkLast(m_mVexs[p1].pFirstEdge, node1);}node2 = new ENode();node2->nVindex = p1;if (m_mVexs[p2].pFirstEdge == NULL){m_mVexs[p2].pFirstEdge = node2;}else{LinkLast(m_mVexs[p2].pFirstEdge, node2);}}}~listUDG(){ENode *pENode = NULL;ENode *pTemp = NULL;for (int i = 0; i < m_nVexNum; i ++){pENode = m_mVexs[i].pFirstEdge;if (pENode != NULL){pTemp = pENode;pENode = pENode->pNext;delete pTemp;}delete pENode;}}void PrintUDG(){ ENode *pTempNode = NULL;cout << "鄰接無向表:" << endl;for (int i = 0; i < m_nVexNum; i ++){cout << "頂點:" << GetVIndex(m_mVexs[i].data)<< "-" << m_mVexs[i].data<< "->";pTempNode = m_mVexs[i].pFirstEdge;while (pTempNode){cout <<pTempNode->nVindex << "->";pTempNode = pTempNode->pNext;}cout << endl;}} private:// 返回頂點的索引int GetVIndex(char ch){int i = 0;for (; i < m_nVexNum; i ++){if (m_mVexs[i].data == ch){return i;}}return -1;}void LinkLast(ENode *pFirstNode, ENode *pNode){if (pFirstNode == NULL || pNode == NULL){return;}ENode *pTempNode = pFirstNode;while (pTempNode->pNext != NULL){pTempNode = pTempNode->pNext;}pTempNode->pNext = pNode;}private:int m_nVexNum; // 頂點數(shù)目int m_nEdgNum; // 邊數(shù)目 VNode m_mVexs[MAX]; };void main() {char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; char edges[][2] = { {'A', 'C'}, {'A', 'D'}, {'A', 'F'}, {'B', 'C'}, {'C', 'D'}, {'E', 'G'}, {'F', 'G'}}; int vlen = sizeof(vexs)/sizeof(vexs[0]); int elen = sizeof(edges)/sizeof(edges[0]); listUDG* pG = new listUDG(vexs, vlen, edges, elen); pG->PrintUDG(); // 打印圖 return; } View Code

鄰接有向圖

1. 鄰接表有向圖介紹

　　鄰接表有向圖是指通過鄰接表表示的有向圖。

　　上面的圖G2包含了"A,B,C,D,E,F,G"共7個頂點，而且包含了"<A,B>,<B,C>,<B,E>,<B,F>,<C,E>,<D,C>,<E,B>,<E,D>,<F,G>"共9條邊。

上　　圖右邊的矩陣是G2在內(nèi)存中的鄰接表示意圖。每一個頂點都包含一條鏈表，該鏈表記錄了"該頂點所對應(yīng)的出邊的另一個頂點的序號"。例如，第1個頂點(頂點B)包含的鏈表所包含的節(jié)點的數(shù)據(jù)分別是"2,4,5"；而這"2,4,5"分別對應(yīng)"C,E,F"的序號，"C,E,F"都屬于B的出邊的另一個頂點。

2. 鄰接表有向圖代碼實現(xiàn)

（1）數(shù)據(jù)結(jié)構(gòu)

struct ENode {int nVindex; // 該邊所指的頂點的位置ENode *pNext; // 指向下一個邊的指針 };struct VNode {char data; // 頂點信息ENode *pFirstEdge; // 指向第一條依附該頂點的邊 };

（2）鄰接表有向圖創(chuàng)建

listDG(char *vexs, int vlen, char edges[][2], int elen) {m_nVexNum = vlen;m_nEdgNum = elen;// 初始化"鄰接表"的頂點for (int i = 0; i < vlen; i ++){m_mVexs[i].data = vexs[i];m_mVexs[i].pFirstEdge = NULL;}char c1,c2;int p1,p2;ENode *node1;// 初始化"鄰接表"的邊for (int j = 0; j < elen; j ++){// 讀取邊的起始頂點和結(jié)束頂點c1 = edges[j][0];c2 = edges[j][1];p1 = GetVIndex(c1);p2 = GetVIndex(c2);node1 = new ENode();node1->nVindex = p2;if (m_mVexs[p1].pFirstEdge == NULL){m_mVexs[p1].pFirstEdge = node1;}else{LinkLast(m_mVexs[p1].pFirstEdge, node1);}} }

（3）完整代碼實現(xiàn)

#include "stdio.h" #include <iostream> using namespace std;#define MAX 100// 邊 struct ENode {int nVindex; // 該邊所指的頂點的位置ENode *pNext; // 指向下一個邊的指針 };struct VNode {char data; // 頂點信息ENode *pFirstEdge; // 指向第一條依附該頂點的邊 };// 有向鄰接表 class listDG { public:listDG(){};listDG(char *vexs, int vlen, char edges[][2], int elen){m_nVexNum = vlen;m_nEdgNum = elen;// 初始化"鄰接表"的頂點for (int i = 0; i < vlen; i ++){m_mVexs[i].data = vexs[i];m_mVexs[i].pFirstEdge = NULL;}char c1,c2;int p1,p2;ENode *node1;// 初始化"鄰接表"的邊for (int j = 0; j < elen; j ++){// 讀取邊的起始頂點和結(jié)束頂點c1 = edges[j][0];c2 = edges[j][1];p1 = GetVIndex(c1);p2 = GetVIndex(c2);node1 = new ENode();node1->nVindex = p2;if (m_mVexs[p1].pFirstEdge == NULL){m_mVexs[p1].pFirstEdge = node1;}else{LinkLast(m_mVexs[p1].pFirstEdge, node1);}}}~listDG(){ENode *pENode = NULL;ENode *pTemp = NULL;for (int i = 0; i < m_nVexNum; i ++){pENode = m_mVexs[i].pFirstEdge;if (pENode != NULL){pTemp = pENode;pENode = pENode->pNext;delete pTemp;}delete pENode;}}void PrintDG(){ ENode *pTempNode = NULL;cout << "鄰接有向表:" << endl;for (int i = 0; i < m_nVexNum; i ++){cout << "頂點:" << GetVIndex(m_mVexs[i].data)<< "-" << m_mVexs[i].data<< "->";pTempNode = m_mVexs[i].pFirstEdge;while (pTempNode){cout <<pTempNode->nVindex << "->";pTempNode = pTempNode->pNext;}cout << endl;}} private:// 返回頂點的索引int GetVIndex(char ch){int i = 0;for (; i < m_nVexNum; i ++){if (m_mVexs[i].data == ch){return i;}}return -1;}void LinkLast(ENode *pFirstNode, ENode *pNode){if (pFirstNode == NULL || pNode == NULL){return;}ENode *pTempNode = pFirstNode;while (pTempNode->pNext != NULL){pTempNode = pTempNode->pNext;}pTempNode->pNext = pNode;}private:int m_nVexNum; // 頂點數(shù)目int m_nEdgNum; // 邊數(shù)目 VNode m_mVexs[MAX]; };void main() {char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; char edges[][2] = { {'A', 'B'}, {'B', 'C'}, {'B', 'E'}, {'B', 'F'}, {'C', 'E'}, {'D', 'C'}, {'E', 'B'}, {'E', 'D'}, {'F', 'G'}}; int vlen = sizeof(vexs)/sizeof(vexs[0]); int elen = sizeof(edges)/sizeof(edges[0]); listDG *pG = new listDG(vexs, vlen, edges, elen); pG->PrintDG(); // 打印圖 return; } View Code

轉(zhuǎn)載于:https://www.cnblogs.com/xiaobingqianrui/p/8917390.html

總結(jié)

以上是生活随笔為你收集整理的数据结构之图的创建（邻接表）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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