Adjacency Matrix用C实现如下：
#include<stdio.h> #include<stdlib.h> #include<curses.h> typedef char VertexType; typedef int EdgeType; #define MAXVEX 100 #define INFINITY 11111 //#define DEBUG typedef struct { VertexType vexs[MAXVEX]; EdgeType arc[MAXVEX][MAXVEX]; int numVertexes, numEdges; //定义顶点数，边数 }Graph; //Locate the vertex you need int locates(Graph *g,char ch) { int i=0; for(i=0; i<g->numVertexes;i++){ if(g->vexs[i]==ch) break; } if(i>=g->numVertexes) //如果超过顶点数量了，返回-1 return -1; return i; //return the index of the vertex you are looking } //建立一个无方向网图的邻接矩阵表示 void CreateGraph(Graph *g) { int i,j,k,w; printf("Input the number of vertex and arc:\n"); scanf("%d %d", &(g->numVertexes), &(g->numEdges)); printf("#\n"); #ifdef DEBUG printf("The number is %d and %d.\n",g->numVertexes,g->numEdges); #endif printf("The total amount of vertexes is %d. Assign to each.\n",g->numVertexes); //assign a value to each vertex for(i=0;i<g->numVertexes;i++){ g->vexs[i]=getchar(); while(g->vexs[i] == '\n'){ g->vexs[i]=getchar(); } } #ifdef DEBUG for(i=0;i<g->numVertexes;i++){ printf("Vexs[i] is %c ",g->vexs[i]); } printf("\n"); #endif //initialize each arc/edge as infinity for(i=0;i<g->numEdges;i++){ for(j=0;j<g->numEdges;j++){ g->arc[i][j]=INFINITY; //initialize } } for (int i = 0; i < g->numEdges; ++i){ char p,q; printf("input the i and j of (Vi,Vj), and the weight:\n"); //一条边的两个结点，和这条边的权重 p=getchar(); while(p=='\n'){ p=getchar(); } q=getchar(); while(q=='\n'){ q=getchar(); } scanf("%d",&w); int m=-1; int n=-1; m=locates(g,p); n=locates(g,q); if(n==-1 || m==-1){ fprintf(stderr,"No such vertex\n"); return; } g->arc[m][n]=w; g->arc[n][m]=g->arc[m][n]; } } void printGraph(Graph 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] ); } printf("\n\n\n"); } } int main(int argc, char const *argv[]) { Graph g; CreateGraph(&g); printGraph(g); return 0; }Adjacency List的表示，用C实现
#include<stdio.h> #include<stdlib.h> #define DEBUG #define MAXVEX 1000 typedef char VertexType; typedef int EdgeType; 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; }GraphList; int Locate(GraphList *g,char ch) { int i; for(i=0;i<MAXVEX;i++){ if(ch==g->adjList[i].data){ break; } } if(i>MAXVEX){ fprintf(stderr,"there is no such vertex.\n"); return -1; } return i; } void CreateGraph(GraphList *g) { int i,j,k; EdgeNode *e; EdgeNode *f; printf("input the amount of matrixs and arcs:\n"); scanf("%d %d",&g->numVertexes,&g->numEdges); #ifdef DEBUG printf("numVertexes is %d. numEdges is %d.\n",g->numVertexes,g->numEdges); #endif for(i=0;i<g->numVertexes;i++){ printf("输入顶点%d:\n",i); g->adjList[i].data=getchar(); g->adjList[i].firstedge=NULL; while(g->adjList[i].data=='\n'){ g->adjList[i].data=getchar(); } } //build 边表 for(k=0;k<g->numEdges;k++){ printf("输入边(vi,vj)上的顶点序号:\n"); char p,q; p=getchar(); while(p=='\n'){ p=getchar(); } q=getchar(); while(q=='\n'){ q=getchar(); } int m,n; m=Locate(g,p); n=Locate(g,q); if(m==-1 || n==-1){ return; } #ifdef DEBUG printf("p=%c\n",p); printf("q=%c\n",q); printf("m=%d\n",m); printf("n=%d\n",n); #endif //申请内存空间生成边表结点 e=(EdgeNode *)malloc(sizeof(EdgeNode)); if(e==NULL){ fprintf(stderr,"malloc() error.\n"); return; } e->adjvex=n; e->next=g->adjList[m].firstedge; g->adjList[m].firstedge=e; f=(EdgeNode *)malloc(sizeof(EdgeNode)); if(f==NULL){ fprintf(stderr,"malloc() error.\n"); return; } f->adjvex=m; f->next=g->adjList[n].firstedge; g->adjList[n].firstedge=f; } } void printGraph(GraphList *g) { int i=0; #ifdef DEBUG printf("printGraph() starts.\n"); #endif while(g->adjList[i].firstedge!=NULL && i<MAXVEX){ printf("顶点%c与这些点连接：",g->adjList[i].data); EdgeNode *e=NULL; e=g->adjList[i].firstedge; while(e!=NULL){ printf("%d ",e->adjvex); //打印边表的节点 e=e->next; } i++; printf("\n"); } } int main() { GraphList g; CreateGraph(&g); printGraph(&g); return 0; }Minimum Cost Spanning Tree
1.Prim Algorithm
用C++实现，代码如下：
/* * prim.cpp * * Created on: May 3, 2017 * Author: yiyue */ #include<iostream> using namespace std; class prims { private: int no_of_edges,no_of_nodes;//number of edges and nodes int graph[10][10],visited[10],mindist[10]; //minimum distance public: void input(); void output(); void spanningtree(); prims()//constructor -- same name of class { no_of_edges=no_of_nodes=0; for(int i=0;i<10;i++){ visited[i]=mindist[i]=0; for(int j=0;j<10;j++){ graph[i][j]=0; } } } }; void prims::input() { int vertex1,vertex2,cost; cout<<"Enter no_of_nodes "; cin>>no_of_nodes; cout<<"Enter the no_of_edges "; cin>>no_of_edges; for(int i=0;i<no_of_edges;i++){ cout<<"Enter Vertex1 "; cin>>vertex1; cout<<"Enter vertex2 "; cin>>vertex2; cout<<"Enter the cost of "<<vertex1<< " and "<<vertex2<<" "; cin>>cost; graph[vertex1][vertex2]=graph[vertex2][vertex1]=cost; } } void prims::output() { for(int i=0;i<no_of_nodes;i++){ cout<<endl; for(int j=0;j<no_of_nodes;j++){ cout.width(4); cout<<graph[i][j]; } } } void prims::spanningtree(){ int min=9999,row,col,index=0; for(int i=0;i<no_of_nodes;i++){ for(int j=i;j<no_of_nodes;j++){ if(graph[i][j]<min&&graph[i][j]!=0){ min=graph[i][j]; row=i; //set it to vertex1 col=j; //vertex2 } } } visited[row]=visited[col]=1; mindist[index++]=min; for(int i=0;i<no_of_nodes-2;i++){ min=9999; for(int j=0;j<no_of_nodes;j++){ if(visited[j]==1){ for(int k=i;k<no_of_nodes;k++){ if(graph[j][k]<min&&graph[j][k]!=0&&visited[k]==0){//visited[k]==0 makes sure it's not self-loop min=graph[j][k]; row=j; //set it to vertex1 col=k; //vertex2 } } } } mindist[index++]=min; visited[row]=visited[col]=1; } int total=0; cout<<endl; cout<<"Minimum distance path is "; for(int i=0;i<no_of_nodes-1;i++){ cout<<" "<<mindist[i]<<" "; total=total+mindist[i]; } cout<<endl<<"Total path cost is "<<total; } int main() { prims obj; obj.input(); obj.output(); obj.spanningtree(); return 0; }另一种实现： （参见数据结构（严蔚敏））
#include <iostream> using namespace std; typedef char VerTexType; typedef int ArcType; #define MVNum 100 #define MaxInt 32767 //表示极大值，即∞ //辅助数组的定义，用来记录从顶点集U到V-U的权值最小的边 struct{ VerTexType adjvex; //最小边在U中的那个顶点 ArcType lowcost; //最小边上的权值 }closedge[MVNum]; //- - - - -图的邻接表存储表示- - - - - typedef char VerTexType; //假设顶点的数据类型为字符型 typedef int ArcType; //假设边的权值类型为整型 typedef struct{ VerTexType vexs[MVNum]; //顶点表 ArcType arcs[MVNum][MVNum]; //邻接矩阵 int vexnum,arcnum; //图的当前点数和边数 }AMGraph; int LocateVex(AMGraph G , VerTexType v){ //确定点v在G中的位置 for(int i = 0; i < G.vexnum; ++i) if(G.vexs[i] == v) return i; return -1; }//LocateVex void CreateUDN(AMGraph &G){ //采用邻接矩阵表示法，创建无向网G int i , j , k; cout <<"请输入总顶点数，总边数，以空格隔开:"; cin >> G.vexnum >> G.arcnum; //输入总顶点数，总边数 cout << endl; cout << "输入点的名称，如a" << endl; for(i = 0; i < G.vexnum; ++i){ cout << "请输入第" << (i+1) << "个点的名称:"; cin >> G.vexs[i]; //依次输入点的信息 } cout << endl; for(i = 0; i < G.vexnum; ++i) //初始化邻接矩阵，边的权值均置为极大值MaxInt for(j = 0; j < G.vexnum; ++j) G.arcs[i][j] = MaxInt; cout << "输入边依附的顶点及权值，如a b 5" << endl; for(k = 0; k < G.arcnum;++k){ //构造邻接矩阵 VerTexType v1 , v2; ArcType w; cout << "请输入第" << (k + 1) << "条边依附的顶点及权值:"; cin >> v1 >> v2 >> w; //输入一条边依附的顶点及权值 i = LocateVex(G, v1); j = LocateVex(G, v2); //确定v1和v2在G中的位置，即顶点数组的下标 G.arcs[i][j] = w; //边<v1, v2>的权值置为w G.arcs[j][i] = G.arcs[i][j]; //置<v1, v2>的对称边<v2, v1>的权值为w }//for }//CreateUDN int Min(AMGraph G){ //返回权值最小的点 int i; int index = -1; int min = MaxInt; for(i = 0 ; i < G.vexnum ; ++i){ if(min > closedge[i].lowcost && closedge[i].lowcost != 0){ min = closedge[i].lowcost; index = i; } }//for return index; }//Min void MiniSpanTree_Prim(AMGraph G, VerTexType u){ //无向网G以邻接矩阵形式存储，从顶点u出发构造G的最小生成树T，输出T的各条边 int k , j , i; VerTexType u0 , v0; k =LocateVex(G, u); //k为顶点u的下标 for(j = 0; j < G.vexnum; ++j){ //对V-U的每一个顶点vi，初始化closedge[i] if(j != k){ closedge[j].adjvex = u; closedge[j].lowcost = G.arcs[k][j]; //{adjvex, lowcost} }//if }//for closedge[k].lowcost = 0; //初始，U = {u} for(i = 1; i < G.vexnum; ++i){ //选择其余n-1个顶点，生成n-1条边(n= G.vexnum) k = Min(G); //求出T的下一个结点：第k个顶点，closedge[k]中存有当前最小边 u0 = closedge[k].adjvex; //u0为最小边的一个顶点，u0∈U v0 = G.vexs[k]; //v0为最小边的另一个顶点，v0∈V-U cout << "边 " <<u0 << "--->" << v0 << endl; //输出当前的最小边(u0, v0) closedge[k].lowcost = 0; //第k个顶点并入U集 for(j = 0; j < G.vexnum; ++j) if(G.arcs[k][j] < closedge[j].lowcost){ //新顶点并入U后重新选择最小边 closedge[j].adjvex = G.vexs[k]; closedge[j].lowcost = G.arcs[k][j]; }//if }//for }//MiniSpanTree_Prim int main(){ cout << "************算法6.8 普里姆算法**************" << endl << endl; AMGraph G; CreateUDN(G); cout << endl; cout << "无向图G创建完成！" << endl; cout <<endl; cout << "******利用普里姆算法构造最小生成树结果：******" << endl; MiniSpanTree_Prim(G , 'a'); cout <<endl; return 0; }//main