用C语言编写以下算法： 一个5个节点的有向图，有向线段上有权重即T[i][j]，它表示节点i对节点j的信任度。

写C程序，随机给出n*n的邻接矩阵，并打印输出邻接矩阵，以及有向图的边的个数，每个顶点的度，并判断该图中是否存在Euler回路： （1）如果为n阶，则随机产生一个n*n的邻接矩阵； （2）输出邻接矩阵，边的个数，每个顶点的度以及图中是否存在Euler回路。 这个题目涉及到了两个主要的知识点，一个是数据结构中的有向图的邻接矩阵的创建，还有就是离散数学中的Euler回路的判定定理。

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#include<math.h>

#define n 5 //定义矩阵的阶数n

typedef int ver

typedef int edg//定义有向图的顶点和边值为整形

typedef struct{

ver v[n] //顶点

edg e[n][n]//边权

}graph //定义邻接矩阵的数据结构

void printgraph (graph G)//打印输出邻接矩阵

{

int i,j

printf("顶点")

for(i=0i<ni++)

printf("%3d",i)

printf("\n")

for(i=0i<ni++)

{

printf("%4d",i)

for(j=0j<nj++)

printf("%3d",G.e[i][j])

printf("\n")

}

}

void countD (graph G) //判断有向图的顶点的度，并判断Euler回路

{

int i,j,l

int e=0,count=0

int k //计数器赋0

int c[n],d[n]

for (i=0i<ni++){

c[i]=0

for (j=0j<nj++){

if (G.e[i][j]!=0)

c[i]=c[i]+1

}

printf("顶点 %d 的出度为: %d \n",i,c[i]) //有向图的任意顶点i的出度为邻接矩阵中第i行不为0的数的个数

}

printf("\n")

for (j=0j<nj++){

d[j]=0

for (i=0i<ni++){

if (G.e[i][j]!=0)

d[j]=d[j]+1

}

printf("顶点 %d 的入度为: %d \n",j,d[j])//有向图的任意顶点j的入度为邻接矩阵中第j列不为0的数的个数

}

for (l=0l<nl++){

if (c[l]==d[l])

count++

else {

if (c[l]-d[l]==1)

e++

else{

if (d[l]-c[l]==1)

e++

}

}

}

k=0

if (count==n) //判断Euler回路： 1：所有顶点的出度等于入度；

//2：有且仅有两个点度数为奇数，且一个出度比入度大一

k=1 //另一个入度比出度大一，其他的顶点出度等于入度

else {

if (e==2 &&count==n-2)

k=1

}

if (k==1)

printf("有向图中存在Euler回路\n")

else

printf("有向图中不存在Euler回路\n")

}

void main() //主函数

{

int i,j,temp

graph G

srand(time (NULL)) //随机种子

for (i=0i<ni++){

for (j=0j<nj++)

G.e[i][j]=0

}

for (i=0i<ni++)

G.v[i]=0

for (i=0i<ni++){

for (j=0j<nj++){

do

{

temp = rand()%n //随机建造邻接矩阵

if (G.v[i]<n)

{

G.e[i][j] = temp

G.v[i]++

break

}

}

while (1)

}

}

printf("生成的有向图邻接矩阵为: \n")

printgraph(G)

countD (G) //调用子函数

printf("有向图的边数为：%d\n",n*(n-1)/2)

}

另外,团IDC网上有许多产品团购,便宜有口碑

用CPM算法求有向图的关键路径和用Dijkstra算法求有向图的最短路径的C语言程序如下

#include <stdio.h>

#include <malloc.h>

#include <stdlib.h>

#include <string.h>

#define MAX 20

#define INF 32767      // 此处修改最大值

#define nLENGTH(a)  (sizeof(a)/sizeof(a[0]))

#define eLENGTH(a) (sizeof(a)/sizeof(char))/(sizeof(a[0])/sizeof(char))

typedef struct _graph{

char vexs[MAX]       // 顶点集合

int vexnum           // 顶点数

int edgnum           // 边数

int matrix[MAX][MAX]// 邻接矩阵

}Graph, *PGraph

// 边的结构体

typedef struct _EdgeData{

char start// 边的起点

char end   // 边的终点

int weight// 边的权重

}EData

//指向节点的位置

int point_node(PGraph g,char c){

for(int i=0i<g->vexnumi++){

if(g->vexs[i]==c){

return i

}

}

return -1

}

PGraph create_graph(int b[][3],char a[],int n,int e){

char c1,c2//边的2个顶点

PGraph g//矩阵

g=(PGraph)malloc(sizeof(Graph))

//memset()第一个参数 是地址，第二个参数是开辟空间的初始值，第三个参数是开辟空间的大小

memset(g, 0, sizeof(Graph))

printf("顶点个数:\n")//顶点数

g->vexnum=n

printf("%d\n",g->vexnum)

printf("边个数:\n")//边数

g->edgnum=e

printf("%d\n",g->edgnum)

//初始化顶点

for(int j=0j<g->vexnumj++){

g->vexs[j]=a[j]

}

for(int i=0i<g->edgnumi++){

int p1,p2

c1=char(b[i][0])

c2=char(b[i][1])

p1=point_node(g, c1)

p2=point_node(g, c2)

if (p1==-1 || p2==-1){

printf("input error: invalid edge!\n")

free(g)

continue

}

g->matrix[p1][p2]=b[i][2]

}

for(int i=0i<g->vexnumi++){

for(int j=0j<g->vexnumj++){

if(g->matrix[i][j]==0)

  g->matrix[i][j]=INF

}

}

return g

}

//关键路径的最短时间

//关键路径法（Critical Path Method，CPM）

void CPM_road(PGraph g){

int i,j

int a[MAX]={0},b[MAX]={-10}

int max=0//最长路径

for( i=0i<g->vexnumi++){//列数遍历

for( j=0j<g->vexnumj++){//行数遍历

//如果g->matrix[j][i]大于0，说明此顶点有前顶点，由前边的遍历可知，前顶点的最长路径a[j]，

//加上g->matrix[j][i]的路径就是当前a[i]的路径

if(g->matrix[j][i]!=INF &&g->matrix[j][i]+a[j]>max){

  max=g->matrix[j][i]+a[j]

  a[i]=max

}

}

max=0

}

//显示最长路径

printf("第一个顶点到每一个顶点的最长路径:")

printf("\n")

for(i=0i<g->vexnumi++){

printf("V%d\t",i+1)

}

printf("\n")

for(i=0i<g->vexnumi++){

printf("%d\t",a[i])

}

printf("\n")

printf("最后一个顶点到每个顶点的最长路径:")

for( i=g->vexnum-1i>=0i--){ //列数遍历

for( j=g->vexnum-1j>=0j--){ //行数遍历

//如果g->matrix[j][i]大于0，说明此顶点有前顶点，由前边的遍历可知，前顶点的最长路径a[j]，

//加上g->matrix[j][i]的路径就是当前a[i]的路径

if(g->matrix[i][j]!=INF &&g->matrix[i][j]+b[j]>max){

  max=g->matrix[i][j]+b[j]

  b[i]=max

}

}

max=0

}

//显示最长路径

printf("\n")

for(i=0i<g->vexnumi++){

printf("V%d\t",i+1)

}

printf("\n")

for(i=0i<g->vexnumi++){

printf("%d\t",b[i])

}

printf("\n")

printf("关键路径:\n")

for(i=0i<g->vexnumi++){

if(a[i]==a[g->vexnum-1]-b[i]){

printf("V%c\t",g->vexs[i])

}

}

printf("\n")

}

void print_shortest_path(PGraph g,int* distance,int* path,int* used,int start,int end){

// 输出最短距离并打印最短路径

int i = 0, pre, inverse_path[g->vexnum]

char s1[3],s2[3]

sprintf(s1, "V%d", (start+1))

sprintf(s2, "V%d", (end+1))

printf("从%s顶点到%s顶点的最短距离: %d\n", s1,  s2, distance[end])

inverse_path[i] = end

pre = path[end]

if(pre == -1){

printf("没有通路!\n")

}else{

while(pre != start){

inverse_path[++i] = pre

pre = path[pre]

}

inverse_path[++i] = start

printf("从%s顶点到%s顶点的最短路径:\n", s1, s2)

for(i >0i--){

sprintf(s1, "V%d", (inverse_path[i]+1))

printf("%s ->", s1)

}

sprintf(s1, "V%d", (inverse_path[i]+1))

printf("%s\n", s1)

}

return

}

void shortest_path(PGraph g,int start, int end){ // 基于Dijkstra算法的最短路径函数

int distance[g->vexnum]// 用于存放起始点到其余各点的最短距离

int path[g->vexnum]// 用于存放起始点到其余各点最短路径的前一个顶点

int used[g->vexnum] = { 0 }// 用于标记该顶点是否已经找到最短路径

int i, j, min_node, min_dis, pass_flag = 0

for(i = 0i <g->vexnumi++){

distance[i] = g->matrix[start][i]// 初始化距离数组

if(g->matrix[start][i] <INF){

path[i] = start// 初始化路径数组

}else{

path[i] = -1

}

}

used[start] = 1

path[start] = start

for(i = 0i <g->vexnumi++){

min_dis = INF

for(j = 0j <g->vexnumj++){

if(used[j] == 0 &&distance[j] <min_dis){

  min_node = j

  min_dis = distance[j]

  pass_flag++// 标记是否存在通路

}

}

if(pass_flag != 0){

used[min_node] = 1

for(j = 0j <g->vexnumj++){

  if(used[j] == 0){

   if(g->matrix[min_node][j] <INF &&distance[min_node] + g->matrix[min_node][j] <distance[j]){

    distance[j] = distance[min_node] + g->matrix[min_node][j]

    path[j] = min_node

   }

  }

}

}

}

print_shortest_path(g,distance, path, used, start, end)

return

}

int main(){

int i,j

PGraph gp

char a[]={'1', '2', '3', '4', '5', '6', '7'}

int b[][3]={{'1', '2',3},

{'1', '3',2},

{'1', '4',6},

{'2', '4',2},

{'2', '5',4},

{'3', '4',1},

{'3', '6',3},

{'4', '5',1},

{'5', '7',3},

{'6', '7',4}}

int n=nLENGTH(a)

int e=eLENGTH(b)

gp=create_graph(b,a,n,e)

//打印邻接矩阵

printf("邻接矩阵:\n")

for (i = 0i <gp->vexnumi++){

for (j = 0j <gp->vexnumj++)

printf("%d  ", gp->matrix[j][i])

printf("\n")

}

CPM_road(gp)

printf("\n")

for(i=0i<gp->vexnumi++){

for(j=0j<gp->vexnumj++){

if(i!=j)

  shortest_path(gp,i, j)

}

}

return 0

}

运行结果

---