一：最小生成树（prim算法）

由于prim算法需要频繁的取一条边的权值，采用邻接矩阵存储更加合适。

代码：

void Prim(MatGraph g,int v0,int &sum){int *lowcost=(int*)malloc(sizeof(int)*g.n);//当前树到剩余顶点的最短边 int *vset=(int*)malloc(sizeof(int)*g.n);//当前树的顶点 int v;//工作顶点指针int i,j,k,min;v=v0;//从v0开始执行该算法for(i=0;i<g.n;i++){lowcost[i]=g.edges[v0][i];//初始化lowcost,开始时树中只有v0顶点vset[i]=0;//所有顶点开始都不在树中 } vset[v0]=1;//顶点v0加入到树中sum=0;//用与计算树的权值for(i=0;i<g.n;i++){min=INF;for(j=0;j<g.n;j++){//找出当前树到树外最短的边 if(vset[j]==0&&lowcost[j]<min){min=lowcost[j];k=j;//记录最短边的另一个顶点 }}vest[k]=1;//顶点k加入到树中sum += min;//更新树的权值；v=k;//更新lowcost，判断顶点的加入是否会有更小的值for(j=0;j<g.n;j++){if(vset[j]==0&&g.edges[v][j]<low[j]){lowcost[j]=g.edges[v][j];}} } free(vset);free(lowcost);
}

 时间复杂度O（n^2）

二：最小生成树（Kruskal）算法。

由于Kruskal算法需要频繁的取一条边的权值，采用邻接矩阵存储更加合适。

代码：

typedef struct{int u;//边的起始顶点int v;//边的终止顶点int w;//边的权值 
}Edg;
void Kruskal(MatGraph g){int i,j,u1,v1,sn1,sn2,k;int vset[MAX];Edg E[MAX];//存放图中所有的边k=0;for(i=o;i<g.n;i++){//右邻接矩阵把边集找出来 for(j=0;j<g.n;j++){if(g.edges[i][j]!=0&&g.edges[i][j]!=INF){E[k].u=i;E[k].v=j;E[k].w=g.edges[i][j];k++}}} InsertSort(E,g.e);//采用直接插入排序法对E数组按照权值递增排序for(i=0;i<g.n;i++){vest[i]=i;//初始化辅助数组 } k=1;//表示当前构造的生成树是第几条边，初始为1 j=0;//数组E的下标，初始为0 while(k<g.n){//生成树的边数小于n时，循环u1=E[j].u;v1=E[j].v;//取一条边的两个顶点sn1=vest[u1];sn2=vest[u2];//分别得到两个顶点集合 if(sn1!=sn2) {//两个顶点属于不同集合，该边是最小生成树的一条边 printf("(%d,%d):%d\n",u1,v1,E[j].w);//输出最小生成树的最小一条边 k++;//生成树的边数+1 for(i=0;i<g.n;i++){//两个集合统一编号if(vset[i])==sn2){ //集合编号sn2改为sn1 vset[i]=sn1;}} }j++;//遍历下一条边 }
}

时间复杂度O（eloge） 

三：最短路径Dijkstra算法求单源最短路径问题。

代码：

//set[]：记录已经求得最短路径的顶点
//dist[]：记录从源点v0到其他各顶点当前的最短路径
//path[]：path[i]表示从源点到顶点i之间的最短路径前驱
void dijkstra(MatGraph g,int v,int dist[],int path[]){//已经求得最短路径的顶点被设置成1 int *set=(int*)malloc(sizeof(int)*g.n);//初始化for(int i=0;i<g.n;i++){dis[i]=g.edges[v][i];//初始时直接读取顶点v的边信息//已求得最短路径结点set[i]=0;if(g.edges[v][i]<INF){path[i]=v;//顶点i的直接前驱就是v } else{path[i]=-1;} }set[v]=1;//源点path[v]=-1;for(int i=0;i<g.n;i++){//选取当前最短路径int min=INF;int u=-1;for(int j=0;i<g.n;j++){//只针对还未求得最短路径的顶点if(set[j]==0&&dist[j]<min){u=j;min=dis[j];} } //从v到u的最短路径已经找到了set[u]=1;//用上一步选取的路径去更新最短路径for(int j=0;j<g.n;j++){if(set[j]==0&&dis[u]+g.edges[u][j]<dist[j]){dis[j]=dis[u]+g.edges[u][j];path[j]=u;}}}free(set); 
} //打印路径,从源点到顶点a的最短路径 
void printPath(int path[],int a){//初始化栈int stack[MAX];int top=-1;while(path[a]!=-1){stack[++top]=a;a=path[a];//去到路径的上一个结点 } stack[++top]=a;//单独处理最后一个结点//正序打印路径while(top!=-1){printf("%d ", stack[top--]);} printf("\n");
} 

时间复杂度：求源点到其他顶点O(n^2)；求每一对不同顶点之间的最短路径时间复杂度O（n^3）；

四：最短路径Floyd算法求多源最短路径问题。

代码：

void floyd(MatGraph g,int path[Max][Max],int dist[Max][Max]){//初始化 for(int i=0;i<g.n;i++){for(int j=0;j<g.n;j++){dis[i][j]=g.edges[i][j];path[i][j]=-1; }}//以顶点k为中间点，完成对所有定点对i,j的更新for(int k=0;k<g.n;k++){for(int i=0;i<g.n;i++){for(int j=0;j<g.n;j++){if(dist[i][j]>dis[i][k]+dis[k][j]){dist[i][j]=dis[i][k]+dis[k][j];path[i][j]=k;}}}} 
}
//输出u到v的最短路径上的顶点序列 
void printpath(int u,int v,int path[Max][Max],int dist[Max][Max]){//u,v不可到达，不输出if(dist[u][v]==INF){return;}if(path[u][v]=-1){printf("（%d,%d）、", u, v);}else{int mind = path[u][v];printpath(u,mid,path,dist);//前半段 printpath(min,c=v,path,dist);//后半段 }
}

时间复杂度O（n^3）

五：拓扑排序。利用邻接矩阵存储。

代码：

//求每个顶点的入度 
int *getIndgree(MatGraph g){int *indegree=(int*)malloc(sizeof(int)*g.n);for(int i=0;i<g.n;i++){//初始化 indegree[i]=0;}//遍历邻接矩阵for(int i=0;i<g.n;i++){for(int j=0;j<g.n;j++){if(g.edges[i][j]!=0){indegree[j]++;//j的入度增加 }}} return indegree; 
} //拓扑排序
bool topSort(MatGraph g){int *indegree=getIndegree(g);//找到一个入度为0的点int stack[MAX];int top=-1;int m=0;//完成拓扑排序的个数 //初始化入度为0的顶点入栈for(int i=0;i<g.n;i++){if(indegree[i]==0){stack[++top]=i;}} while(top!=-1){m++;//完成拓扑排序的个数 //出栈int v=stack[top--];printf("%d,", v);//由该顶点的边到达顶点的入度都减少1。for(int i=0;i<g.n;i++){if(g.edges[v][i]==1){indegree[i]--;if(indegree[i]==0){//入栈stack[++top]; }}}  }free(indegree);return m==g.n;//m= g.n拓扑排序成功，没有环。 m<g.n拓扑排序失败，有环。
} 

时间复杂度O（n^2）

六：拓扑排序。利用邻接表存储。

代码：

int topSort(AdjGraph *G){SqStack *st;InitStack(st);int indegree[MAX];//定义一个入度数组for(int i=0;i<G->n;i++) indegree[i]=0;//初始化入度数组for(int i=0;i<G->n;i++){//求所有顶点入度 ArcNode *p=G->adjlist.firstarc;while(p!=NULL){int w=p->adjvex;indegree[w]++;p=p->nextarc;}} for(int i=0;i<G->n;i++){if(indegree[i]==0){push(st,i);}} int i,n=0;while(!StackEmpth(st)){pop(st,i);//栈不为空时，入栈 n++; printf("%d",i);//输出该顶点 ArcNode *p=G->adjlist[i].firstarc;//寻找第一个邻接点 while(p!=NULL){int w=p->adjvex;indegree[w]--;//入度减1 if(indegree[w]==0){//将入度为0的顶点入栈 push(st,w);}p=p->nextarc;//找下一个邻接点 }}return n=G->n ? 1:0; 
}

时间复杂度O（v+e）