有向图的邻接矩阵与邻接表详细实现 |
您所在的位置：网站首页 › 用邻接矩阵创建无向图 › 有向图的邻接矩阵与邻接表详细实现 |
有向图的邻接矩阵与邻接表详细实现
|
有向图的邻接矩阵
通过邻接矩阵来表示有向图。如下如所示：
上面的有向图G2包含了“A, B, C, D, E, F, G”共7个顶点，而且包含了“, , , , , , , , ”共9条边。 上图中右边的矩阵是有向图G2的邻接矩阵示意图。A[i][j] = 1表示第i个顶点到第j个顶点是一条边，A[i][j] = 0则表示不是一条边，而A[i][j]表示的是第i行第j列的值。例如，A[1][2] = 1表示的是顶点B到顶点C是一条边。 代码实现 #include #include using namespace std; #define MAX 100 class MatrixDG { private: char mVexs[MAX]; //顶点集合 int mVexNum; //顶点数 int mEdgNum; //边数 int mMatrix[MAX][MAX]; //邻接矩阵 public: //创建图(手动输入) MatrixDG(); //创建图(用提供的顶点和边) MatrixDG(char *vexs, int vNum, char (*edges)[2], int eNum); ~MatrixDG(); void print(); char readChar(); int getPosition(char ch); }; MatrixDG::MatrixDG() { char c1, c2; int p1, p2; cout mVexNum; cout mEdgNum; if (mVexNum cout cout //获得边的起始点和结束点 p1 = getPosition(edges[j][0]); p2 = getPosition(edges[j][1]); //将连线的两个点都置为1 if (p1 == -1 && p2 == -1) { cout for (int i = 0; i char ch; do { cin >> ch; } while (!((ch >= 'a' && ch = 'A' && ch for (int j = 0; j 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 vNum = sizeof(vexs) / sizeof(vexs[0]); int eNum = sizeof(edges) / sizeof(edges[0]); //1. 根据提供的数据生成 // MatrixDG mdg(vexs, vNum, edges, eNum); // mdg.print(); //2. 手动生成 MatrixDG mdg1; mdg1.print(); }手动输入时运行结果如下： 输入顶点数:7 输入边数：9 vertex(0):A vertex(1):B vertex(2):C vertex(3):D vertex(4):E vertex(5):F vertex(6):G edge(0):AB edge(1):BC edge(2):BE edge(3):BF edge(4):CE edge(5):DC edge(6):EB edge(7):ED edge(8):FG 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 有向图的邻接表通过邻接表来表示有向图。如下如所示：
上面的有向图G2包含了“A, B, C, D, E, F, G”共7个顶点，而且包含了“, , , , , , , , ”共9条边。 上图中右边的邻接表是有向图G2的邻接表示意图。每个顶点都包含一条链表，该链表记录了“该顶点所对应的出边的另一个顶点的序号”。例如，第1个顶点B包含的链表所包含的节点的数据分别是“2, 4, 5”，而这“2, 4, 5”分别对应“C, E, F”的序号，“C, E, F”都属于B的出边的另一个顶点。 代码实现 #include using namespace std; #define MAX 100 class ListDG { private: struct ENode //每一条边 { int iVex; //指向的顶点的位置 ENode *nextEdge = NULL; //指向顶点的下一条边的指针 }; struct VNode //数组中存储的顶点 { char data; ENode *firstEdge = NULL; //指向第一条该顶点的边 }; private: int mVexNum; //图的顶点数目 int mEdgeNum; //图的边的数目 VNode mVexs[MAX]; //存储顶点 public: ListDG(); ListDG(char vexs[], int vNum, char edges[][2], int eNum); ~ListDG(); //打印邻接表 void print(); private: //读取一个合法的输入字符 char readChar(); //返回字符ch在的位置 int getPosition(char ch); //将node结点链接到list的最后 void linkLast(ENode *list, ENode *node); }; ListDG::ListDG() { char c1, c2; int p1, p2; ENode *node1; cout mVexNum; cout mEdgeNum; if (mVexNum > MAX || mEdgeNum > MAX || mVexNum cout cout mVexs[i].data = vexs[i]; } for (int j = 0; j cout ENode *p = list; while (p->nextEdge) p = p->nextEdge; p->nextEdge = node; } int ListDG::getPosition(char ch) { for (int i = 0; i char ch; do { cin >> ch; } while (!((ch >= 'a' && ch = 'A' && ch cout 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 vNum = sizeof(vexs) / sizeof(vexs[0]); int eNum = sizeof(edges) / sizeof(edges[0]); //1. 根据提供的数据生成 // ListDG ldg(vexs, vNum, edges, eNum); // ldg.print(); //2. 手动生成 ListDG ldg1; ldg1.print(); return 0; }手动输入时运行结果如下： 输入顶点数:7 输入边数:9 vertex(0):A vertex(1):B vertex(2):C vertex(3):D vertex(4):E vertex(5):F vertex(6):G edge(0):AB edge(1):BC edge(2):BE edge(3):BF edge(4):CE edge(5):DC edge(6):EB edge(7):ED edge(8):FG 0(A):1(B) 1(B):2(C)4(E)5(F) 2(C):4(E) 3(D):2(C) 4(E):1(B)3(D) 5(F):6(G) 6(G): |
【本文地址】
今日新闻 |
推荐新闻 |