将图表示为一个矩阵。
输入:
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; }
用邻接表来表示图数据
//边表节点 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; }