数据结构学习笔记—图---图的连通性、顶点间的路径

在无向图中，如果从顶点Vi到顶点Vj有路径，则称Vi和Vj连通。若图中任意两个两个顶点之间都连通——连通图。

极大连通子图——连通分量。（无向图）

从一个顶点开始作为一个子图，逐个添加和这个子图有边相连的顶点，直到所有相连的顶点都被纳入到图中所生成的子图就是一个极大连通子图。

完全图——任意两个顶点之间都有边或弧

对于无向图，有n个顶点，则有有n(n-1)/2条边；

对于有向图，有n个顶点，则有n(n-1)条边。

 

判定两个顶点Vi和Vj之间是否有路径

若是有有向图，对顶点Vi作深度优先搜索，即DFS(G,Vi)，若存在路径，则在搜索过程中必有visited[Vj]=1。若是无向图，对其中任意一顶点作DFS即可。

 

求解一个无向图的连通分量个数，并判定该无向图的连通性。

选择任意某一个顶点V，执行DFS(G,V)算法时，可以访问到V所在的连通分量中的所有顶点，所以遍历整个图而选择的初始出发点的个数即为图的连通分量的个数。

若连通分量的个数为1，表示图G是连通的，否则非连通。
图的基本数据结构：

#define MAX_VERTEX_NUM 20   //图中最大节点数目

#define INFINITY    10000

typedef struct ArcNode           //边表结点，即邻接链表的表结点
{
     int adjvex;                   //所指向下个结点的位置，对应数组中的下标
     struct ArcNode *nextarc;       //指向下一条弧的指针
     int weight;             //权重
}ArcNode;

typedef struct VNode          //顶点结构
{
     VertexType data;        //顶点数据类型
     ArcNode *firstarc;       //顶点相关弧链表的头结点
}VNode,AdjList[MAX_VERTEX_NUM];   //顶点结点

typedef struct
{
     AdjList vertices;    //图的顶点数组
     int vexnum,arcnum;  //图的顶点数和边数
}ALGraph;

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX_VERTEX_NUM 20
typedef  int VertexType;

typedef struct ArcNode
{
     int adjvex;
     struct ArcNode *nextarc;
     int weight;
}ArcNode;

typedef struct VNode
{
     VertexType data;
     ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct
{
     AdjList vertices;
     int vexnum,arcnum;
}ALGraph;

void CreateALGraph(ALGraph *G)
{
     ArcNode *p;
     int i,j,k;
     //printf("input vexnum : ");
     scanf("%d",&G->vexnum);
     //printf("input arcnum: ");
     scanf("%d",&G->arcnum);
     getchar();
     for(i=1;i<=G->vexnum;i++)
     {
          //printf("input %dth vex(char) : ");
          scanf("%c",&G->vertices[i].data);
          getchar();
          G->vertices[i].firstarc=NULL;
     }
     for(k=1;k<=G->arcnum;k++)
     {
          //printf("input %dth arc i(int) j(int)",k);
          scanf("%d%d",&i,&j);
          //在第i个链表上插入序号为j的表结点
          p=(ArcNode*)malloc(sizeof(ArcNode));
          p->adjvex=j;
          p->nextarc=G->vertices[i].firstarc;
          G->vertices[i].firstarc=p;
          //在第j个链表上插入序号为i的表结点
          p=(ArcNode*)malloc(sizeof(ArcNode));
          p->adjvex=i;
          p->nextarc=G->vertices[j].firstarc;
          G->vertices[j].firstarc=p;
     }
}
int visited[MAX_VERTEX_NUM];
void DFS(ALGraph G,int i)
{
     int j;
     ArcNode *p;
     visited[i]=1;
     printf("%3c",G.vertices[i].data);
     for(p=G.vertices[i].firstarc;p!=NULL;p=p->nextarc)
     {
          j=p->adjvex;
          if(visited[j]==0)
               DFS(G,j);
     }
}

void Is_connected(ALGraph G)
{
     int i;
     int count=0;
     for(i=1;i<=G.vexnum;i++)
          visited[i]=0;
     for(i=1;i<=G.vexnum;i++)
     {
          if(!visited[i])
          {
               printf(" ");
               DFS(G,i);
               count++;
          }
     }
     if(count==1)
          printf(" G is connected graph!");
     else
          printf(" G is not connected graph!");
     printf("%d ",count);
}

int main()
{
     ALGraph G;
     CreateALGraph(&G);
     Is_connected(G);
     return 0;
}

//测试数据
/*
13
13
A B C D E F G H I J K L M
1 2
1 3
1 6
1 12
2 13
4 5
7 8
7 9
7 11
8 11
10 12
10 13
12 13
*/

 

寻找连通图中给定的两个顶点i到j之间的所有简单路径

/*1.将Vi加入到当前路径path中
2.若当前路径path中的最后一个顶点为目标结点Vj，即存在从Vi到Vj的路径，输出该有向路径，否则，通过递归调用将Vi的一个未加入路径的邻接点w加入到当前路径中
3.将Vi从当前路径中删除

 

int visited[MAX_VERTEX_NUM];
int successful=0;
int top=0;
char path[MAX_VERTEX_NUM];
void pathdfs(ALGraph& G,int i,int j)
{
ArcNode *p;
int s,w;
visited[i]=1;  //将顶点i加入当前路径
path[++top]=G.vertices[i].data;
if(!successful && path[top]==G.vertices[j].data)
successful=1;   //存在顶点i到顶点j的路径
if(successful)   //找到
{
//输出当前路径上所有顶点
printf(" ");
for(s=1;s<=top;s++)
printf("%c ",path[s]);
successful=0;
}
else
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
w=p->adjvex;
if(!visited[w])
pathdfs(G,w,j);
}
visited[i]=0;    //每当顶点i回溯时，把visited[i]置为0，下次可通过顶点i寻找其他可能到达j的路径
top--;   //删除顶点i
}

 

int main()
{
ALGraph G;
CreateALGraph(&G);
pathdfs(G,1,13);
printf(" ");
return 0;
}