数据结构进阶实训十三 图的应用

数据结构进阶实训课程笔记和算法练习

Source Code

C语言中文网

---

---

题目1

判断给定的图G是否是连通图。若连通，则输出该生成树。若不连通，则输出其所有的连通子图（生成森林）
  - 图G分别采用邻接矩阵或邻接表存储表示
  - 实现在该两种存储表示方法下的上述操作

1.1 算法设计思想

深度优先搜索算法的改进。

如果一次深度优先搜索没有把所有顶点遍历完，即visited数组有false值，那么就可以证明图不是连通的。

1.2 源代码

// 邻接矩阵
void Judge(MGraph G, bool *b){
  printf("The spanning tree or forest of this graph is: ");
  int v;
  //将用做标记的visit数组初始化为false
  for( v = 0; v < G.vexnum; ++v){
    visited[v] = false;
  }
  DFS( G, 0);    //从任意一点遍历，这里从下标为0的点开始
  for( v = 1; v < G.vexnum; v++){
    if(!visited[v]){
      DFS( G, v);
      *b = false;
      printf(" | ");
    }
  }
  *b = true;
}

//邻接表
void JudgeAdjList(ALGraph *g, bool *b){
  printf("The spanning tree or forest of this graph is: ");
  int i;
  int visited[MAX_VERtEX_NUM];
  for(i=0;i<g->vexnum;i++){
    visited[i]=0;
  }
  DFSAdjList(g, 0, visited);
  for(i=1;i<g->vexnum;i++){
    if(!visited[i]){
      printf(" | ");
      DFSAdjList(g, i, visited);
      *b = false;
    }
  }
  *b = true;
}

1.3 运行情况截图

---

---

题目2

无向图G（不带权值）采用邻接表结构，试设计一个算法，求图G中从顶点u到顶点v的最短路径。

2.1 算法设计思想

运用Dijkstra(迪杰斯特拉)算法的思想。

visit[]：这个数组用来标记结点的访问与否，如果该结点被访问，则为1，如果该结点还没有访问，则为0；

distance[]：这个数组用来记录当前从v到各个顶点的最短路径长度，算法的核心思想就是通过不断修改这个表实现。

先遍历直达源顶点的所有顶点，距离记为1，置visit[]已访问；

后面遍历所有其他未访问的顶点，更新distance[]数组。

    实例
     1
   /   \
  0     2
 / \   
3   4
程序将以此图作为输入

2.2 源代码

void Dijkstra(ALGraph G, int s, int t){//求 s 到 t 的最短路径
  int i, j;
  int visit[MAX_VERTEX_NUM];
  int distance[MAX_VERTEX_NUM];        //从 s 到各点的距离
  
  for(i=0; i<G.vexnum; i++){
    distance[i]=INFINITY;
    visit[i]=false;
  }
  distance[s]=0;
  visit[s]=1;
  ArcNode *p=G.vertices[s].firstarc;
  
  while(p){   //先把距离源点距离最近的顶点都遍历完
    if(!visit[p->adjvex]){
      distance[p->adjvex]=1;
      visit[p->adjvex]=1;        //当前顶点已访问
    }
    p=p->nextarc;
  }

  for(i=0; i<G.vexnum; i++){      //再求其他顶点
    if(!visit[G.vertices[i].data]){
      p=G.vertices[i].firstarc;   //未访问的节点
      while(p){
        if(distance[p->adjvex]<INFINITY){
          distance[G.vertices[i].data]=distance[p->adjvex]+1;
        }
        p=p->nextarc;
      }
    }
  }
}

2.3 运行情况截图

---

---

题目3

无向图G（不带权值）采用邻接表表示，试设计一个算法，输出从顶点Vi到顶点Vj的所有简单路径。

3.1 算法设计思想

利用递归算法，从起始点出发，分别递归遍历它的所有顶点，将遍历过的顶点访问数组置false，并将节点记录进path数组，当遇到目标加点将path数组中顶点全部输出，即为简单路径。

    实例
     0
   /   \
  1     2
   \   /
     3
程序将以此图作为输入

3.2 源代码

int path[MAX_VERTEX_NUM];
path[0]=start;     //记录源点

void findAllSimplePath(ALGraph G, int start, int end, int path[], int i){
  ArcNode *p;
  int j, n;
  visited[start]=1;  // 记录已近访问过这个顶点
  p=G.vertices[start].firstarc;
  while (p){
    n=p->adjvex;
    if(n==end){   //找到一个路径
      path[i+1] = end;
      for(j=0; j<=i+1; j++)
        printf("%-3d", path[j]);
      printf("\n");
    }
    else if(!visited[n]){   //改点未被遍历
      path[i+1]=n;//存入路径
      findAllSimplePath(G, n, end, path, i+1); // 递归
    }
    p=p->nextarc;
  }
}

3.3 运行情况截图

---

---

题目4

图G采用邻接表表示，试设计一个算法，求无向连通图G中距离顶点v最远的一个顶点。

4.1 算法设计思想

同题目2的算法思想，既然用Dijkstra算法求出了所有一个点到其他所有顶点的路径，那么取distance数组中的最大值即为最远顶点。

4.2 源代码

int Dijkstra(ALGraph G, int s){
  int i, j;
  int visit[MAX_VERTEX_NUM];
  int distance[MAX_VERTEX_NUM];        //从 s 到各点的距离
  
  for(i=0; i<G.vexnum; i++){
    distance[i]=INFINITY;
    visit[i]=false;
  }
  distance[s]=0;
  visit[s]=1;
  ArcNode *p=G.vertices[s].firstarc;
  
  while(p){   //先把距离源点距离最近的顶点都遍历完
    if(!visit[p->adjvex]){
      distance[p->adjvex]=1;
      visit[p->adjvex]=1;        //当前顶点已访问
    }
    p=p->nextarc;
  }

  for(i=0; i<G.vexnum; i++){      //再求其他顶点
    if(!visit[G.vertices[i].data]){
      p=G.vertices[i].firstarc;   //未访问的节点
      while(p){
        if(distance[p->adjvex]<INFINITY){
          distance[G.vertices[i].data]=distance[p->adjvex]+1;
        }
        p=p->nextarc;
      }
    }
  }

  int max=0;    //最远顶点的位置
  for(i=1; i<G.vexnum; i++){
    if(distance[max]<distance[i])
      max=i;
  }
  return max;
}

4.3 运行情况截图

---