数据结构试验4-图实验报告及源码

数据结构图的实验报告，内含源码。需要的放心下载！

#include
#define MAX_VERTEX_NUM 20   //最多顶点个数 为 20个
#define XX 99  //表示极大值，即∞
typedef struct ArcNode{
	//定义邻接矩阵中的节点
	int adj;    //存储权值，若无权值则为∞
}ArcNode;
typedef struct{
	//定义邻接矩阵
	char vertex[MAX_VERTEX_NUM];   //一位数组存放顶点
	ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  //二维数组表示顶点之间的关系
	int vexnum;  //顶点数
	int arcnum;  //弧数
}AdjMatrix;
void CreateGraph（AdjMatrix* m）;
void PrintGraph（AdjMatrix* m）;
void dfs_graph（AdjMatrix * graph bool visited[] const int i）;
void g_depth_first_search（AdjMatrix * graph）;
void init_prim（AdjMatrix * graph AdjMatrix * prim_tree）;
void Prim（AdjMatrix * graph AdjMatrix * prim_tree）;
bool Connectivity_Warshall（AdjMatrix* m）;
int main（）
{
	AdjMatrix M;
	AdjMatrix prim_tree;

	CreateGraph（&M）;

	PrintGraph（&M）;

	g_depth_first_search（&M）;

	Prim（&M &prim_tree）;

	if（Connectivity_Warshall（&M））
		printf（“是连通树\n“）;
	else
		printf（“不是连通树\n“）;
	return 0;
}
void CreateGraph（AdjMatrix* m）
{
	//创建连通图
	int iixjy;

	printf（“请输入图的顶点个数：\n“）;
	scanf（“%d“&m->vexnum）;
	printf（“请输入图的顶点：\n“）;
	getchar（）;
	for（i = 0; i < m->vexnum; i++）
	{
		m->vertex[i] = getchar（）;	
	}
	printf（“请输入图的顶点关系：\n“）;
	for（ix = 0; ix < m->vexnum; ix++）{
		for（jy = 0; jy < m->vexnum; jy++）{
			scanf（“%d“&m->arcs[ix][jy].adj）;
			if（getchar（） == ‘ ‘）
		     	continue;
	    	else
			    break;
		}
	}
}
//输出图的邻接矩阵
void PrintGraph（AdjMatrix* m）
{
	int ixjy;
	printf（“图的（邻接矩阵）遍历结果：\n“）;
	for（ix = 0; ix < m->vexnum; ix++）{
		printf（“%c   “m->vertex[ix]）;
		for（jy = 0; jy < m->vexnum; jy++）{
			printf（“%-5d“m->arcs[ix][jy].adj）;
		}
		printf（“\n“）;
	}
}
void g_depth_first_search（AdjMatrix * graph）
{
    bool visited[MAX_VERTEX_NUM];
    int i;
	printf（“深度遍历结果如下：“）;
    for （ i = 0; i < graph->vexnum; i++ ）
        visited[i] = false;
    visited[0] = true;
    dfs_graph（graph visited 0）;
    printf（“\n“）;
}
void dfs_graph（AdjMatrix * graph bool visited[] const int i）
{
    int j;
    printf（“%c\t“ graph->vertex[i]）;
    for （ j = 0; j < graph->vexnum; j++ ）//依次检查矩阵
    {
        if （ graph->arcs[i][j].adj != XX && !visited[j] ）//i 代表矩阵的行 j 代表矩阵的列
        {
            visited[j] = true;
            dfs_graph（graph visited j）;
        }
    }
}

//判断是否为连通树
bool Connectivity_Warshall（AdjMatrix* m）
{
 AdjMatrix judgemat;
 judgemat.vexnum=m->vexnum;
 int ij;
 for（i=1;i<=m->vexnum;i++）
 {
  for（j=1;j<=m->vexnum;j++）
  {
   if（m->arcs[i][j].adj）
    judgemat.arcs[i][j].adj=1; //初始化判断矩阵
   else
    judgemat.arcs[i][j].adj=0;
  }
  judgemat.arcs[i][j].adj=1;
 }

 for（int x=1;x<=judgemat.vexnum;x++） //采用warshall算法判断图的连通性。注意下标。
 {
  for（int y=1;y<=judgemat.vexnum;y++）
  {
   if（judgemat.arcs[x][y].adj）
   {
    for（int z=1;z<=judgemat.vexnum;z++）
    {
     if（judgemat.arcs[z][x].adj）
      judgemat.arcs[z][y].adj=1;
    }
   }
  }
  //print（judgemat）;
 }
 for（i=1;i<=judgemat.vexnum;i++）
 {
  for（j=1;j<=judgemat.vexn

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      16883  2018-12-14 09:54  数据结构试验4\第四次实验.docx

     文件        528  2018-12-20 22:38  数据结构试验4\带权连通图.dsw

     文件      48640  2018-12-20 22:38  数据结构试验4\带权连通图.opt

     文件     142003  2019-03-08 12:28  数据结构试验4\图.docx

     文件      41984  2018-12-20 21:39  数据结构试验4\Debug\vc60.idb

     文件      53248  2018-12-20 21:14  数据结构试验4\Debug\vc60.pdb

     文件     451584  2018-12-20 21:14  数据结构试验4\Debug\带权连通图.pdb

     文件     203700  2018-12-15 10:38  数据结构试验4\Debug\带权连通图.pch

     文件     206840  2018-12-20 21:14  数据结构试验4\Debug\带权连通图.ilk

     文件     184387  2018-12-20 21:14  数据结构试验4\Debug\带权连通图.exe

     文件      11545  2018-12-20 21:14  数据结构试验4\Debug\带权连通图.obj

     文件       1285  2018-12-20 21:14  数据结构试验4\带权连通图.plg

     文件      33792  2018-12-20 17:47  数据结构试验4\带权连通图.ncb

     文件       4756  2018-12-20 21:14  数据结构试验4\带权连通图.cpp

     文件       3451  2018-12-20 22:38  数据结构试验4\带权连通图.dsp

     目录          0  2018-12-14 10:32  数据结构试验4\Debug

     目录          0  2018-12-14 09:54  数据结构试验4

----------- ---------  ---------- -----  ----

              1404626                    17