图的实现：邻接表
当图中的边数较少时，用邻接表来实现图结构，则会浪费非常多内存空间。因此，考虑还有一种实现图结构的方法：邻接表。在邻接表中主要有两种节点结构体：
顶点节点
边节点
直接看代码
类定义
#include#include using namespace std;//最大权值#define MAXWEIGHT 100//边节点typedef struct edgenode_tag{ int adjvex; //邻接点 int weight; //边的权值 struct edgenode_tag *next;}EdgeNode;//顶点节点typedef struct vertex_tag{ int vertex; //顶点 EdgeNode *next;}Vertex;class Graph{private: //是否带权 bool isWeighted; //是否有向 bool isDirected; //顶点数 int numV; //边数 int numE; //邻接表 Vertex *adjList;public: /* 构造方法 numV是顶点数，isWeighted是否带权值，isDirected是否有方向 */ Graph(int numV, bool isWeighted = false, bool isDirected = false); //建图 void createGraph(); //析构方法 ~Graph(); //获取顶点数 int getVerNums() {return numV;} //获取边数 int getEdgeNums() {return numE;} //插入边 void insertEdge(int tail, int head, int weight = 1); void insertedge(int tail, int head, int weight); //设置指定边的权值 void setEdgeWeight(int tail, int head, int weight); //打印邻接表 void printAdjacentList(); //检查输入 bool check(int tail, int head, int weight = 1);};
类实现
/*构造方法numV是顶点数，isWeighted是否带权值，isDirected是否有方向*/Graph::Graph(int numV, bool isWeighted, bool isDirected){ while (numV <= 0) { cout << "输入的顶点数不正确！，又一次输入 "; cin >> numV; } this->numV = numV; this->isWeighted = isWeighted; this->isDirected = isDirected; //边数初始化为0 numE = 0; adjList = new Vertex[numV]; //指针数组 for (int i = 0; i < numV; i++) { adjList[i].vertex = i; adjList[i].next = NULL; }}//建图void Graph::createGraph(){ //用一个新的变量表示边数，numE的改动则留到insertedge()中 int numEdge = 0; cout << "输入边数 "; while (cin >> numEdge && numEdge < 0) cout << "输入有误！，又一次输入 "; int i, j, w; if (!isWeighted) //无权图 { cout << "输入每条边的起点和终点：\n"; for (int k = 0; k < numEdge; k++) { cin >> i >> j; while (!check(i, j)) { cout << "输入的边不正确！又一次输入\n"; cin >> i >> j; } insertEdge(i, j); } } else //有权图 { cout << "输入每条边的起点、终点和权值：\n"; for (int k = 0; k < numEdge; k++) { cin >> i >> j >> w; while (!check(i, j, w)) { cout << "输入的边不正确！又一次输入\n"; cin >> i >> j >> w; } insertEdge(i, j, w); } }}//析构方法Graph::~Graph(){ int i; EdgeNode *p, *q; for (i = 0; i < numV; i++) { if (adjList[i].next) { p = adjList[i].next; while (p) { q = p->next; delete p; p = q; } } } delete[]adjList;}//设置指定边的权值void Graph::setEdgeWeight(int tail, int head, int weight){ if (!isWeighted) //无权图 { while (!check(tail, head)) { cout << "输入的边不正确！又一次输入\n"; cin >> tail >> head; } insertEdge(tail, head); } else //有权图 { while (!check(tail, head, weight)) { cout << "输入的边不正确！又一次输入\n"; cin >> tail >> head >> weight; } insertEdge(tail, head, weight); }}//插入边void Graph::insertEdge(int vertex, int adjvex, int weight){ insertedge(vertex, adjvex, weight); if (!isDirected) //无向图 insertedge(adjvex, vertex, weight);}void Graph::insertedge(int vertex, int adjvex, int weight){ EdgeNode *p, *q, *r; p = q = r = NULL; if (adjList[vertex].next) //非第一个节点 { p = adjList[vertex].next; //移动p到合适位置 while (p && (p->adjvex < adjvex)) { q = p; p = p->next; } if (p && (p->adjvex == adjvex)) //改动已有边权值 p->weight = weight; else { r = new EdgeNode; r->adjvex = adjvex; r->weight = weight; r->next = p; //当增加的新节点位于表的第一个位置 if (adjList[vertex].next == p) adjList[vertex].next = r; else q->next = r; numE++; } } else { p = new EdgeNode; p->adjvex = adjvex; p->weight = weight; p->next = NULL; adjList[vertex].next = p; numE++; }}//输入检查bool Graph::check(int tail, int head, int weight){ if (tail >= 0 && tail < numV && head >= 0 && head < numV && weight > 0 && weight <= MAXWEIGHT) return true; else return false;}//打印邻接表void Graph::printAdjacentList(){ int i; EdgeNode *edge = NULL; for (i = 0; i < numV; i++) { edge = adjList[i].next; if (edge) //为什么加一个if推断？跟后面的换行有关。若某顶点无邻接点(无边)，则会空出一行 { while (edge) { cout << "w(" << i << "," << edge->adjvex << ")=" << edge->weight << " "; edge = edge->next; } cout << endl; } }} 主函数 int main(void){ cout << "******使用邻接表实现图结构***by David***" << endl; bool isDirected, isWeighted; int numV; cout << "建图" << endl; cout << "输入顶点数 "; cin >> numV; cout << "边是否带权值，0(不带) or 1(带) "; cin >> isWeighted; cout << "是否是有向图，0(无向) or 1(有向) "; cin >> isDirected; Graph graph(numV, isWeighted, isDirected); cout << "这是一个"; isDirected ? cout << "有向、" : cout << "无向、"; isWeighted ? cout << "有权图" << endl : cout << "无权图" << endl; graph.createGraph(); cout << "打印邻接表" << endl; graph.printAdjacentList(); cout << endl; int tail, head, weight; cout << "改动指定边的权值" << endl; if (isWeighted) //针对有权图 { cout << "输入边的起点、终点和权值 "; cin >> tail >> head >> weight; graph.setEdgeWeight(tail, head, weight); } else //针对无权图 { cout << "输入边的起点、终点 "; cin >> tail >> head; graph.setEdgeWeight(tail, head, 1); } cout << "改动成功！" << endl; cout << "打印邻接矩阵" << endl; graph.printAdjacentList(); system("pause"); return 0;} 执行 
邻接表
完整代码下载：
转载请注明出处，本文地址：
若有所帮助，顶一个哦！
专栏文件夹：