题目

一、实验目的

掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。

二、实验要求

采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。本实验给出了示例程序，其中共有4处错误，错误段均有标识，属于逻辑错误。请认真理解程序，修改程序代码，并在电脑上调试运行。

三、 DFS和BFS 的基本思想

深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。

广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，……，Vt；再依次访问与V1，V2，……，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。

四、示例程序

1.邻接矩阵作为存储结构的程序示例

#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定义最大顶点数
typedef struct{
char vexs[MaxVertexNum]; //顶点表
int edges[MaxVertexNum][MaxVertexNum];
//邻接矩阵，可看作边表
int n,e; //图中的顶点数n和边数e
}MGraph; //用邻接矩阵表示的图的类型
//========= 建立邻接矩阵 =======
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf(“Input VertexNum(n) and EdgesNum(e): “);
scanf(”%d,%d”,&G->n,&G->e); //输入顶点数和边数
scanf("%c",&a);
printf(“Input Vertex string:”);
for(i=0;in;i++)
{
scanf("%c",&a);
G->vexs[i]=a; //读入顶点信息，建立顶点表
}
for(i=0;in;i++)
for(j=0;jn;j++)
G->edges[i][j]=0; //初始化邻接矩阵
printf(“Input edges,Creat Adjacency Matrix\n”);
for(k=0;ke;k++) { //读入e条边，建立邻接矩阵
scanf("%d%d",&i,&j); //输入边（Vi，Vj）的顶点序号
G->edges[i][j]=1;
G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句
}
}
//========= 定义标志向量，为全局变量 ======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//======== DFS：深度优先遍历的递归算法======
void DFSM(MGraph *G,int i)
{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵
int j;
printf("%c",G->vexs[i]); //访问顶点Vi
visited[i]=TRUE; //置已访问标志
for(j=0;jn;j++) //依次搜索Vi的邻接点
if(G->edges[i][j]== 1 && ! visited[j])
DFSM(G,j); //（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点
}
void DFS(MGraph *G)
{ //此段代码有一处错误
int i;
for(i=0;in;i++)
visited[i]=FALSE; //标志向量初始化
for(i=0;in;i++)
if(!visited[i]) //Vi未访问过
DFS(G,i); //以Vi为源点开始DFS搜索
}
//======== BFS：广度优先遍历 ======
void BFS(MGraph *G,int k)
{ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索
int i,j,f=0,r=0;
int cq[MaxVertexNum]; //定义队列
for(i=0;in;i++)
visited[i]=FALSE; //标志向量初始化
for(i=0;i<=G->n;i++)
cq[i]=-1; //队列初始化
printf("%c",G->vexs[k]); //访问源点Vk
visited[k]=TRUE;
cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入队
while(cq[f]!=-1) { //队非空则执行
i=cq[f]; f=f+1; //Vf出队
for(j=0;jn;j++) //依次Vi的邻接点Vj
if(G-> edges[i][j] = =1 && !visited[j]) { //Vj未访问 以下三行代码有一处错误
printf("%c",G->vexs[j]); //访问Vj
visited[j] =FALSE; r=r+1; cq[r]=j; //访问过Vj入队
}
}
}
// ========= main =====
void main()
{
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //为图G申请内存空间
CreatMGraph(G); //建立邻接矩阵
printf(“Print Graph DFS: “);
DFS(G); //深度优先遍历
printf(”\n”);
printf(“Print Graph BFS: “);
BFS(G,3); //以序号为3的顶点开始广度优先遍历
printf(”\n”);}
执行顺序：
Input VertexNum(n) and EdgesNum(e): 8，9
Input Vertex string: 01234567
Input edges,Creat Adjacency Matrix
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5 6
Print Graph DFS: 01374256
Print Graph BFS: 31704256
2.邻接链表作为存储结构程序示例
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 50 //定义最大顶点数
typedef struct node{ //边表结点
int adjvex; //邻接点域
struct node *next; //链域
}EdgeNode;
typedef struct vnode{ //顶点表结点
char vertex; //顶点域
EdgeNode *firstedge; //边表头指针
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型
typedef struct {
AdjList adjlist; //邻接表
int n,e; //图中当前顶点数和边数
} ALGraph; //图类型
//建立图的邻接表
void CreatALGraph(ALGraph *G)
{
int i,j,k;
char a;
EdgeNode *s; //定义边表结点
printf(“Input VertexNum(n) and EdgesNum(e): “);
scanf(”%d,%d”,&G->n,&G->e); //读入顶点数和边数
scanf("%c",&a);
printf(“Input Vertex string:”);
for(i=0;in;i++) //建立顶点表
{
scanf("%c",&a);
G->adjlist[i].vertex=a; //读入顶点信息
G->adjlist[i].firstedge=NULL; //边表置为空表
}
printf(“Input edges,Creat Adjacency List\n”);
for(k=0;ke;k++) { //建立边表
scanf("%d%d",&i,&j); //读入边（Vi，Vj）的顶点对序号
s=(EdgeNode )malloc(sizeof(EdgeNode)); //生成边表结点
s->adjvex=j; //邻接点序号为j
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s; //将新结点S插入顶点Vi的边表头部
s=(EdgeNode )malloc(sizeof(EdgeNode));
s->adjvex=i; //邻接点序号为i
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s; //将新结点S插入顶点Vj的边表头部
}
}
//定义标志向量，为全局变量
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//DFS：深度优先遍历的递归算法======
void DFSM(ALGraph *G,int i)
{ //以Vi为出发点对邻接链表表示的图G进行DFS搜索
EdgeNode *p;
printf("%c",G->adjlist[i].vertex); //访问顶点Vi
visited[i]=TRUE; //标记Vi已访问
p=G->adjlist[i].firstedge; //取Vi边表的头指针
while§ { //依次搜索Vi的邻接点Vj，这里j=p->adjvex
//以下3行代码有一处错误
if(! visited[p->adjvex]) //若Vj尚未被访问
DFS(G,p->adjvex); //则以Vj为出发点向纵深搜索
p=p->next; //找Vi的下一个邻接点
}
}
void DFS(ALGraph *G)
{
int i;
for(i=0;in;i++)
visited[i]=FALSE; //标志向量初始化
for(i=0;in;i++)
if(!visited[i]) //Vi未访问过
DFSM(G,i); //以Vi为源点开始DFS搜索
}
//BFS：广度优先遍历
void BFS(ALGraph *G,int k)
{ //以Vk为源点对用邻接链表表示的图G进行广度优先搜索
int i,f=0,r=0;
EdgeNode *p;
int cq[MaxVertexNum]; //定义FIFO队列
for(i=0;in;i++)
visited[i]=FALSE; //标志向量初始化
for(i=0;i<=G->n;i++)
cq[i]=-1; //初始化标志向量
printf("%c",G->adjlist[k].vertex); //访问源点Vk
visited[k]=TRUE;
cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入队
while(cq[f]!=-1)
{ //队列非空则执行
i=cq[f]; f=f+1; //Vi出队
p=G->adjlist[i].firstedge; //取Vi的边表头指针
while§
{ //依次搜索Vi的邻接点Vj（令p->adjvex=j）
if(!visited[p->adjvex]) { //若Vj未访问过
printf("%c",G->adjlist[p->adjvex].vertex); //访问Vj
visited[p->adjvex]=TRUE;
//以下3行代码有一处错误
r=r+1; cq[r]=p->adjvex; //访问过的Vj入队
}
p=p->next->next; //找Vi的下一个邻接点
}
}//endwhile
}
//主函数
void main()
{
int i;
ALGraph *G;
G=(ALGraph *)malloc(sizeof(ALGraph));
CreatALGraph(G);
printf(“Print Graph DFS: “);
DFS(G);
printf(”\n”);
printf(“Print Graph BFS: “);
BFS(G,3);
printf(”\n”);
}
执行顺序：
Input VertexNum(n) and EdgesNum(e): 8，9
Input Vertex string: 01234567
Input edges,Creat Adjacency List
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5 6
Print Graph DFS: 02651473
Print Graph BFS: 37140265

五、实验任务

改正程序中的错误并调试通过，测试并完成实验报告的撰写。
选做题，编写程序输出该无向网络的最小生成树以及该最小生成树的所有边。

代码

邻接矩阵作为图的存储结构：

#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 100     //定义最大顶点数
typedef struct{
    char vexs[MaxVertexNum];        //顶点表
    int edges[MaxVertexNum][MaxVertexNum];
//邻接矩阵，可看作边表
    int n,e;          //图中的顶点数n和边数e
}MGraph;              //用邻接矩阵表示的图的类型
//=========建立邻接矩阵=======
void CreatMGraph(MGraph *G)
{
     int i,j,k;
     char a;
     printf("Input VertexNum(n) and EdgesNum(e): ");
     scanf("%d,%d",&G->n,&G->e);         //输入顶点数和边数
     scanf("%c",&a);
     printf("Input Vertex string:");
     for(i=0;i<G->n;i++)
     {
 scanf("%c",&a);
 G->vexs[i]=a;             //读入顶点信息，建立顶点表
     }
     for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
    G->edges[i][j]=0;    //初始化邻接矩阵
     printf("Input edges,Creat Adjacency Matrix\n");
     for(k=0;k<G->e;k++) {       //读入e条边，建立邻接矩阵
 scanf("%d%d",&i,&j);        //输入边（Vi，Vj）的顶点序号
 G->edges[i][j]=1;
 G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句
     }
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度优先遍历的递归算法======
void DFSM(MGraph *G,int i)
{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵
    int j;
    printf("%c",G->vexs[i]);     //访问顶点Vi
    visited[i]=TRUE;             //置已访问标志
    for(j=0;j<G->n;j++)          //依次搜索Vi的邻接点
if(G->edges[i][j]==1 && ! visited[j])
    DFSM(G,j);              //（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点
}
void DFS(MGraph *G)
{  //此段代码有一处错误
    int i;
    for(i=0;i<G->n;i++)
visited[i]=FALSE;            //标志向量初始化
    for(i=0;i<G->n;i++)
if(!visited[i])              //Vi未访问过
    DFSM(G,i);               //以Vi为源点开始DFS搜索
}
//===========BFS：广度优先遍历=======
void BFS(MGraph *G,int k)
{                //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索
    int i,j,f=0,r=0;
    int cq[MaxVertexNum];        //定义队列
    for(i=0;i<G->n;i++)
visited[i]=FALSE;         //标志向量初始化
    for(i=0;i<G->n;i++)
cq[i]=-1;                    //队列初始化
    printf("%c",G->vexs[k]);     //访问源点Vk
    visited[k]=TRUE;
    cq[r]=k;          //Vk已访问，将其入队。注意，实际上是将其序号入队
    while(cq[f]!=-1) {          //队非空则执行
     i=cq[f]; f=f+1;             //Vf出队
     for(j=0;j<G->n;j++)         //依次Vi的邻接点Vj
         if(G->edges[i][j]==1 && !visited[j]) {  //Vj未访问 \\以下三行代码有一处错误
         printf("%c",G->vexs[j]);         //访问Vj
         visited[j]=TRUE;          r=r+1; cq[r]=j;          //访问过Vj入队
         }
    }
}
//==========main=====
int main()
{
    MGraph *G;
    G=(MGraph *)malloc(sizeof(MGraph));   //为图G申请内存空间
    CreatMGraph(G);          //建立邻接矩阵
printf("Print Graph DFS: ");
DFS(G);                  //深度优先遍历
    printf("\n");
    printf("Print Graph BFS: ");
    BFS(G,3);             //以序号为3的顶点开始广度优先遍历
    printf("\n");
    return 0;
}

邻接链表作为图的存储结构：

#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 50          //定义最大顶点数
typedef struct node{       //边表结点
     int adjvex;           //邻接点域
     struct node *next;    //链域
}EdgeNode;
typedef struct vnode{      //顶点表结点
    char vertex;           //顶点域
    EdgeNode *firstedge;   //边表头指针
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];         //AdjList是邻接表类型
typedef struct {
    AdjList adjlist;       //邻接表
    int n,e;               //图中当前顶点数和边数
} ALGraph;                 //图类型
//=========建立图的邻接表=======
void CreatALGraph(ALGraph *G)
{
     int i,j,k;
     char a;
     EdgeNode *s;           //定义边表结点
     printf("Input VertexNum(n) and EdgesNum(e): ");
     scanf("%d,%d",&G->n,&G->e);       //读入顶点数和边数
     scanf("%c",&a);
     printf("Input Vertex string:");
     for(i=0;i<G->n;i++)         //建立边表
     {
  scanf("%c",&a);
  G->adjlist[i].vertex=a;       //读入顶点信息
  G->adjlist[i].firstedge=NULL;  //边表置为空表
     }
     printf("Input edges,Creat Adjacency List\n");
     for(k=0;k<G->e;k++) {        //建立边表
  scanf("%d%d",&i,&j);          //读入边（Vi，Vj）的顶点对序号
  s=(EdgeNode *)malloc(sizeof(EdgeNode));    //生成边表结点
  s->adjvex=j;                  //邻接点序号为j
  s->next=G->adjlist[i].firstedge;
  G->adjlist[i].firstedge=s;     //将新结点*S插入顶点Vi的边表头部
  s=(EdgeNode *)malloc(sizeof(EdgeNode));
  s->adjvex=i;                   //邻接点序号为i
  s->next=G->adjlist[j].firstedge;
  G->adjlist[j].firstedge=s;      //将新结点*S插入顶点Vj的边表头部
     }
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度优先遍历的递归算法======
void DFSM(ALGraph *G,int i)
{                         //以Vi为出发点对邻接链表表示的图G进行DFS搜索
    EdgeNode *p;
    printf("%c",G->adjlist[i].vertex);    //访问顶点Vi
    visited[i]=TRUE;                      //标记Vi已访问
    p=G->adjlist[i].firstedge;            //取Vi边表的头指针
while(p) {                  //依次搜索Vi的邻接点Vj，这里j=p->adjvex
//以下3行代码有一处错误
  if(! visited[p->adjvex])      //若Vj尚未被访问
        DFSM(G,p->adjvex);        //则以Vj为出发点向纵深搜索
  p=p->next;                    //找Vi的下一个邻接点
    }
}
void DFS(ALGraph *G)
{
    int i;
    for(i=0;i<G->n;i++)
  visited[i]=FALSE;             //标志向量初始化
    for(i=0;i<G->n;i++)
  if(!visited[i])               //Vi未访问过
      DFSM(G,i);                //以Vi为源点开始DFS搜索
}
//==========BFS：广度优先遍历=========
void BFS(ALGraph *G,int k)
{                          //以Vk为源点对用邻接链表表示的图G进行广度优先搜索
    int i,f=0,r=0;
    EdgeNode *p;
    int cq[MaxVertexNum];         //定义FIFO队列
    for(i=0;i<G->n;i++)
  visited[i]=FALSE;          //标志向量初始化
    for(i=0;i<=G->n;i++)
  cq[i]=-1;                          //初始化标志向量
    printf("%c",G->adjlist[k].vertex); //访问源点Vk
    visited[k]=TRUE;
    cq[r]=k;           //Vk已访问，将其入队。注意，实际上是将其序号入队
    while(cq[f]!=-1) {   //队列非空则执行
  i=cq[f]; f=f+1;                //Vi出队
  p=G->adjlist[i].firstedge;     //取Vi的边表头指针
  while(p) {                //依次搜索Vi的邻接点Vj（令p->adjvex=j）
      if(!visited[p->adjvex]) {           //若Vj未访问过
    printf("%c",G->adjlist[p->adjvex].vertex);      //访问Vj
    visited[p->adjvex]=TRUE;
//以下3行代码有一处错误
    r=r+1; cq[r]=p->adjvex;            //访问过的Vj入队
      }
      p=p->next;               //找Vi的下一个邻接点
  }
    }//endwhile
}
//==========主函数===========
int main()
{
    int i;
    ALGraph *G;
    G=(ALGraph *)malloc(sizeof(ALGraph));
    CreatALGraph(G);
    printf("Print Graph DFS: ");
    DFS(G);
    printf("\n");
    printf("Print Graph BFS: ");
    BFS(G,3);
    printf("\n");
    return 0;
}

选做题

#include "stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100
#define MaxEdgeNum 200
typedef struct{
    char vexs[MaxVertexNum];
    int edges[MaxVertexNum][MaxVertexNum];
    int n,e;
}MGraph;
typedef struct edge
{
    char p1;
    char p2;
    int weight;
}Edge;
typedef struct edges
{
    int num;
    Edge edge[MaxEdgeNum];
}Edges;
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//=========建立邻接矩阵=======
void CreatMGraph(MGraph *G)
{
     int i,j,k,l;
     char a;
     printf("Input VertexNum(n) and EdgesNum(e): ");
     scanf("%d,%d",&G->n,&G->e);         //输入顶点数和边数
     scanf("%c",&a);
     printf("Input Vertex string:");
     for(i=0;i<G->n;i++)
     {
         scanf("%c",&a);
         G->vexs[i]=a;             //读入顶点信息，建立顶点表
     }
     for(i=0;i<G->n;i++)
        for(j=0;j<G->n;j++)
            G->edges[i][j]=0;    //初始化邻接矩阵
    printf("Input edges,Creat Adjacency Matrix\n");
    for(k=0;k<G->e;k++)
    {       //读入e条边，建立邻接矩阵
         scanf("%d,%d,%d",&i,&j,&l);        //输入边（Vi，Vj）的顶点序号
         G->edges[i][j]=l;
         G->edges[j][i]=l; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句
    }
}
int is_existed(char *arr,char c)
{
    int i;
    for(i=0;i<MaxEdgeNum;i++)
    {
        if(arr[i]=='#')
            return 0;
        if(arr[i]==c)
            return 1;
    }
    return 0;
}
int Init_Edge(Edge **edge)
{
    *edge=(Edge*)malloc(sizeof(Edge));
    (*edge)->p1='#';
    (*edge)->p2='#';
    (*edge)->weight=0;
    return 1;
}
int Edges_Init(Edges **edges)
{
    *edges=(Edges*)malloc(sizeof(Edges));
    (*edges)->num=0;
}
int Edges_Read(MGraph *G,Edges* E)
{
    int i,j;
    for(i=0;i<G->n;i++)
    {
        for(j=0;j<=i;j++)
        {
            if(G->edges[i][j]!=0)
            {
                E->edge[E->num].p1=G->vexs[i];
                E->edge[E->num].p2=G->vexs[j];
                E->edge[E->num].weight=G->edges[i][j];
                E->num++;
            }
        }
    }
    return 1;
}
int Edges_Delete(Edges* E,char a1,char a2)
{
    int i;
    int pos=-1;
    for(i=0;i<E->num;i++)
    {
        if((E->edge[i].p1==a1&&E->edge[i].p2==a2)||(E->edge[i].p1==a2&&E->edge[i].p2==a1))
        {
            pos=i;
            break;
        }
    }
    if(pos==-1)
        return 1;
    for(i=pos;i<E->num;i++)
    {
        E->edge[i]=E->edge[i+1];
    }
    E->num--;
    return 1;
}
int Edges_Sort(Edges* E)
{
    int i,j,pos,min;
    Edge temp;
    for(i=0;i<E->num-1;i++)
    {
        pos=i;
        min=E->edge[i].weight;
        for(j=i+1;j<E->num;j++)
        {
            if(E->edge[j].weight<min)
            {
                pos=j;
                min=E->edge[j].weight;
            }
        }
        temp=E->edge[i];
        E->edge[i]=E->edge[pos];
        E->edge[pos]=temp;
    }
    return 1;
}
int find_char(char M[MaxVertexNum][MaxVertexNum],char c)
{
    int i,j;
    for(i=0;i<MaxVertexNum;i++)
    {
        for(j=0;j<MaxVertexNum;j++)
        {
            if(M[i][j]=='#')
                break;
            if(M[i][j]==c)
                return i;
        }
    }
    return -1;
}
int delete_char(char *M,char c)
{
    int i;
    int pos=-1;
    for(i=0;i<MaxVertexNum;i++)
    {
        if(M[i]=='#')
            break;
        if(M[i]==c)
            pos=i;
    }
    if(pos==-1)
        return 1;
    for(i=pos;i<MaxVertexNum;i++)
    {
        if(M[i+1]!='#')
        {
            M[i]=M[i+1];
        }
        else
        {
            M[i]='#';
            break;
        }
    }
    return 1;
}
int Kruskal(MGraph *G,Edges *E_result)
{
    int i,j,is_p1,is_p2,flag,line1,line2,p,q,l;
    char connected[MaxVertexNum][MaxVertexNum];
    for(i=0;i<MaxVertexNum;i++)
    {
        for(j=0;j<MaxVertexNum;j++)
        {
            connected[i][j]='#';
        }
    }
    Edges *E;
    Edges_Init(&E);
    Edges_Read(G,E);
    Edges_Sort(E);
    int edge_count=0;
    while(edge_count<G->n-1)
    {
        i=0;
        while(i<G->n)
        {
            flag=0;
            for(j=0;j<G->n;j++)
            {
                is_p1=is_existed(connected[i],E->edge[0].p1);
                is_p2=is_existed(connected[i],E->edge[0].p2);
                if(is_p1==1&&is_p2==1)
                {
                    Edges_Delete(E,E->edge[0].p1,E->edge[0].p2);
                    flag=-1;
                    break;
                }
                if((is_p1==1&&is_p2==0)||(is_p1==0&&is_p2==1))
                {
                    if(is_p2==0)
                    {
                        for(q=0;q<G->n;q++)
                        {
                            if(is_existed(connected[q],E->edge[0].p2)==1)
                            {
                                flag=2;
                                break;
                            }
                        }
                        if(flag!=2)
                            flag=1;
                        break;
                    }
                    if(is_p1==0)
                    {
                        for(q=0;q<G->n;q++)
                        {
                            if(is_existed(connected[q],E->edge[0].p1)==1)
                            {
                                flag=3;
                                break;
                            }
                        }
                        if(flag!=3)
                            flag=4;
                        break;
                    }
                }
            }
            if(flag!=0)
                break;
            i++;
        }
        if(flag==-1)
        {
            continue;
        }
        else if(flag==2||flag==3)
        {
            line1=find_char(connected,E->edge[0].p1);
            line2=find_char(connected,E->edge[0].p2);
            l=get_length(connected[line2]);
            for(p=0;p<l;p++)
            {
                connected[line1][get_length(connected[line1])]=connected[line2][p];
                connected[line2][p]='#';
            }
            E_result->edge[E_result->num]=E->edge[0];
            E_result->num++;
            Edges_Delete(E,E->edge[0].p1,E->edge[0].p2);
            edge_count++;
            continue;
        }
        else if(flag==1)
        {
            line1=find_char(connected,E->edge[0].p1);
            connected[line1][get_length(connected[line1])]=E->edge[0].p2;
            E_result->edge[E_result->num]=E->edge[0];
            E_result->num++;
            Edges_Delete(E,E->edge[0].p1,E->edge[0].p2);
            edge_count++;
            continue;
        }
        else if(flag==4)
        {
            line2=find_char(connected,E->edge[0].p2);
            connected[line2][get_length(connected[line2])]=E->edge[0].p1;
            E_result->edge[E_result->num]=E->edge[0];
            E_result->num++;
            Edges_Delete(E,E->edge[0].p1,E->edge[0].p2);
            edge_count++;
            continue;
        }
        else if(flag==0)
        {
            for(p=0;p<MaxVertexNum;p++)
            {
                if(get_length(connected[p])==0)
                {
                    connected[p][0]=E->edge[0].p1;
                    connected[p][1]=E->edge[0].p2;
                    break;
                }
            }
            E_result->edge[E_result->num]=E->edge[0];
            E_result->num++;
            Edges_Delete(E,E->edge[0].p1,E->edge[0].p2);
            edge_count++;
            continue;
        }
    }
    printf("\nedges in minimum created tree is:\n");
    for(i=0;i<E_result->num;i++)
    {
        printf("%c,%c,%d\n",E_result->edge[i].p1,E_result->edge[i].p2,E_result->edge[i].weight);
    }
    return 1;
}
int get_length(char *arr)
{
    int i=0;
    for(i=0;i<MaxVertexNum;i++)
    {
        if(arr[i]=='#')
            return i;
    }
    return 0;
}
void init_Arr(char *arr)
{
    int i;
    for(i=0;i<MaxVertexNum;i++)
    {
        arr[i]='#';
    }
}
//==========main=====
void main()
{
    MGraph *G;
    G=(MGraph *)malloc(sizeof(MGraph));   //为图G申请内存空间
    CreatMGraph(G);          //建立邻接矩阵
    printf("\n");
    Edges *E_result;
    Edges_Init(&E_result);
    Kruskal(G,E_result);
}

数据结构实验课：实验六、图的遍历操作及应用

题目

一、实验目的

二、实验要求

三、 DFS和BFS 的基本思想

四、示例程序

五、实验任务

代码

邻接矩阵作为图的存储结构：

邻接链表作为图的存储结构：

选做题

热门文章

最新文章

相关课程

相关电子书

相关实验场景

数据结构实验课：实验六、图的遍历操作及应用

题目

一、实验目的

二、 实验要求

三、 DFS和BFS 的基本思想

四、示例程序

五、 实验任务

代码

邻接矩阵作为图的存储结构：

邻接链表作为图的存储结构：

选做题

热门文章

最新文章

相关课程

相关电子书

相关实验场景

二、实验要求

五、实验任务