算法与数据结构基础8 C++实现有向图——邻接表存储

                前面实现了链表和树，现在看看图。
链表是一对一的对应关系；
树是一对多的对应关系；
图是多对多的对应关系。


图一般有两种存储方式，邻接表和邻接矩阵。


先看邻接表。
邻接表就是将图中所有的点用一个数组存储起来，并将此作为一个链表的头，
链表中保存跟这个点相邻的点（边点），如果有权值，则在边点中增加一权值字段。

因此，有向图邻接表的空间复杂度为O(v+e)，无向图加倍。

C++实现代码如下：
// GraphList.h

#include <iostream>#include <cstdio>using namespace std;// 边struct Edge{ int vName; int weight; struct Edge* next;};// 顶点(链表头)struct Vertex{ int vName; struct Edge* next;};// 有向图class GraphList{public: ~GraphList(); void createGraph(); void printGraph();private: // 1. 输入定点数 void inputVertexCount(); // 2. 生成定点数组 void makeVertexArray(); // 3. 输入边数 void inputEdgeCount(); // 4. 输入边的起始点 void inputEdgeInfo(); // 5. 添加边节点至对应的链表中 void addEdgeToList(int vFrom, int weight, int vTo);private: int m_vCount; int m_eCount; Vertex* m_vVertex;};GraphList::~GraphList(){ for (int i = 0; i < m_vCount; ++i){  Edge* tmp = m_vVertex[i].next;  Edge* edge = NULL;  while(tmp){   edge = tmp;   tmp = tmp->next;   delete edge;   edge = NULL;  } } delete[] m_vVertex;}void GraphList::inputVertexCount(){ cout << "please input count of vertex:"; cin >> m_vCount;}void GraphList::makeVertexArray(){ m_vVertex = new Vertex[m_vCount]; // 初始化 for (int i = 0; i < m_vCount; ++i){  m_vVertex[i].vName = i;  m_vVertex[i].next = NULL; }}void GraphList::inputEdgeCount(){ cout << "please input count of edge:"; cin >> m_eCount;}void GraphList::inputEdgeInfo(){ cout << "please input edge information:" << endl; for (int i = 0; i < m_eCount; ++i){  cout << "the edge " << i << ":" << endl;  // 起点  int from = 0;  cout << "From: ";  cin >> from;    // 权值  int weight = 0;  cout << "Weight:";  cin >> weight;  // 终点  int to = 0;  cout << "To: ";  cin >> to;  cout << endl;  addEdgeToList(from, weight, to); }}void GraphList::addEdgeToList(int vFrom, int weight, int vTo){ Edge* edge = new Edge(); edge->vName = vTo; edge->weight = weight; edge->next = NULL; if (m_vVertex[vFrom].next){  Edge* tmp = m_vVertex[vFrom].next;  while(tmp->next){   tmp = tmp->next;  }  tmp->next = edge; }else{  m_vVertex[vFrom].next = edge; }}void GraphList::printGraph(){ for (int i = 0; i < m_vCount; ++i){  Edge* tmp = m_vVertex[i].next;  cout << "list:" << m_vVertex[i].vName << "->";  while(tmp){   cout << "(" << tmp->weight << ")";   cout << tmp->vName << "->";   tmp = tmp->next;  }  cout << "NULL" << endl; }}// **************************************************************************// 流程控制// **************************************************************************void GraphList::createGraph(){ inputVertexCount(); makeVertexArray(); inputEdgeCount(); inputEdgeInfo();}

// main.cpp

// test for GraphList#include "GraphList.h"#include <cstdlib>int main(){ GraphList graph; graph.createGraph(); graph.printGraph(); system("pause"); return 0;}

假如有如下的图：

运行结果：