c++实现图的表示,数据结构之图(一)
2021/7/9 20:36:29
本文主要是介绍c++实现图的表示,数据结构之图(一),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
数据结构之图(一)
1. 邻接矩阵
将图表示为一个矩阵。
输入:
5 6 #顶点数和边数 A B C D E #顶点信息 0 4 6 #边的下标(0,4)-->6和权值 1 0 9 1 2 3 2 0 2 2 3 5 3 4 1
- 代码实现:创建邻接矩阵并打印。
#include <iostream> using namespace std; #define MAXVEX 100 #define INF_M 65535 typedef char VertexType; //顶点类型 typedef int EdgeType; //边上权值 typedef struct{ VertexType vexs[MAXVEX]; EdgeType arc[MAXVEX][MAXVEX]; int numVertexes,numEdges; }MGraph; void CreateGraph(MGraph *G){ int i,j,k,w; cout<<"请输入顶点数和边数:"<<endl; //scanf("%d,%d",&G->numVertexes,&G->numEdges); cin>>G->numVertexes>>G->numEdges; for(i = 0; i < G->numVertexes; i++){ //scanf("%d",&G->vexs[i]); cin>>G->vexs[i]; } for(i = 0; i < G->numVertexes; i++){ for(i = 0; i < G->numVertexes; i++){ G->arc[i][j] = 0; } } for(k = 0; k < G->numEdges; k++){ //printf("请输入边的下标和权重:\n"); cout<<"请输入边的下标和权重:"<<endl; //scanf("%d %d %d",&i,&j,&w); cin>>i>>j>>w; G->arc[i][j] = w; G->arc[j][i] = G->arc[i][j];//无向图是一个对称的。 } } void printGraph(MGraph *G){ int i,j; for(i = 0; i < G->numVertexes; i++){ for(j = 0; j < G->numVertexes; j++){ //printf("%d\t", G->arc[i][j]); cout<<G->arc[i][j]<<"\t"; } cout<<endl; } } int main() { MGraph *G = new MGraph; CreateGraph(G); printGraph(G); return 0; }
2. 邻接表
用邻接表来表示图数据
- 代码实现:创建邻接表并打印。
//边表节点 typedef struct EdgeNode{ int adjvex; EdgeType weight; struct EdgeNode *next; }EdgeNode; //顶点表节点 typedef struct VertexNode{ VertexType data; EdgeNode *firstedge; //边表类型的指针 }VertexNode,AdjList[MAXVEX]; //邻接表 typedef struct{ AdjList adjList; int numVertexes,numEdges; }GraphAdjList; //结构体指针变量用->,普通结构体变量用.; void CreateGraphA(GraphAdjList *G){ int i,j,k,w; EdgeNode *e; //生成一个边表类型的指针 cout<<"请输入顶点数和边数:\n"; cin>>G->numVertexes>>G->numEdges; for(i = 0; i < G->numVertexes; i++){ cin>>G->adjList[i].data; G->adjList[i].firstedge = NULL; } for(k = 0;k < G->numEdges; k++){ cout<<"请输入边的顶点信息:\n"; cin>>i>>j>>w; //头插法插入边表结点。 e = (EdgeNode*)malloc(sizeof(EdgeNode));//申请内存空间,生成内存结点。 e->adjvex = j; e->next = G->adjList[i].firstedge; e->weight = w; G->adjList[i].firstedge = e; e = (EdgeNode*)malloc(sizeof(EdgeNode)); e->adjvex = i; e->next = G->adjList[j].firstedge; e->weight = w; G->adjList[j].firstedge = e; } } void printGraphA(GraphAdjList *G){ int i,j; EdgeNode *GA; for(i = 0; i < G->numVertexes; i++){ GA = G->adjList[i].firstedge; cout<<G->adjList[i].data<<":"; while(GA != NULL){ cout<<GA->adjvex<<" "<<GA->weight<<";"; GA = GA->next; } cout<<endl; } } int main() { GraphAdjList *G = new GraphAdjList; CreateGraphA(G); printGraphA(G); return 0; }
这篇关于c++实现图的表示,数据结构之图(一)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置