一、邻接表的概念
邻接表是一种图的存储结构。它由一个链表数组组成，每个节点表示图中的一个顶点，每个节点对应的链表记录与该顶点相邻的所有顶点。
二、邻接表在有向图中的使用
有向图是一种图，其边有一个方向。邻接表在有向图中的使用，主要有以下两个方面：
1. 存储有向图信息
有向图中每一条有向边是从某一个顶点指向另一个顶点的，因此在邻接表中，与每个顶点对应的链表记录的是该顶点所指向的其他顶点。
比如，我们定义了一个有向图G(V,E)，其中V为顶点集合，E为有向边集合。那么G的邻接表定义如下：
class DirectedGraphNode {
public:
int val;
vector neighbors;
DirectedGraphNode(int x) : val(x) {};
};
在上述定义中，每个DirectedGraphNode表示有向图中的一个顶点，val为该顶点的值，neighbors为一个向量，记录该顶点所指向的其他顶点。
2. 基于邻接表的有向图算法
邻接表在有向图的算法中应用广泛，尤其是在图搜索、拓扑排序、最短路径等算法中。
三、邻接表在有向图中的实际案例
下面举一个实际案例来说明邻接表在有向图中的应用。
假设有一个学校，其中每个班级都有一个班主任和若干个学生。如果所有班主任之间都有指导关系，则可以将这些班主任看作图中的顶点，将指导关系看作图中的有向边。这样就可以将该学校的组织结构看作一个有向图。
为了方便存储和查询该学校的组织结构，可以使用邻接表来表示该有向图。具体做法如下：
1. 创建一个DirectedGraphNode类，用于表示有向图中的顶点。class DirectedGraphNode {
public:
string name; // 班主任姓名
vector neighbors; // 指导关系
DirectedGraphNode(string n) : name(n) {};
};
2. 创建一个函数createGraph，该函数将学校的组织结构转化成有向图，并返回图的根节点，即所有班主任之间都有指导关系的顶点。
DirectedGraphNode* createGraph() {
// 创建班主任节点
DirectedGraphNode* nodeA = new DirectedGraphNode("A");
DirectedGraphNode* nodeB = new DirectedGraphNode("B");
DirectedGraphNode* nodeC = new DirectedGraphNode("C");
DirectedGraphNode* nodeD = new DirectedGraphNode("D");
// 建立指导关系
nodeA->neighbors.push_back(nodeB);
nodeB->neighbors.push_back(nodeC);
nodeC->neighbors.push_back(nodeD);
nodeD->neighbors.push_back(nodeA);
return nodeA;
}
3. 创建一个函数findRoot，该函数根据有向图的组织结构，找出所有班主任之间都有指导关系的顶点，即图的根节点。如果存在多个根节点，则返回任意一个即可。
DirectedGraphNode* findRoot(DirectedGraphNode* node) {
queue q;
unordered_set
visited;
q.push(node);
visited.insert(node);
while (!q.empty()) {
DirectedGraphNode* cur = q.front();
q.pop();
for (int i = 0; i < cur->neighbors.size(); i++) {
DirectedGraphNode* neighbor = cur->neighbors[i];
if (visited.count(neighbor)) continue;
visited.insert(neighbor);
q.push(neighbor);
}
}
return node;
}
在上述代码中，我们使用广度优先搜索遍历了整个有向图，并将遍历到的顶点放入一个unordered_set中，以记录已经访问过的顶点。最后遍历结束后，unordered_set中剩余的顶点就是未被遍历到的顶点，它们之间未建立指导关系，因此它们不是图的根节点。剩下的顶点中任意一个都可以被认为是图的根节点。
