本文共 3218 字，大约阅读时间需要 10 分钟。

 1、邻接表表示法的基本思想：

       对图中的每个顶点vi都分别建立一个对应的单链表（对无向图称为“边表”，对有向图称为“出边表”）来存储所有邻接与顶点vi的边（对于有向图而言是指以vi为尾的弧），边表中的每个结点分别对应于邻接于顶点vi的一条边。边表中的每个结点主要包含两个域，其中邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置，链域(nextedge)指示下一条边或弧的结点。如果是带权图，还可以再加一个域weight，表示从vi到adjvex这条边的权值。

       对于图中的所有顶点信息，用一个一维数组（称为“顶点表”）来存放。对于顶点表中的每个顶点单元，需要存放：该顶点信息值(data)、一个指向由邻接于该顶点的所有的边组成的边表的头指针(firstedge)。

       如下图所示：

2、代码描述：

       ALGraph.h文件： 

#pragma once#ifndef _ALGRAPH_H_#define _ALGRAPH_H_#include 
   
    #include 
    
     using namespace std;struct EdgeNode				//出边表的结点结构类型{	int adjvex;				//该边的终点位置	int weight;				//边的权值	EdgeNode* nextedge;		//指向下一条边的指针};struct VexNode				//顶点表的元素结构类型{	char data;				//顶点信息	EdgeNode* firstedge;	//指向该顶点对应的出边表的指针};class ALGraph{public:	ALGraph(vector
     
       vexs, int n, int e);	//构造函数	void DFSTraverse();							//深度优先遍历图private:	int vexnum;	int edgenum;							//顶点数、边数	vector
      
        adjlist;				//顶点表 - 存储图中的所有顶点信息	void DFS(int v, bool* visited);			//连通图的深度优先遍历        void DFS(int v, bool* visited);			//连通图的深度优先遍历};#endif
      
     
    
   

        ALGraph.cpp文件：

#include "ALGraph.h"/*有向图的邻接表建立算法：	参数vexs为存储各顶点值的数组，参数 n 和 e 分别为顶点数和边数*/ALGraph::ALGraph(vector
   
     vexs, int n, int e){	vexnum = n;	edgenum = e;							//确定图的顶点个数和边数	adjlist.resize(vexnum);	//初始化顶点表	for (int i = 0; i < vexnum; ++i)	{		adjlist[i].data = vexs[i];		adjlist[i].firstedge = 0;	}	//依次输入所有的边的信息	EdgeNode* p;	for (int j = 0; j < edgenum; ++j)	{		int va, vb, w;		cin >> va >> vb >> w;					//输入一条边邻接的两个顶点的序号		p = new EdgeNode;						//产生第一个表结点		p->adjvex = vb;		p->weight = w;		p->nextedge = adjlist[va].firstedge;		//插在表头		adjlist[va].firstedge = p;	}}/*连通图的深度优先遍历递归算法*/void ALGraph::DFS(int v, bool* visited){	cout << adjlist[v].data << endl;	//访问第v的顶点	visited[v] = true;			//设置访问标志为true(已访问)	EdgeNode* p = adjlist[v].firstedge;	while (p)	{		int i = p->adjvex;		if (!visited[i])		{			DFS(i, visited);		}		p = p->nextedge;	}	return;}/*图的深度优先遍历递归算法*/void ALGraph::DFSTraverse(){	bool* visited = new bool[vexnum];		//建立访问标记数组	for (int v = 0; v < vexnum; ++v)	{		visited[v] = false;					//初始化访问标记数组(未访问)	}	for (int v = 0; v < vexnum; ++v)	{		if (!visited[v])		{			DFS(v, visited);		}	}	delete []visited;	return;}/*拓扑排序*/void ALGraph::TopoSort(){	int* indegree = new int[vexnum];		//存放各顶点入度的数组	SeqQueue
    
      s;					//存储所有入度为0的顶点	for (int i = 0; i < vexnum; ++i)	{		indegree[i] = 0;	}	EdgeNode* p;	for (int i = 0; i < vexnum; ++i)		//求所有顶点的入度	{		p = adjlist[i].firstedge;		for (; p; p = p->nextedge)		{			++(indegree[p->adjvex]);		}	}	for (int i = 0; i < vexnum; ++i)		//使入度为0的顶点入队	{		if (!indegree[i])		{			s.EnQueue(i);		}	}		while (!s.Empty())	{		int i = s.DeQueue();				//出队		cout << adjlist[i].data;			//输出顶点		p = adjlist[i].firstedge;		for (; p; p = p->nextedge)		{			--(indegree[p->adjvex]);			if (!indegree[p->adjvex])			{				s.EnQueue(p->adjvex);			}		}	}	delete[]indegree;}
    
   

       test.cpp文件：

/*多段图中的最短路径问题*/#include 
   
    #include 
    
     #include "ALGraph.h"using namespace std;int main(){	//建立多段图	int n, e;		//n为顶点数，e为边数	cin >> n >> e;	vector
     
       vexs;		//顶点表	for (int i = 0; i < n; ++i)	{		char temp;		cin >> temp;		vexs.push_back(temp);	}	ALGraph ms(vexs, n, e);		//建立一个有向图	ms.DFSTraverse();        ms.TopoSort();	return 0;}
     
    
   

3、测试：

转载地址：http://tttai.baihongyu.com/