数据结构--图的基本使用:深度优先搜索和广度优先搜索

0 人赞了该文章

图,由结点的有穷集合V和边的集合E组成。

有向图和无向图,一个有方向,一个没有方向。

弧,在有向图中,将边称为弧,含有箭头的一端称为弧头,另一端称为弧尾,记为<vi,vj>。

度,在无向图中,边表示为(vi,vj),与顶点V相关的边的条数称为顶点的度。在有向图中,指向该顶点是称为入度,指出,称为出度。

有向完全图,如果具有n个结点,同时具有n(n-1)条边时,称为该图为有向完全图。

无向完全图,如果具有N个结点,同时具有n(n-1)/2个结点时,称为无向完全图。

路径与路径长度,路径为相邻顶点序偶所构成的序列。路径长度是指路径上边的数目。

简单路径,序列中顶点不重复出现的路径。

无向图连通,在无向图中,如果中顶点v1到顶点v2有路径,则称v1,v2之间连通。

连通图,在无向图中,如果任意两个顶点之间都是连通的,则称该无向图为连通图。

连通分量,在无向图中如果不是任意两个顶点之间都能够连通,那么称图中的极大连通子图为连通分量。

有向图连通,在有向图中,如果从顶点v1到顶点v2是有路径可达的,则称两者为连通。

强连通图,如果对于每一对顶点,两者互相都有路径可达,则称图为强连通图。

强连通分量,极大强连通子图,称为强连通分量。

权,给边附上值。


图的基本表示方式主要是邻接矩阵和邻接表两种。

邻接矩阵:

typedef struct
{
   int no;
   char  info;
}VertexType;

typedef struct 
{
  int edges[maxSize][maxSize];
  int n,e;
  VertexType vex[maxSize];
}MGraph;

邻接表:

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

typedef struct
{
  char data;
  ArcNode *firstarc
}VNode;

typedef struct
{
  VNode adjlist[maxSize];
  int n,e;
}AGragh;

深度优先搜索算法:

int visit[maxSize];

void DFS(AGraph *G,int v)
{
  ArcNode  *p;
  visit[v] = 1;
  //对已经进行过访问的结点进行处理
  p = G->adjlist[v].firstarc;
  while(p!=null)
  {
     if(visit[p->adjvex]==0)
      {
         DFS(G,p->adjvex);
      }
      p = p->nextarc;
  } 
}

把图的深度优先搜索遍历过程中所经历的边保留,其余的彼岸进行删除,生成的树,称为深度优先树。

广度优先搜索遍历

void  BFS(AGraph *G,int v , int visit[maxSize])
{
  ArcNode *p;
  int que[maxSize],front = 0,rear = 0;
  int j;
  //进行访问操作
  visit[v] = 1;
rear = (rear+1)%maxSize;
que[rear] = v;
while(front!=rear)
{
  front = (front+1)%maxSize;
j = que[front];
 p=G->adjlist[j].firstarc;
while(p!=null)
{
  if(visit[p->adjvex]==0)
  {
    visit[p->adjvex]=1;
    rear = (rear+1)%maxSize;
    que[rear]=p->adjvex;
   }
    p=p->nextarc;
}
}
}

评论

暂无评论