数据结构之图的创建（邻接表）
生活随笔
收集整理的这篇文章主要介绍了
数据结构之图的创建（邻接表）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
数据结构之图的基本概念中了解了图的基本概念，接下来对图的代码实现进行详解。
邻接无向图
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在内存中的邻接表示意图。每一个顶点都包含一条链表，该链表记录了"该顶点的邻接点的序号"。例如，第2个顶点(顶点C)包含的链表所包含的节点的数据分别是"0,1,3"；而这"0,1,3"分别对应"A,B,D"的序号，"A,B,D"都是C的邻接点。就是通过这种方式记录图的信息的。
2. 邻接表无向图代码实现
（1）数据结构
struct ENode {int nVindex; // 该边所指的顶点的位置ENode *pNext; // 指向下一个边的指针 };struct VNode {char data; // 顶点信息ENode *pFirstEdge; // 指向第一条依附该顶点的边 };（2）图的创建
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 ++){// 读取边的起始顶点和结束顶点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 ++){// 读取边的起始顶点和结束顶点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; // 顶点数目int m_nEdgNum; // 边数目 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在内存中的邻接表示意图。每一个顶点都包含一条链表，该链表记录了"该顶点所对应的出边的另一个顶点的序号"。例如，第1个顶点(顶点B)包含的链表所包含的节点的数据分别是"2,4,5"；而这"2,4,5"分别对应"C,E,F"的序号，"C,E,F"都属于B的出边的另一个顶点。
2. 邻接表有向图代码实现
（1）数据结构
struct ENode {int nVindex; // 该边所指的顶点的位置ENode *pNext; // 指向下一个边的指针 };struct VNode {char data; // 顶点信息ENode *pFirstEdge; // 指向第一条依附该顶点的边 };（2）邻接表有向图创建
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 ++){// 读取边的起始顶点和结束顶点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）完整代码实现
#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 ++){// 读取边的起始顶点和结束顶点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; // 顶点数目int m_nEdgNum; // 边数目 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转载于:https://www.cnblogs.com/xiaobingqianrui/p/8917390.html
总结
以上是生活随笔为你收集整理的数据结构之图的创建（邻接表）的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： Java-JUC（一）：volatile
- 下一篇： 【备忘录】使用mongodb，报db.c