网站建设公司小猫建站,网站制作成品,安阳网站设计多少钱,北京网站的优化在数据结构中图算是个较为难理解的结构形式了。
大致我们可以分为两个大类#xff1a; 1、通过数组实现 2、通过链表实现
而链表的实现方式还可以继续细分#xff1a;邻接表、邻接多重表、十字链表
所以关于图的结构的存储这里我们介绍四种基本形式#xff1a; 1、邻接矩…在数据结构中图算是个较为难理解的结构形式了。
大致我们可以分为两个大类 1、通过数组实现 2、通过链表实现
而链表的实现方式还可以继续细分邻接表、邻接多重表、十字链表
所以关于图的结构的存储这里我们介绍四种基本形式 1、邻接矩阵数组 2、邻接表链表 3、邻接多重表链表 4、十字链表链表
在C中图的存储方式通常有两种邻接矩阵和邻接表。 邻接矩阵 #include iostream
#include vectorusing namespace std;const int MAX_VERTICES 100;class Graph {
private:int vertices;vectorvectorint adjacencyMatrix;public:Graph(int V) : vertices(V), adjacencyMatrix(V, vectorint(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 listusing namespace std;class Graph {
private:int vertices;listint *adjacencyList;public:Graph(int V) : vertices(V), adjacencyList(new listint[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) {}};vectorEdgeNode* edgeList;public:Graph(int V) : edgeList(V, nullptr) {}void addEdge(int start, int end) {EdgeNode* edge new EdgeNode(start, end);// Update pointersedge-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) {}};vectorNode* 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 algorithmusing namespace std;class Graph {
private:mapchar, vectorchar adjacencyList;mapchar, bool visited;public:void addEdge(char u, char v) {adjacencyList[u].push_back(v);adjacencyList[v].push_back(u);}void DFS(char vertex, setchar component) {visited[vertex] true;component.insert(vertex);for (vectorchar::iterator it adjacencyList[vertex].begin(); it ! adjacencyList[vertex].end(); it) {char neighbor *it;if (!visited[neighbor]) {DFS(neighbor, component);}}}vectorsetchar getConnectedComponents() {vectorsetchar components;visited.clear();for (mapchar, vectorchar ::const_iterator it adjacencyList.begin(); it ! adjacencyList.end(); it) {char vertex it-first;if (!visited[vertex]) {setchar 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);}vectorsetchar components graph.getConnectedComponents();for (int i 0; i components.size(); i) {setchar component components[i];cout i 1 :;for (setchar::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 mapusing namespace std;// 计算指定顶点的度数
int calculateDegree(int vertex, const vectorvectorbool 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;// 构建顶点映射表mapchar, int vertexMap;vectorchar vertexList(vertices);for (int i 0; i vertices; i){cin vertexList[i];vertexMap[vertexList[i]] i;}// 构建邻接矩阵vectorvectorbool adjacencyMatrix(vertices, vectorbool(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;cinG.vexnumG.arcnum;for(int i0; iG.vexnum; i)cinG.vexs[i];for(int i0; iG.vexnum; i)for(int j0; jG.vexnum; j)G.arcs[i][j]0;for(int i1; iG.arcnum; i){cinuv;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 i0;iG.vexnum;i){coutG.vertices[i].data:;ArcNode *pG.vertices[i].firstarc;while(p){coutG.vertices[p-adjvex].data;pp-nextarc;}coutendl;}}
int main()
{MGraph G;ALGraph G1;createMGraph(G);createALGraph(G1,G);printAdjustVex(G1);
}
