数据结构图的存储

2023-12-14 12:30:42

在数据结构中图算是个较为难理解的结构形式了。

大致我们可以分为两个大类：
1、通过数组实现
2、通过链表实现

而链表的实现方式还可以继续细分：邻接表、邻接多重表、十字链表

所以关于图的结构的存储这里我们介绍四种基本形式：
1、邻接矩阵（数组）
2、邻接表（链表）
3、邻接多重表（链表）
4、十字链表（链表）

在C++中，图的存储方式通常有两种：邻接矩阵和邻接表。

邻接矩阵：

#include <iostream>
#include <vector>

using namespace std;

const int MAX_VERTICES = 100;

class Graph {
private:
    int vertices;
    vector<vector<int>> adjacencyMatrix;

public:
    Graph(int V) : vertices(V), adjacencyMatrix(V, vector<int>(V, 0)) {}

    void addEdge(int start, int end) {
        adjacencyMatrix[start][end] = 1;
        adjacencyMatrix[end][start] = 1;  
    }

    void printGraph() {
        for (int i = 0; i < vertices; ++i) {
            for (int j = 0; j < vertices; ++j) {
                cout << adjacencyMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph g(5);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(3, 4);

    g.printGraph();

    return 0;
}

邻接表：

#include <iostream>
#include <list>

using namespace std;

class Graph {
private:
    int vertices;
    list<int> *adjacencyList;

public:
    Graph(int V) : vertices(V), adjacencyList(new list<int>[V]) {}

    void addEdge(int start, int end) {
        adjacencyList[start].push_back(end);
    }

    void printGraph() {
        for (int i = 0; i < vertices; ++i) {
            cout << i << ": ";
            for (const auto &neighbor : adjacencyList[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph g(5);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(3, 4);

    g.printGraph();

    return 0;
}

在这里，顶点从0到V-1编号。你可以根据需要选择合适的表示方式，邻接矩阵适合稠密图，而邻接表适合稀疏图。

当涉及到图的存储时，除了邻接矩阵和邻接表之外，还有其他一些高级的表示方式，如邻接多重表和十字链表。

3.邻接多重表：

邻接多重表主要用于存储无向图，其中每条边都有一个表结点。每个表结点包含两个指针，分别指向该边的两个顶点，并包含一些边的信息。这种表示方法在处理无向图时更为直观。下面是一个简化的例子：

class Graph {
private:
    struct EdgeNode {
        int vertex1, vertex2;
        EdgeNode* next1;
        EdgeNode* next2;

        EdgeNode(int v1, int v2) : vertex1(v1), vertex2(v2), next1(nullptr), next2(nullptr) {}
    };

    vector<EdgeNode*> edgeList;

public:
    Graph(int V) : edgeList(V, nullptr) {}

    void addEdge(int start, int end) {
        EdgeNode* edge = new EdgeNode(start, end);
        // Update pointers
        edge->next1 = edgeList[start];
        edgeList[start] = edge;

        edge->next2 = edgeList[end];
        edgeList[end] = edge;
    }

    void printGraph() {
        for (int i = 0; i < edgeList.size(); ++i) {
            cout<< i << ": ";
            EdgeNode* edge = edgeList[i];
            while (edge != nullptr) {
                cout << "(" << edge->vertex1 << "," << edge->vertex2 << ") ";
                edge = edge->next1;
            }
            cout << endl;
        }
    }
};

4.** 十字链表**：

十字链表适用于有向图，它在邻接表的基础上进一步改进，以有效地表示有向边。每个结点包含两个指针，分别指向入边和出边，以及一些边的信息。下面是一个简化的例子：

class Graph {
private:
    struct Node {
        int vertex;
        Node* next;

        Node(int v) : vertex(v), next(nullptr) {}
    };

    struct ArcNode {
        int endVertex;
        ArcNode* nextIn;
        ArcNode* nextOut;

        ArcNode(int end) : endVertex(end), nextIn(nullptr), nextOut(nullptr) {}
    };

    vector<Node*> nodeList;

public:
    Graph(int V) : nodeList(V, nullptr) {}

    void addEdge(int start, int end) {
        ArcNode* arc = new ArcNode(end);
        arc->nextOut = nodeList[start];
        nodeList[start] = arc;

        Node* node = new Node(start);
        node->next = nodeList[end];
        nodeList[end] = node;
    }

    void printGraph() {
        for (int i = 0; i < nodeList.size(); ++i) {
            cout  << i << ": ";
            ArcNode* arcOut = nodeList[i];
            while (arcOut != nullptr) {
                cout << arcOut->endVertex << " ";
                arcOut = arcOut->nextOut;
            }
            cout << endl;

            cout << i << ": ";
            Node* nodeIn = nodeList[i];
            while (nodeIn != nullptr) {
                cout << nodeIn->vertex << " ";
                nodeIn = nodeIn->next;
            }
            cout << endl;
        }
    }
};

下面是一些练习题：
1.无向图的连通分量

【问题描述】求解无向图的连通分量。
【输入形式】第一行：顶点数边数；第二行：顶点；第三行及后面：边（每一行一条边）
【输出形式】分量:顶点集合（顶点按从小到大排序输出）（每个连通分量输出占用一行）
【样例输入】
6 5
ABCDEF
A B
A E
B E
A F
B F
【样例输出】
1:ABEF
2:C
3:D

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

class Graph {
private:
    map<char, vector<char> > adjacencyList;
    map<char, bool> visited;

public:
    void addEdge(char u, char v) {
        adjacencyList[u].push_back(v);
        adjacencyList[v].push_back(u);
    }

    void DFS(char vertex, set<char>& component) {
        visited[vertex] = true;
        component.insert(vertex);

        for (vector<char>::iterator it = adjacencyList[vertex].begin(); it != adjacencyList[vertex].end(); ++it) {
            char neighbor = *it;
            if (!visited[neighbor]) {
                DFS(neighbor, component);
            }
        }
    }

    vector<set<char> > getConnectedComponents() {
        vector<set<char> > components;
        visited.clear();

        for (map<char, vector<char> >::const_iterator it = adjacencyList.begin(); it != adjacencyList.end(); ++it) {
            char vertex = it->first;
            if (!visited[vertex]) {
                set<char> component;
                DFS(vertex, component);
                components.push_back(component);
            }
        }

        return components;
    }
};

int main() {
    int vertices, edges;
    cin >> vertices >> edges;

    Graph graph;

    string verticesStr;
    cin >> verticesStr;


    for (string::iterator it = verticesStr.begin(); it != verticesStr.end(); ++it) {
        char vertex = *it;
        graph.addEdge(vertex, vertex);
    }


    for (int i = 0; i < edges; ++i) {
        char u, v;
        cin >> u >> v;
        graph.addEdge(u, v);
    }

    vector<set<char> > components = graph.getConnectedComponents();

    for (int i = 0; i < components.size(); ++i) {
        set<char> component = components[i];
        cout << i + 1 << ":";

        for (set<char>::iterator it = component.begin(); it != component.end(); ++it) {
            cout << *it;
        }

        cout << endl;
    }

    return 0;
}

无向图顶点的度

【问题描述】已知一个无向图，求解该无向图中顶点的度。输入：无向图的顶点数及边数，各顶点及边，某顶点；输出：该顶点的度。
【输入形式】第一行：顶点数、边数，第二行：顶点；第三行开始：边（一条边占用一行），最后一行：顶点（求该顶点的度）
6 8
ABCDEF
A B
A C
A D
B C
B D
C D
C E
E F
A
【输出形式】3

#include <iostream>
#include <vector>
#include <map>

using namespace std;

// 计算指定顶点的度数
int calculateDegree(int vertex, const vector<vector<bool> > &adjacencyMatrix)
{
    int degree = 0;
    for (size_t i = 0; i < adjacencyMatrix[vertex].size(); ++i)
    {
        if (adjacencyMatrix[vertex][i])
        {
            degree++;
        }
    }
    return degree;
}

int main()
{
    int vertices, edges;
    cin >> vertices >> edges;

    // 构建顶点映射表
    map<char, int> vertexMap;
    vector<char> vertexList(vertices);
    for (int i = 0; i < vertices; ++i)
    {
        cin >> vertexList[i];
        vertexMap[vertexList[i]] = i;
    }

    // 构建邻接矩阵
    vector<vector<bool> > adjacencyMatrix(vertices, vector<bool>(vertices, false));
    for (int i = 0; i < edges; ++i)
    {
        char start, end;
        cin >> start >> end;
        adjacencyMatrix[vertexMap[start]][vertexMap[end]] = true;
        adjacencyMatrix[vertexMap[end]][vertexMap[start]] = true;
    }

    // 输入要查询的顶点
    char queryVertex;
    cin >> queryVertex;

    // 计算顶点度数并输出
    int degree = calculateDegree(vertexMap[queryVertex], adjacencyMatrix);
    cout  << degree << endl;

    return 0;
}

图的存储结构

【问题描述】已知无向图的邻接矩阵存储结构，构造该图的邻接表存储结构。其中函数createMGraph用于创建无向图的邻接矩阵存储结构;函数createALGraph(ALGraph &G,MGraph G1)根据无向图的邻接矩阵存储结构G1，构建图的链接表存储结构G;函数printAdjustVex实现遍历邻接表，打印各顶点及邻接点。请根据上下文，将程序补充完整。
【输入形式】第一行：顶点数n和边数e；第一行：顶点序列；接着的e行：边依附的两个顶点在顶点数组中的索引
【输出形式】n行。每一行内容为：顶点:邻接点序列
【样例输入】
6 5
ABCDEF
0 1
0 4
1 4
0 5
1 5
【样例输出】
A:BEF
B:AEF
C:
D:
E:AB
F:AB

#include  <iostream>
using  namespace  std;
#define  MaxVexNum  20                                //最大顶点数设为20
struct    MGraph
{
        char  vexs[MaxVexNum];                      //顶点表
        int  arcs[MaxVexNum][MaxVexNum];  //邻接矩阵
        int  vexnum,arcnum;                            //图中顶点数和边数
};                                                                    //MGragh是以邻接矩阵存储的图类型
struct  ArcNode
{
        int  adjvex;                                          //邻接点域
        struct  ArcNode    *  nextarc;            //指向下一个邻接点的指针域
}  ;                                                                  //可增加一个数据域info表示边或弧的信息
struct  VNode
{
        char    data;                                          //顶点信息
        ArcNode    *  firstarc;                        //边表头指针
};
struct  ALGraph
{
        VNode  vertices[MaxVexNum];
        int  vexnum,arcnum;                            //顶点数和边数
}  ;
void  createMGraph(MGraph  &G)
{
        int  u,v;
        cin>>G.vexnum>>G.arcnum;
        for(int  i=0;  i<G.vexnum;  i++)
                cin>>G.vexs[i];
        for(int  i=0;  i<G.vexnum;  i++)
                for(int  j=0;  j<G.vexnum;  j++)
                        G.arcs[i][j]=0;
        for(int  i=1;  i<=G.arcnum;  i++)
        {
                cin>>u>>v;
                G.arcs[u][v]=1;
                G.arcs[v][u]=1;
        }
}
void createALGraph(ALGraph &G, MGraph G1)
{
    G.vexnum = G1.vexnum;
    G.arcnum = G1.arcnum;

    for (int i = 0; i < G1.vexnum; i++)
    {
        G.vertices[i].data = G1.vexs[i];
        G.vertices[i].firstarc = NULL;
    }

    for (int i = G1.vexnum - 1; i >= 0; i--)
    {
        for (int j = G1.vexnum - 1; j >= 0; j--)
        {
            if (G1.arcs[i][j] == 1)
            {
                ArcNode *newArc = new ArcNode;
                newArc->adjvex = j;
                newArc->nextarc = G.vertices[i].firstarc;
                G.vertices[i].firstarc = newArc;
            }
        }
    }
}

void  printAdjustVex(ALGraph  G)
{
        for(int  i=0;i<G.vexnum;i++)
        {
                cout<<G.vertices[i].data<<":";
                ArcNode    *p=G.vertices[i].firstarc;
                while(p)
                {
                        cout<<G.vertices[p->adjvex].data;
                        p=p->nextarc;
                }
                cout<<endl;
        }

}
int  main()
{
        MGraph  G;
        ALGraph  G1;
        createMGraph(G);
        createALGraph(G1,G);
        printAdjustVex(G1);
}

文章来源:https://blog.csdn.net/m0_73814009/article/details/134992099
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！

数据结构 图的存储

数据结构图的存储