大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
数据结构之图的基本概念中了解了图的基本概念，接下来对图的代码实现进行详解。
邻接无向图
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://javaforall.net/120150.html原文链接：https://javaforall.net
