首页 数据结构（C++）
  1. 图
    1.1 图的抽象数据类型
    1.2 图的模版基类
  2. 邻接矩阵（相邻矩阵）
    2.1 类定义
    2.2 构造函数
  3. 邻接表
    3.1 类定义
    3.2 构造函数
    3.3 析构函数
    3.4 建立算法
  4. 图的遍历
    4.1 深度优先遍历算法 (DFS)
    4.2 广度优先遍历算法 (BFS)
  5. 四叉特征数
    5.1 存储结构
    5.2 前序遍历算法 (深度优先遍历)
    5.3 层次遍历算法 (广度优先遍历)
  6. 迷宫问题
    6.1 深度优先遍历
    6.2 广度优先遍历
  7. 最小生成树
    7.1 克鲁斯卡尔算法 (Kruskal 算法)
    7.2 普里姆算法 (Prim 算法)
    7.3 迪杰斯特拉算法 (dijkstra 算法)
  8. 拓扑排序

# 一、图

# 1. 图的抽象数据类型

// 图的抽象数据类型
template<class T>
class Graph
{
    // 对象：由一个顶点的非空集合和一条边集合构成
    // 每条边由一个顶点来表示
public:
    Graph();// 建立一个空的图
    void insertVertex(const T &vertex);// 插入一个顶点 vertex，该顶点暂时没有入边
    void insertEdge(int v1,int v2,int weight);// 在图中插入一条边 (v1,v2,w)
    void removeVertex(int v);// 在图中删除顶点 V 和所有关联到它的边
    void removeEdge(int v1,int v2);// 在图中删去边 (v1,v2)
    bool IsEmpty();// 若图中没有顶点，则返回 true，否则返回 false
    T getWeight(int v1,int v2);// 函数返回边 (v1,v2) 的权值
    int getFirstNeighbor(int v);// 给出顶点 V 第一个邻接顶点的位置
    int getNextNeighbor(int v,int w);// 给出顶点 v 的某邻接顶点 w 的下一个邻接顶点
};


# 2. 图的模版基类

const int maxWeight=0x3f3f3f3f;// 无穷大的值
const int DefaultVertices=30;// 最大顶点数
template<class T,class E>
class Graph
{
protected:
    int maxVertices;// 图中最大顶点数
    int numEdges;// 当前边数
    int numVertices;// 当前顶点数
    int getVertexPos(T vertex);// 给出顶点 vertex 在图中的位置
public:
    Graph(int sz=DefaultVertices);// 构造函数
    ~Graph();
    bool GraphEmpty() const// 判图空否
    {
        return numEdges==0;
    }
    int NumberOfVertices()// 返回当前顶点数
    {
        return numVertices;
    }
    int NumberOfEdges()// 返回当前边数
    {
        return numEdges;
    }
    virtual T getValue(int i);// 取顶点 i 的值
    virtual E getWeight(int v1,int v2);// 取边上权值
    virtual int getFirstNeighbor(int v);// 取顶点 V 的第一个邻接顶点
    virtual int getNextNeighbor(int v,int w);// 取邻接顶点 W 的下一邻接顶点
    virtual bool insertVertex(const T vertex);// 插入到一个顶点 vertex
    virtual bool insertEdge(int v1,int v2,E cost);// 插入边 (v1,v2)，权为 cost
    virtual bool removeVertex(int v);// 删去顶点 V 和所有与其相关联边
    virtual bool removeEdge(int v1,int v2);// 在图中删去边 (v1,v2)
};

# 二、邻接矩阵（相邻矩阵）
image-20251121105356089
image-20251121105404522
image-20251121105427774

# 1. 类定义
template<class T,class E>
class Graphmtx:public Graph<T,E>
{
    friend istream &operator>>(istream &in,Graphmtx<T,E> &G);// 输入
    friend ostream &operator<<(ostream &out,Graphmtx<T,E> &G);// 输出
private:
    T *VerticesList;// 顶点表
    E **Edge;// 邻接矩阵
    int getVertexPos(T vertex)// 查找某个顶点的位置
    {
        for(int i=0;i<numVertices;i++)
        {
            if(VerticesList[i]==vertex)
            {
                return i;
            }
        }
        return -1;
    }
public:
    Graphmtx(int sz=DefaultVertices);// 构造函数
    ~Graphmtx()// 析构函数
    {
        for(int i=0;i<numVertices;i++)
        {
        	delete [] Edge[i];// 逐行释放内存
        }
        delete []VerticesList;
        delete []Edge;
    }
    T getValue(int i)
    {
        return (i>=0 && i<=numVertices ? VerticesList[i] : NULL);
    }
    E getWeight(int v1,int v2)// 取边 (v1,v2) 上权值
    {
        return v1!=-1 && v2 !=-1 ? Edge[v1][v2] : 0;
    }
    int getFirstNeighbor(int v);// 取顶点 V 的第一个邻接顶点
    int getNextNeighbor(int v,int w);// 取邻接顶点 W 的下一邻接顶点
    bool insertVertex(const T vertex);// 插入到一个顶点 vertex
    bool insertEdge(int v1,int v2,E cost);// 插入边 (v1,v2)，权为 cost
    bool removeVertex(int v);// 删去顶点 V 和所有与其相关联边
    bool removeEdge(int v1,int v2);// 在图中删去边 (v1,v2)
};

# 2. 构造函数
image-20251121151454394
template<class T,class E>
Graphmtx<T,E>::Graphmtx(int sz)// 构造函数
{
    maxVertices=sz;// 最大能放多少个顶点
    numVertices=0;// 当前顶点个数
    numEdges=0;// 当前边个数
    int i,j;
    VerticesList=new T[maxVertices];// 创建顶点表
    Edge=(E**)new E *[maxVertices];
    for(i=0;i<maxVertices;++i)// 开一个 maxVertices*maxVertices 大小的数组
    {
        Edge[i]=new int[maxVertices];
        for(j=0;j<maxVertices;++j)
        {
            Edge[i][j]=(i==j)?0:maxWeight;// 对角线设为 0，其余设为无穷大
        }
    }
}


# 三、邻接表
image-20251121151552500
image-20251121151602660
# 1. 类定义
image-20251121160935211
image-20251121161633471
// 链表的结点结构类
template<class T,class E>
struct Edge// 边结点的定义
{
    int dest;// 边的另一顶点位置   这条边指向哪个顶点（下标）
    E cost;// 边上的权值
    Edge<T,E> *link;// 下一条边链指针
    Edge(){}// 构造函数
    Edge(int num,E weight):dest(num),cost(weight),link(NULL){}
    bool operator!=(Edge<T,E> &R) const
    {
        return dest!=R.dest;// 判边等否
    }
};
// 顺序表结点结构类
template<class T,class E>
struct Vertex// 顶点的定义
{
    T data;// 顶点的名字
    Edge<T,E> *adj;// 边链表的头指针
};
// 邻接表类
template<class T,class E>
class Graphlnk : public Graph<T,E>
{
    friend istream &operator>>(istream &in,Graphlnk<T,E> &G);// 输入
    friend ostream &operator<<(ostream &out,Graphlnk<T,E> &G);// 输出
private:
    Vertex<T,E> *NodeTable;// 顶点表
    int getVertexPos(const T vertx)
    {
        for(int i=0;i<numVertices;++i)
        {
            if(NodeTable[i].data==vertx)
            {
                return i;
            }
        }
        return -1;
    }
public:
    Graphlnk(int sz=DefaultVertices);// 构造函数
    ~Graphlnk();// 析构函数
    T getValue(int i)// 取顶点 i 的值
    {
        return(i>=0 && i<numVertices)? NodeTable[i].data:0;
    }
    E getWeight(int v1,int v2);// 取边 (v1,v2) 权值
    bool insertVertex(const T &vertex);// 插入顶点
    bool removevertex(int v);// 删除顶点
    bool insertEdge(int v1,int v2,E cost);// 插入边
    bool removeEdge(int v1,int v2);// 删除边
    int getFirstNeighbor(int v);// 获取 v 的第一个邻接点
    int getNextNeighbor(int i,int w);// 获取 w 后的邻接点
    void CreateNodeTable();// 建立邻接表结构
};


# 2. 构造函数
template<class T,class E>
Graphlnk<T,E>::Graphlnk(int sz)// 构造函数
{
    maxVertices=sz;
    numVertices=0;
    numEdges=0;
    NodeTable=new Vertex<T,E>[maxVertices];// 创建顶点表数组
    if(NodeTable==NULL)
    {
        cerr <<"存储分配错！" <<endl;
        exit(1);
    }
    for(int i=0;i<maxVertices;++i)
    {
        NodeTable[i].adj=NULL;
    }
}

# 3. 析构函数
template<class T,class E>
Graphlnk<T,E>::~Graphlnk()// 析构函数
{
    for(int i=0;i<numVertices;++i)
    {
        Edge<T,E> *p=NodeTable[i].adj;
        while(p!=NULL)
        {
            NodeTable[i].adj=p->link;
            delete p;
            p=NodeTable[i].adj;
        }
    }
    delete []NodeTable;// 删除顶点表数组
}

# 4. 建立算法
image-20251121163457574
image-20251121163652884
template<class T,class E>
void Graphlnk<T,E>::CreateNodeTable()// 建立邻接表结构
{
    //n：顶点个数			i：当前处理第几个顶点
    //m：某个顶点的邻接点数量	p：指向边结点的指针（邻接表里的链表结点）
    int n,i,j,m;
    Edge<T,E> *p;
    cin >>n;// 结点个数
    for(i=1;i<=n;++i)
    {
        NodeTable[i].adj=0;// 预设为空链
        cin >>NodeTable[i].data;// 输入结点值
        cin >>m;// 每个结点的邻接点个数
        for(j=0;j<m;++j)
        {
            p=new Edge<T,E>;// 生成一个新结点
            cin >>p->dest;// 建立边结点，输入结点值到 dest 域
            cin >>p->cost;// 带权图则多加一个权值的输入
            p->link=NodeTable[i].adj;
            NodeTable[i].adj=p;// 头插入建链
        }
    }

# 四、图的遍历
# 1. 深度优先遍历算法 (DFS)
// 深度优先遍历算法
void Graphlnk<T,E>::DFS(int v)// 私有函数
{
    // 从顶点 v 出发，深度优先遍历连通图 G
    visited[v]=true;// 1. 标记当前点 v 已访问
    cout <<NodeTable[v].data;// 2. 输出这个顶点
    p=NodeTable[v].adj; //p 指向 v 的第一个邻接边（链表头）
    while(p!=NULL)// 找出邻接点逐个进行递归调用
    {
        if(!visited[p->dest])// 3. 如果这个邻接点没有访问过
        {
            DFS(p->dest);// 4. 递归访问它
            p=p->link;// 5. 查看下一个邻接点
        }
    }
}
bool *visited;// 成员属性，，辅助数组
int numVertices;// 成员属性，结点个数
visited=new bool[n];// 加入到 Graplnk 构造函数中
cin >>numVertices;
void Graphlnk<T,E>::dfs()
{
    int i,v0;
    for(i=0;i<numVertices;++i)
    {
        visited[i]=false;// 初始化 visited 数组
    }
    cin >>v0;// 输入深度优先遍历的出发点
    dfs(v0);// 调用深度优先的递归函数
}

# 2. 广度优先遍历算法 (BFS)
template<class T, class E>
void Graphlnk<T,E>::BFS()
{
    queue<int> qu;
    int v;
    cin >> v; // 输入起点
    // 初始化 visited
    for(int i = 0; i < numVertices; ++i)
        visited[i] = false;
    // 起点入队
    qu.push(v);// 起点入队，并标记为已访问
    visited[v] = true;
    while(!qu.empty())// 队列不空就继续处理
    {
        int cur = qu.front();// 取队头元素（当前访问的节点）
        qu.pop();
        cout << NodeTable[cur].data;
        Edge<T,E>* p = NodeTable[cur].adj;//p 指向当前节点 cur 的邻接链表的头（第一个邻接点）
        // 遍历邻接点
        while(p != NULL)// 遍历邻接链表中所有邻接点
        {
            if(!visited[p->dest])// 若该邻接点未访问过
            {
                visited[p->dest] = true;// 标记已访问（避免重复入队）
                qu.push(p->dest);
            }
            p = p->link;
        }
    }
}


# 五、四叉特征数
image-20251121184654921
# 1. 存储结构
// 存储结构
struct treenode
{
    int data;
    struct treenode *child[4];
};


# 2. 前序遍历算法 (深度优先遍历)
image-20251121194549322
// 前序遍历算法
void DFS(node *root)
{
    if (root == NULL) return;
    cout << root->data << " ";
    for (int i = 0; i < 4; i++)
    {
        DFS(root->child[i]);
    }
}

// 前序遍历算法 (深度优先遍历)
void DFS(struct node *root)
{
    if (root == NULL)
    {
        return;
    }
    cout << root->data << " ";
    int i = 0;
    while (i < 4)
    {
        DFS(root->child[i]);
        i++;
    }
}

# 3. 层次遍历算法 (广度优先遍历)
image-20251121194653396
// 层次遍历算法
void BFS(struct treenode *root)
{
    if(!root)
    {
        return;
    }
    queue<treenode *> qu;
    qu.push(root);
    while(!qu.empty())
    {
        treenode *temp = qu.front();
        qu.pop();
        cout << temp->data << " ";
        for(int i = 0; i < 4; ++i)
        {
            if(temp->child[i] != NULL)
            {
                qu.push(temp->child[i]);
            }
        }
    }
}


# 六、迷宫问题
image-20251121211945819
# 1. 深度优先遍历
image-20251121211922056
int MazePath(int x, int y)
{
    int loop;
    Maze[x][y] = -1; // 标志入口位置已到达过
    for(loop = 0; loop < 8; loop++) // 探索当前位置的 8 个相邻位置
    {
        x = x + move[loop].x;  // 计算新位置 x
        y = y + move[loop].y;  // 计算新位置 y
        if((x == m) && (y == n)) // 如果到达出口
        {
            PrintPath();   // 输出路径
            Restore(Maze); // 恢复迷宫
            return 1;      // 找到路径
        }
        if(Maze[x][y] == 0) // 新位置可以通过
        {
            ..........// 保存该点坐标（用于以后打印路径）
            MazePath(x, y);
        }
    }
    return 0; // 所有方向都试完了，仍没找到，返回失败
}

# 2. 广度优先遍历
int maze[m+2][n+2];
struct DataType {
    int x, y, pre;
};
int MazePath() {
    queue<DataType> q;      // II 定义一个容量为 m*n 的队列
    DataType Temp1, Temp2;  // DataType { int x, int y , int pre; };
    int x, y, loop;
    Temp1.x = 1;
    Temp1.y = 1;
    Temp1.pre = -1;
    maze[1][1] = -1;        // Il 标志入口位置已到达过
    q.push(Temp1);          // II 将入口位置入列
    while (!q.empty())      // II 队列非空，则反复探索
    {
        Temp2 = q.front();
        q.pop();            // I / 队头元素出列
        for (loop = 0; loop < 8; loop++)   // ⅡI 探索当前位置的 8 个相邻位置
        {
            x = Temp2.x + move[loop].x;    // II 计算出新位置 x 位置值
            y = Temp2.y + move[loop].y;    // !l 计算出新位置 x 位置值
            if ((x == m) && (y == n))      // I/ 成功到达出口
            {
                PrintPath(q);              // II 输出路径 该函数请自行完成
                Restore(maze);             // II 恢复迷宫 i 该函数请自行完成
                return (1);                // I / 表示成功找到路径
            }
            if (maze[x][y] == 0)           // II 新位置是否可到达
            {
                Temp1.x = x;
                Temp1.y = y;
                // Temp1.pre = q.front;    // 设置到达新位置的前趋位置
                maze[x][y] = -1;           // I / 标志该位置已到达过
                q.push(Temp1);             //// 新位置入列
            }
        }
    }
    return (0);                             // ⅡI 表示查找失败，即迷宫无路径
} // MazePath


# 七、最小生成树
image-20251122091037575
image-20251122091051279
# 1. 克鲁斯卡尔算法 (Kruskal 算法)
image-20251122121100868
image-20251122132348587
通过小根堆选最小边 + 并查集判断是否成环，构建最小生成树
// 初始化操作
// 图中所有边的数据（结点，结点，权）插入堆中。
for (u = 0; u < n; u++)         // 图采用邻接矩阵
{
    for (v = u + 1; v < n; v++)
    {
        if (Edge[u][v] < maxWeight)
        {
            ed.tail = u;
            ed.head = v;
            ed.cost = Edge[u][v];
            // 插入堆
            H.Insert(ed);
        }
    }
}
count = 1;   // 最小生成树边数计数
while (count < n)   // 反复执行，取 n-1 条边
{
    H.Remove(ed);   // 从堆中取权值最小的边
    // 检查该边的两个顶点是否在同一集合中
    // 查找出该两顶点所在集合的根 u 与 v — 并查集
    u = F.Find(ed.tail);
    v = F.Find(ed.head);
    if (u != v)   // 不是同一集合，不连通
    {
        F.Union(u, v);      // 集合合并，连通它们 — 并查集
        MST.Insert(ed);     // 将该边放入生成树 MST 中
        //cout << ed.tail << ed.head << ed.cost;  // 输出边（如需要）
        count++;
    }
}


# 2. 普里姆算法 (Prim 算法)
image-20251122123439134
image-20251122133142340
image-20251122132201618
image-20251122132216933
​
template <class T, class E>
struct MSTEdgeNode   // 树边结点的类定义
{
    int head;   // 未加入生成树的结点编号
    int tail;   // 已加入生成树的结点编号
    E cost;     // 权值
    // 这里应该还有 < 重载
};
MinHeap<MSTEdgeNode<T, E>> H(m);  // 最小堆
Edge[u][u] = true;   //u 加入生成树
count = 1;           // 记录已加入生成树的边数
while (count < n)
{
    // 逐个查看 v 是否在生成树中
    for (v = 0; v < n; v++)
    {
        if ((Edge[v][v] == 0) && Edge[u][v] < maxWeight)
        {
            ed.tail = u;
            ed.head = v;
            ed.cost = Edge[u][v];
            // (u, v, w) 加入堆
            H.Insert(ed);
        }
    }
    while (!H.IsEmpty() && count < n)
    {
        H.Remove(ed);   // 从堆中删除最小权的边
        // 是否符合选择要求
        if (Edge[ed.head][ed.head] == 0)
        {
            MST.Insert(ed);  // 将该边加入最小生成树
            //cout <<ed.tail <<ed.head <<ed.cost;   // 输出边（如需要）
            u = ed.head;
            Edge[u][u] = true;   //u 加入生成树
            count++;
            break;
        }
    }
}


# 3. 迪杰斯特拉算法 (dijkstra 算法)
//v0 为起点
for (i = 0; i < n; i++)      //n 表示结点个数
{
    dist[i] = G[v0][i];      // 初始化 dist 数组：dist [i]= 起点 v0 到 i 的距离
}
G[v0][v0] = 1;               // 将 v0 加入 “已访问集合”
for (i = 0; i < n - 1; i++)  // 共需确定 n-1 个结点
{
    // 找到尚未访问、dist 最小的结点
    min = 32767;
    for (k = 0; k < n; k++)
    {
        if (G[k][k] == 0 && dist[k] < min)
        {
            pos = k;
            min = dist[k];
        }
    }
    G[pos][pos] = 1;         // 将 pos 加入 “已访问集合”
    // 用新加入的结点 pos 来更新 dist []
    for (j = 0; j < n; j++)
    {
        if (G[j][j] == 0 && G[pos][j] + min < dist[j])
        {
            dist[j] = G[pos][j] + min;
        }
    }
}


# 八、拓扑排序
image-20251122133723466
基于入度的拓扑排序：
找入度 0 → 入栈 → 出栈输出 → 消除出边 → 新的入度 0 入栈
若最终未处理完所有节点，则图有环。
1. 在 count 数组中找出入度为零的顶点，并分别入栈;
2. while(栈非空)
   {
	    出栈到 v;
        cout << NodeTable[v].data;
        ++m;
        p = NodeTable[v].adj;
        while (p != NULL)
        {
            count[p->dest]--;           //v → p->dest，去掉这条边，入度减 1
            如果 count[p->dest] == 0 则把它入栈
            p = p->link;                   // 链到下一个邻接点
        }
    }
3. if (m < n)
   {
        cout << "图中有回路"
   }
      
 更新于