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

1. 在数据结构中对于图的存储主要有三种方式，分别为邻接矩阵，邻接表和边集，前两种比较常用，下面使用的是C++语言vector来实现邻接表并且实现深度优先搜索

因为对于初学者来说，使用链表来实现邻接表的话过程比较复杂，不太容易理解，存在多个结构体之间的相互嵌套，所以我们在学习的时候可以使用简单一点的工具来实现邻接表

2. 下面是具体的实现过程：

① 由于vector变长数组之称，因此可以开一个vector数组Adj[N]，其中N为顶点的个数，这样每个Adj[i]都是一个变长数组vector，使得存储空间只与图的边数是有关的

② 如果邻接表只存放每条边的终点编号而不存放边权那么我们可以将vector中的元素类型可以直接声明为int类型，如vector<int>

如果需要同时存储边的终点编号和边权，那么可以创建结构体Node，用来存放每条边的终点编号和边权，代码如下：

struct Node{	int v;	int weight;};

这样vector邻接表的每个元素的类型是Node类型的，此时如果我们需要添加一个从顶点1到顶点3的有向边，边权为4那么就可以已定义为一个Node类型的临时变量temp，令temp.v = 3，temp.w = ，然后把temp加入到Adj[1]中即可，代码如下：

Node temp;temp.v = 3;temp.w = 4;Adj[1].push_back(temp)

测试数据如下：

560 1 10 2 20 3 31 4 42 4 23 4 5

3. 下面是具体使用vector实现邻接表存储图并且实现深度优先搜索的代码（存储的是有向有权图）

#include
   
    #include
    
     #include
     
      #define maxSize 1000 using namespace std;struct Node{	int v;	int weight;};vector
      
        Adj[maxSize];bool vis[maxSize] = {false};void dfs(int u){	vis[u] = true;	cout << u << " ";	for(int i = 0; i < Adj[u].size(); i++){		Node node = Adj[u][i];		int v = node.v; 		if(vis[v] == false){			dfs(v);		}	}}int n, edges;int main(void){	cout << "输入图中的顶点数: ";	cin >> n;	cout << endl;	cout << "输入图中的边数: ";	cin >> edges;	cout << endl << "输入图中的起始顶点, 结束顶点和边的权重: " << endl;	int u = -1, v = -1, weight = -1;	for(int i = 0; i < edges; i++){		cin >> u >> v >> weight;		Node newNode;		newNode.v = v;		newNode.weight = weight;		Adj[u].push_back(newNode);	}		for(int i = 0; i < n; i++){		//判断Adj[i]是否为空 		if(!Adj[i].empty()){			cout << i << " ";			for(int j = 0; j < Adj[i].size(); j++){				Node pop = Adj[i][j];				cout << pop.v << " ";			}			cout << endl;		}	}	cout << "深度优先搜索顶点的结果如下: " << endl;	dfs(0);	return 0;}