数据结构课程设计，有向图，C语言高手进

Question

对任意给定的有向图（顶点数不小于20，边数不少于30），能够输入图的顶点和边的信息，并存储到邻接矩阵存储结构，对自己所创建的图完成以下操作：
1输出图的深度优先遍历序列
2求图的深度优先生成树（存储结构为孩子-兄弟链表），并对生成树进行遍历
3判断图中是否存在环
4求顶点u到v的所有简单路径
5求顶点u到v的最短路径
用c语言写，可以的话发到我的邮箱[email protected],能运行出来追加分数，谢谢！！

Answer 1

已编译确认：

/* 图的深度优先遍历 */
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

struct node /* 图顶点结构定义 */
{
int vertex; /* 顶点数据信息 */
struct node *nextnode; /* 指下一顶点的指标 */
};

typedef struct node *graph; /* 图形的结构新型态 */
struct node head[9]; /* 图形顶点数组 更改为实际大小*/
int visited[9]; /* 遍历标记数组 更改为实际数组大小*/
/********************根据已有的信息建立邻接表********************/
void creategraph(int node[20][2],int num)/*num指的是图的边数*/
{
graph newnode; /*指向新节点的指针定义*/
graph ptr;
int from; /* 边的起点 */
int to; /* 边的终点 */
int i;
for ( i = 0; i < num; i++ ) /* 读取边线信息，插入邻接表*/
{
from = node[i][0]; /* 边线的起点 */
to = node[i][1]; /* 边线的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 建立顶点内容 */
newnode->nextnode = NULL; /* 设定指标初值 */
ptr = &(head[from]); /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode; /* 下一个顶点 */
ptr->nextnode = newnode; /* 插入节点 */
}
}
/********************** 图的深度优先搜寻法********************/
void dfs(int current)
{
graph ptr;
visited[current] = 1; /* 记录已遍历过 */
printf("vertex[%d]\n",current); /* 输出遍历顶点值 */
ptr = head[current].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过 */
dfs(ptr->vertex); /* 递回遍历呼叫 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
}
/****************************** 主程序******************************/
int main()
{
graph ptr; /* 边线数组 */
int node[20][2] = { {1, 2}, {2, 1}, /*换成自己的顶点数值，下面for循环中 i 的取值范围相应更改*/
{1, 3}, {3, 1},
{1, 4}, {4, 1},
{2, 5}, {5, 2},
{2, 6}, {6, 2},
{3, 7}, {7, 3},
{4, 7}, {4, 4},
{5, 8}, {8, 5},
{6, 7}, {7, 6},
{7, 8}, {8, 7} };
int i;
system("cls");
for ( i = 1; i <= 8; i++ ) /* 顶点数组初始化 */
{
head[i].vertex = i; /* 设定顶点值 */
head[i].nextnode = NULL; /* 指针为空 */
visited[i] = 0; /* 设定遍历初始标志 */
}
creategraph(node,20); /* 建立邻接表 */
printf("Content of the gragh's ADlist is:\n");
for ( i = 1; i <= 8; i++ )
{
printf("vertex%d ->",head[i].vertex); /* 顶点值 */
ptr = head[i].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex); /* 印出顶点内容 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
printf("\n"); /* 换行 */
}
printf("\nThe end of the dfs are:\n");
dfs(1); /* 打印输出遍历过程 */
printf("\n"); /* 换行 */
puts(" Press any key to quit...");
getch();
return 0;
}

Answer 2

写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=0;i<n;i++)
printf("%3d",i);
printf("\n");
for(i=0;i<n;i++)
{
printf("%4d",i);
for(j=0;j<n;j++)
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=0;i<n;i++){
c[i]=0;
for
(j=0;j<n;j++){
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=0;j<n;j++){
d[j]=0;
for
(i=0;i<n;i++){
if
(G.e[i][j]!=0)
d[j]=d[j]+1;
}
printf("顶点
%d
的入度为:
%d
\n",j,d[j]);
//有向图的任意顶点j的入度为邻接矩阵中第j列不为0的数的个数
}
for
(l=0;l<n;l++){
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=0;i<n;i++){
for
(j=0;j<n;j++)
G.e[i][j]=0;
}
for
(i=0;i<n;i++)
G.v[i]=0;
for
(i=0;i<n;i++){
for
(j=0;j<n;j++){
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);
}