图

前言

简单对比一下线性表、树 、图：

从上图可以看出图结构是很复杂的，研究图结构的一个专门理论工具便是图论。

图的基本概念

图结构：

• 顶点（Vertex）：图中的数据元素。
• 边（Edge）：图中连接这些顶点的线。
  一个完整的图结构由顶点集合和边集合组成。
  G = (V，E)
  其中，V表示图中所有顶点的集合，必须为非空。E表示图中所有边的集合，可以为空，此时表示没有边。

  有向图与无向图

  有向图：在图结构中，边有方向性，这种图便称为有向图。*在表示边时，与顶点的顺序有关。***
  无向图：在图结构中，边没有方向性，这种图便称为无向图。*在表示边时，与顶点的顺序无关。***

  子图

  假设有两个图G = (V，E)和G’ = (V’，E’)，如果V’∈V 且 E’∈E，则称G’为G的子图。

注意：只有顶点集合是子集，或者只有边集合是子集的，都不是子图。

无向完全图与有向完全图

无向完全图：如果在一个无向图中，每两个顶点之间都存在一条边（即n(n-1)/2条），这种图结构称为无向完全图。
有向完全图：如果在一个有向图中，每两个顶点之间都存在方向相反的两条边（即**n(n-1)**条），这种图结构称为有向完全图。

权和网

在实际应用中，每条边可以标上带有具体含义的数值，该数值称为该边上的权。
这种带权的图就叫网。

邻接顶点

两个点确定一条边，这两点就是邻接顶点。
有向图稍微复杂一点，两个顶点分为起始顶点和结束顶点（因为有方向）。

返回目录

顶点的度

连接顶点的边的数量称为顶点的度。
有向图稍微复杂一点，根据方向性可分为入度和出度。
入度：箭头指向自己的边的数量。ID(V)。
出度：箭头往外指的边的数量。OD(V)。
D(V)=ID(V)+OD(V)
一般地，所有顶点的度的和加起来除以2等于图的边数：
$$ e=\sum_{i=0}^n D(Vi) $$

路径和路径长度

路径指图结构中两个顶点之间要走的边，路径上边的数量称为路径长度。

如图所示，从V5 到 V2 其中一条路径为（V5，V4）、（V4，V2），路径长度为2。

回路或环

第一个顶点和最后一个顶点相同的路径称为回路或环。

简单路径与简单回路

简单路径：在图结构中，如果一条路径上的顶点不重复出现，则称为简单路径。
简单回路：在图结构中，如果除了第一个顶点和最后一个顶点相同，其余各顶点都不重复的回路称为简单回路。

连通、连通图和连通分量—-无向图

连通：如果图结构中两个顶点之间有路径，则这两个顶点是连通的。
**注意：连通的两个顶点未必是邻接顶点，只要有路径走得通即可。**

连通图：如果无向图中 任意 两个顶点都是连通的，那么这个图便称为连通图。
该图的连通分量。
对于一个连通图，其连通分量有且只有一个，那就是该连通图自身。

强连通图和强连通分量—-有向图

强连通图：任意两个顶点Vi，Vj，从Vi 到 Vj 和从Vj 到 Vi 都存在路径，那么这个图便称为强连通图。
强连通分量：有向图的极大强连通子图称为该图的强连通分量。
对于一个强连通图，其强连通分量有且只有一个，那就是该强连通图自身。

返回目录

• 图的存储结构

  • 邻接矩阵

    采用二维数组的形式保存顶点之间的关系。该数组称为邻接矩阵。
    除了一个用于存储邻接矩阵的二维数组外，还需要用一个一维数组来存储顶点信息。
    无权值：
    

  有权值：
  
  对于无向图，其邻接矩阵左下角和右上角是对称的。

  • 邻接表

    对图中每个顶点Vi建立一个单链表，把与Vi的邻接点放在这个链中。Vi存在头结点中，其余结点存放邻接点边的信息。
    这样邻接表便由两部分组成：**表头结点表和边表。**
    表头结点表：由所有头结点顺序存储，以便可以随机访问任意顶点的边表。结点包括两个域，数据域，存放顶点名。指针域，指向第一个结点（第一个邻接点）。
    边表：结点包括三个域。邻接点域，存放该邻接点在图中的位置。数据域，存放权值。指针域，指向下一邻接点。

                       ![在这里插入图片描述](https://img-blog.csdnimg.cn/20190710155806527.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Nvbmdzb25nTA==,size_16,color_FFFFFF,t_70 =300x300)
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/20190710155821686.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Nvbmdzb25nTA==,size_16,color_FFFFFF,t_70 =600x300)

  • 邻接矩阵与邻接表的比较

    返回目录

  图的操作

• 采用邻接矩阵表示法

  由上面图的基本概念可知，创建图与网的区别就是增加一个权值。
  创建有向无向的区别就是无向可以默认生成 对称信息，有向 来与回 不同步。

  • 初始化

    typedef struct MNode{
    	vertexType vertex[MVNum];	//存储顶点 
    	arcType Arc[MVNum][MVNum];	//邻接矩阵，存储边 
    	int vexnum,arcnum;
       	GraphKind kind;				//图的种类，有向无向等 
    }GraphNode,*Graph;

  • 创建无向图

    void CreateUDG(Graph G)			//创建无向图 
    {
    	int num=0,					//控制输入顶点数 
    		pos1,pos2,				//确认顶点位置 
    		i,j;
    	char a,
    		 b,
    		 ch;					//顶点 
        for(i = 0;i<MVNum;i++){ 	//初始化弧
            for(j = 0;j<MVNum;j++){
                G->Arc[i][j] = 0;
            }
        }
        G->kind = UDG; 				//图的类型为无向图 
    
        printf("请输入顶点(不超过10个，以#结束):\n");
        cin>>ch;
        while(ch!='#' && num <10){
            G->vertex[num] = ch;
            cin>>ch;
            num++;
        }
        G->vexnum = num;  			//顶点个数
    
        cout<<"请输入对应的弧（ab与ba是一样的边），以##结束"<<endl;
        cin>>a>>b;
        while(a!='#' && b!='#'){
            cout<<a<<"-"<<b<<endl;
            FindPos(G,a,b,pos1,pos2);
            printf("位置a:%d,位置b:%d\n",pos1,pos2);
            if(pos1!= -1 && pos2!= -1){  //忽略不存在的顶点
                G->Arc[pos1][pos2] = 1;
                G->Arc[pos2][pos1] = 1;
                G->arcnum++;
            }
            cin>>a>>b;
        }
    }

  • 创建无向网

    void CreateUDN(Graph G)			//创建无向网
    {
    	int num=0,					//控制输入顶点数 
    		pos1,pos2,				//确认顶点位置 
    		i,j,
    		weight;					//权值 
    	char a,
    		 b,
    		 ch;					//顶点 
    		 
    	for(i = 0;i<MVNum; i++){ //初始化弧
            for(j = 0;j<MVNum; j++){
                G->Arc[i][j] = MAXINT;
            }
        }
        G->kind = UDN; //设置图的类型
    
        printf("请输入顶点(不超过10个，以#结束):\n");
        cin>>ch;
        while(ch!='#' && num <10){
            G->vertex[num] = ch;
            scanf("%c",&ch);
            num++;
        }
        G->vexnum = num;  //顶点个数
    
        cout<<"请输入对应的弧（ab与ba是一样的边）和权值，以###结束"<<endl;
        cin>>a>>b>>weight;
        while(a!='#' && b!='#'){
            cout<<a<<"-"<<b<<":"<<weight<<endl;
            FindPos(G,a,b,pos1,pos2);
            printf("位置a:%d,位置b:%d\n",pos1,pos2);
            if(pos1!= -1 && pos2!= -1){ 		 //忽略不存在的顶点
                G->Arc[pos1][pos2] = weight;
                G->Arc[pos2][pos1] = weight;
                G->arcnum++;
            }
            cin>>a>>b>>weight;
        }
    }

  • 创建有向图

    void CreateDG(Graph G)			//创建有向图 
    {
    	int num=0,					//控制输入顶点数 
    		pos1,pos2,				//确认顶点位置 
    		i,j;
    	char a,
    		 b,
    		 ch;					//顶点 
    	for(int i=0;i<MVNum;i++){				//初始化 
    		for(int j=0;j<MVNum;j++){
    			G->Arc[i][j]=0;
    		}
    	}
    	G->kind=DG;								//类型为有向图 
    	cout<<"请输入顶点，以#结束"<<endl;
    	cin>>ch;
    	while(ch!='#'&&num<10){
    		G->vertex[num]=ch;
    		cin>>ch;
    		num++;
    	} 
    	G->vexnum=num;
    	
    	cout<<"请输入对应的弧（ab与ba是方向相反的边），以##结束"<<endl;
    	cin>>a>>b;
    	while(a!='#'&&b!='#'){
    		cout<<a<<"->"<<b<<endl;
    		FindPos(G,a,b,pos1,pos2);
    		cout<<"位置a："<<pos1<<"位置b："<<pos2<<endl;
    		if(pos1!=-1&&pos2!=-1){
    			G->Arc[pos1][pos2]=1;
    			G->arcnum++;
    		}
    		cin>>a>>b;			
    	}
    }

  • 创建有向网

    void CreateDN(Graph G)			//创建有向网 
    {
    	int num=0,					//控制输入顶点数 
    		pos1,pos2,				//确认顶点位置 
    		i,j,
    		weight;					//权值 
    	char a,
    		 b,
    		 ch;					//顶点 
        for(i = 0;i < MVNum; i++){ 	//初始化弧
            for(j = 0;j<MVNum; j++){
                G->Arc[i][j] = MAXINT;
            }
        }
        G->kind = DN; 				//图的类型为有向网 
    
        printf("请输入顶点(不超过10个，以#结束):\n");
        cin>>ch;
        while(ch!='#' && num <10){
            G->vertex[num] = ch;
            cin>>ch;
            num++;
        }
        G->vexnum = num;  //顶点个数
    
        cout<<"请输入对应的弧（ab与ba是方向相反的边）和权值，以###结束"<<endl;
        cin>>a>>b>>weight;
        while(a!='#' && b!='#'){
            cout<<a<<"->"<<b<<":"<<weight<<endl;
            FindPos(G,a,b,pos1,pos2);
            printf("位置a:%d,位置b:%d\n",pos1,pos2);
            if(pos1!= -1 && pos2!= -1){  //忽略不存在的顶点
                G->Arc[pos1][pos2] = weight;
                G->arcnum++;
            }
            cin>>a>>b>>weight;
        }
    }

    返回目录

• 采用邻接表表示法

  由上面图的基本概念可知，创建图与网的区别就是增加一个权值。
  创建有向无向的区别就是无向可以默认生成 对称信息，有向 来与回 不同步。

  • 创建无向图

    void CreateUDG(ALGraph &G) {								//采用邻接表表示法，创建无向图G
    			
    	int i, k;
    	
    	cout << "请输入总顶点数和总边数："  ;				//输出总顶点数，总边数
    	cin >> G.vexnum >> G.arcnum;
    	cout << endl;
    	
    	cout << "请输入顶点：" << endl;
    	for (i = 0 ; i < G.vexnum; i++) {					//输入各点，构建表头结点
    		cout << "请输入第" << (i + 1) << "个顶点的名称：";
    		cin >> G.vertices[i].data;
    		G.vertices[i].fristarrc = NULL;                 //初始化表头结点的指针域为NULL
    	}
    	
    	cout << endl;
    	cout << "请输入一条边依附的顶点：" <<endl;
    	for (k = 0; k < G.arcnum; k++) {
    		VerTexType v1, v2;
    		int i, j;
    		cout << "请输入第" << (k+1) << "条边依附的顶点";
    		cin >> v1 >> v2;								//输入一条边依附的两个顶点
    		i = LocateVex(G, v1);							//确定v1和v2在G中的位置，
    		j = LocateVex(G, v2);							//即顶点在G.vertices(邻接表)中的序号
    												
    		ArcNode *p1 = new ArcNode;						//生成一个新的边结点*p1
    		p1->adjvex = j;									//邻接点序号为j
    		p1->nextarc = G.vertices[i].fristarrc;	
    		G.vertices[i].fristarrc = p1;					//将新节点*p1插入vi的边表
    		  
    		ArcNode *p2 = new ArcNode;						//生成另一个对称的新的边结点*p2
            p2->adjvex = i;									//邻接点序号为i
    		p2->nextarc = G.vertices[j].fristarrc;	
    		G.vertices[j].fristarrc = p2;					//将新结点*p2插入顶点Vj的边表
    				
    	}
    }

  • 创建无向网

    void CreateUDN(ALGraph &G) {							//采用邻接表表示法，创建无向网G
    			
    	int i, k;
    	
    	cout << "请输入总顶点数和总边数："  ;				//输出总顶点数，总边数
    	cin >> G.vexnum >> G.arcnum;
    	cout << endl;
    	
    	cout << "请输入顶点：" << endl;
    	for (i = 0 ; i < G.vexnum; i++) {					//输入各点，构建表头结点
    		cout << "请输入第" << (i + 1) << "个顶点的名称：";
    		cin >> G.vertices[i].data;
    		G.vertices[i].fristarrc = NULL;                 //初始化表头结点的指针域为NULL
    	}
    	
    	cout << endl;
    	cout << "请输入一条边依附的顶点,和权值" <<endl;
    	for (k = 0; k < G.arcnum; k++) {
    		VerTexType v1, v2;
    		int i, j,weight;
    		cout << "请输入第" << (k+1) << "条边依附的顶点";
    		cin >> v1 >> v2>>weight;						//输入一条边依附的两个顶点
    		i = LocateVex(G, v1);							//确定v1和v2在G中的位置，
    		j = LocateVex(G, v2);							//即顶点在G.vertices(邻接表)中的序号
    												
    		ArcNode *p1 = new ArcNode;						//生成一个新的边结点*p1
    		p1->adjvex = j;	
    		p1->info = weight;								//邻接点序号为j
    		p1->nextarc = G.vertices[i].fristarrc;	
    		G.vertices[i].fristarrc = p1;					//将新节点*p1插入vi的边表
    		  
    		ArcNode *p2 = new ArcNode;						//生成另一个对称的新的边结点*p2
            p2->adjvex = i;		
    		p2->info = weight;								//邻接点序号为i
    		p2->nextarc = G.vertices[j].fristarrc;	
    		G.vertices[j].fristarrc = p2;					//将新结点*p2插入顶点Vj的边表
    				
    	}
    }

    返回目录

• 图的遍历

  因为图中的任意顶点都可能和其余的顶点邻接。所以必须记下每个已访问过的顶点，避免同一顶点被访问多次。设一个辅助数组 IsRead[MVNum]**，初始值为0/false，一旦访问过就置1/true。即 **打卡 操作。

  • 深度优先搜索

  • 广度优先搜索

返回目录

• 邻接矩阵表示法总的代码：

  #include<iostream>
  #include<stdio.h> 
  #include<stdlib.h>
  #include<queue>
  #include<math.h> 
  using namespace std;
  
  
  #define MVNum 10//最大顶点数 
  #define MAXINT 32768//表示极大值 
  typedef enum{DG,DN,UDG,UDN} GraphKind; //有向图、有向网、无向图、无向网 
  typedef int arcType;
  typedef char vertexType;
  
  
  #define MAX_SIZE 20
  
  /*定义队列*/
  typedef struct QNode{
      int Qarr[MAX_SIZE];
      int tail,head;
      int size;
  }QNode,*Queue;
  
  void InitQueue(Queue &Q){
      Q= (QNode *)malloc(sizeof(QNode));
      if(Q){
          Q->size = 0;
          Q->head = 0;
          Q->tail = 0;
      }
  }
  
  int isEmpty(Queue Q){
      if(Q->head == Q->tail)
  		return 1;
      return 0;
  }
  
  int isFull(Queue Q){
      if((Q->tail +1) % MAX_SIZE == Q->head)
  		return 1;
      return 0;
  }
  
  /*入队列*/
  void EnterQueue(Queue Q, int data){
      if(isFull(Q)){
          printf("队列已经满!!\n");
          return;
      }
      Q->Qarr[Q->tail] = data;
      Q->size++;
      Q->tail = (Q->tail +1) % MAX_SIZE;
      return;
  }
  
  void OutQueue(Queue Q, int &data){
      if(isEmpty(Q)){
          printf("队列为空!!\n");
          return;
      }
      data= Q->Qarr[Q->head];
      Q->size--;
      Q->head = (Q->head +1) % MAX_SIZE;
      return;
  }
  
  
  
  typedef struct MNode{
  	vertexType vertex[MVNum];	//存储顶点 
  	arcType Arc[MVNum][MVNum];	//邻接矩阵，存储边 
  	int vexnum,arcnum;
     	GraphKind kind;				//图的种类，有向无向等 
  }GraphNode,*Graph;
  
  int IsRead[MVNum];
  
  int Init(Graph &G){
  	G=(GraphNode *)malloc(sizeof(GraphNode));
  	G->vexnum=0;
  	G->arcnum=0;
  	if(G) return 1;
  	else cout<<"初始化出错！"<<endl;
  	return 0;
  }
  
  void FindPos(Graph G,char a,char b,int &pos1,int &pos2){//查找位置 
  	int i=0;
  	pos1=-1;pos2=-1;
  	for(int i=0;i<G->vexnum;i++){
  		if(G->vertex[i]==a){
  			pos1=i;
  			continue;
  		}
  		else if(G->vertex[i]==b){
  			pos2=i;
  			continue;
  		}
  	}
  }
  
  void CreateDG(Graph G)			//创建有向图 
  {
  	int num=0,					//控制输入顶点数 
  		pos1,pos2,				//确认顶点位置 
  		i,j;
  	char a,
  		 b,
  		 ch;					//顶点 
  	for(int i=0;i<MVNum;i++){				//初始化 
  		for(int j=0;j<MVNum;j++){
  			G->Arc[i][j]=0;
  		}
  	}
  	G->kind=DG;								//类型为有向图 
  	cout<<"请输入顶点，以#结束"<<endl;
  	cin>>ch;
  	while(ch!='#'&&num<10){
  		G->vertex[num]=ch;
  		cin>>ch;
  		num++;
  	} 
  	G->vexnum=num;
  	
  	cout<<"请输入对应的弧（ab与ba是方向相反的边），以##结束"<<endl;
  	cin>>a>>b;
  	while(a!='#'&&b!='#'){
  		cout<<a<<"->"<<b<<endl;
  		FindPos(G,a,b,pos1,pos2);
  		cout<<"位置a："<<pos1<<"位置b："<<pos2<<endl;
  		if(pos1!=-1&&pos2!=-1){
  			G->Arc[pos1][pos2]=1;
  			G->arcnum++;
  		}
  		cin>>a>>b;			
  	}
  }
  
  void CreateDN(Graph G)			//创建有向网 
  {
  	int num=0,					//控制输入顶点数 
  		pos1,pos2,				//确认顶点位置 
  		i,j,
  		weight;					//权值 
  	char a,
  		 b,
  		 ch;					//顶点 
      for(i = 0;i < MVNum; i++){ 	//初始化弧
          for(j = 0;j<MVNum; j++){
              G->Arc[i][j] = MAXINT;
          }
      }
      G->kind = DN; 				//图的类型为有向网 
  
      printf("请输入顶点(不超过10个，以#结束):\n");
      cin>>ch;
      while(ch!='#' && num <10){
          G->vertex[num] = ch;
          cin>>ch;
          num++;
      }
      G->vexnum = num;  //顶点个数
  
      cout<<"请输入对应的弧（ab与ba是方向相反的边）和权值，以###结束"<<endl;
      cin>>a>>b>>weight;
      while(a!='#' && b!='#'){
          cout<<a<<"->"<<b<<":"<<weight<<endl;
          FindPos(G,a,b,pos1,pos2);
          printf("位置a:%d,位置b:%d\n",pos1,pos2);
          if(pos1!= -1 && pos2!= -1){  //忽略不存在的顶点
              G->Arc[pos1][pos2] = weight;
              G->arcnum++;
          }
          cin>>a>>b>>weight;
      }
  }
  
  void CreateUDG(Graph G)			//创建无向图 
  {
  	int num=0,					//控制输入顶点数 
  		pos1,pos2,				//确认顶点位置 
  		i,j;
  	char a,
  		 b,
  		 ch;					//顶点 
      for(i = 0;i<MVNum;i++){ 	//初始化弧
          for(j = 0;j<MVNum;j++){
              G->Arc[i][j] = 0;
          }
      }
      G->kind = UDG; 				//图的类型为无向图 
  
      printf("请输入顶点(不超过10个，以#结束):\n");
      cin>>ch;
      while(ch!='#' && num <10){
          G->vertex[num] = ch;
          cin>>ch;
          num++;
      }
      G->vexnum = num;  			//顶点个数
  
      cout<<"请输入对应的弧（ab与ba是一样的边），以##结束"<<endl;
      cin>>a>>b;
      while(a!='#' && b!='#'){
          cout<<a<<"-"<<b<<endl;
          FindPos(G,a,b,pos1,pos2);
          printf("位置a:%d,位置b:%d\n",pos1,pos2);
          if(pos1!= -1 && pos2!= -1){  //忽略不存在的顶点
              G->Arc[pos1][pos2] = 1;
              G->Arc[pos2][pos1] = 1;
              G->arcnum++;
          }
          cin>>a>>b;
      }
  }
  
  void CreateUDN(Graph G)			//创建无向网
  {
  	int num=0,					//控制输入顶点数 
  		pos1,pos2,				//确认顶点位置 
  		i,j,
  		weight;					//权值 
  	char a,
  		 b,
  		 ch;					//顶点 
  		 
  	for(i = 0;i<MVNum; i++){ //初始化弧
          for(j = 0;j<MVNum; j++){
              G->Arc[i][j] = MAXINT;
          }
      }
      G->kind = UDN; //设置图的类型
  
      printf("请输入顶点(不超过10个，以#结束):\n");
      cin>>ch;
      while(ch!='#' && num <10){
          G->vertex[num] = ch;
          scanf("%c",&ch);
          num++;
      }
      G->vexnum = num;  //顶点个数
  
      cout<<"请输入对应的弧（ab与ba是一样的边）和权值，以###结束"<<endl;
      cin>>a>>b>>weight;
      while(a!='#' && b!='#'){
          cout<<a<<"-"<<b<<":"<<weight<<endl;
          FindPos(G,a,b,pos1,pos2);
          printf("位置a:%d,位置b:%d\n",pos1,pos2);
          if(pos1!= -1 && pos2!= -1){  //忽略不存在的顶点
              G->Arc[pos1][pos2] = weight;
              G->Arc[pos2][pos1] = weight;
              G->arcnum++;
          }
          cin>>a>>b>>weight;
      }
  }
  
  void BuildGraph(Graph G){
  	int choose=0;				//选择 
  	cout<<"请选择建立图的类型:"<<endl;
  	cout<<"1.有向图      2.有向网"<<endl<<"3.无向图      4.无向网"<<endl;
  	cin>>choose;
  	cout<<endl;
  	switch(choose){
  		case 1:CreateDG(G);break;
  		case 2:CreateDN(G);break;
  		case 3:CreateUDG(G);break;
  		case 4:CreateUDN(G);break;
  		default:cout<<"ERROR";return;
  	}
  }
  
  void DepthFS(Graph G,int pos){		 /*深度优先搜索for图*/
      int i = 0,j = 0;
      if(IsRead[pos] == 0){
          IsRead[pos] = 1; 			//被访问过，打卡 
          printf("遍历顶点%c\n",G->vertex[pos]);
      }
  
      for(i = 0;i<G->vexnum;i++){
          if(G->Arc[pos][i] == 1 && IsRead[i] ==0){  //存在弧
              DepthFS(G,i);
          }
      }
  }
  
  void DepthFS1(Graph G,int pos){		 /*深度优先搜索for网*/
      int i = 0,j = 0;
      if(IsRead[pos] == 0){
          IsRead[pos] = 1; 			//被访问过，打卡 
          printf("遍历顶点%c\n",G->vertex[pos]);
      }
  
      for(i = 0;i<G->vexnum;i++){
          if(G->Arc[pos][i] !=INFINITY && IsRead[i] ==0){  //存在弧且未被遍历
              DepthFS1(G,i);
          }
      }
  }
  
  /*深度优先搜索*/
  void DFS(Graph G){
      if(G->kind == DG || G->kind == UDG){  //图
          DepthFS(G,0);
      }else if(G->kind == DN || G->kind == UDN){ //网
          DepthFS1(G,0);
      }
  }
  
  void BFS1(Graph G,int pos){ //广度优先搜索for图
      int i = 0,temp;
      Queue Q;
      InitQueue(Q);
      for(i = 0; i<G->vexnum;i++){  //清零
          IsRead[i] = 0;
      }
      if(IsRead[pos] ==0){
          IsRead[pos] = 1;
          printf("遍历顶点:%c\n",G->vertex[pos]);
      }
      EnterQueue(Q,pos);
      while(!isEmpty(Q)){//当队列不为空
          OutQueue(Q,temp);
          for(i = 0; i< G->vexnum;i++){
              if(G->Arc[temp][i] == 1 && IsRead[i] == 0){
                  IsRead[i] = 1;
                  printf("遍历顶点:%c\n",G->vertex[i]);
                  EnterQueue(Q,i);
              }
          }
      }
      free(Q);
  }
  
  void BFS2(Graph G,int pos){ //广度优先搜索for图
      int i = 0,temp;
      Queue Q;
      InitQueue(Q);
      for(i = 0; i <G->vexnum;i++){  //清零
          IsRead[i] = 0;
      }
      if(IsRead[pos] ==0){
          IsRead[pos] = 1;
          printf("遍历顶点:%c\n",G->vertex[pos]);
      }
      EnterQueue(Q,pos);
      while(!isEmpty(Q)){//当队列不为空
          OutQueue(Q,temp);
          for(i = 0; i< G->vexnum;i++){
              if(G->Arc[temp][i] != INFINITY && IsRead[i] == 0){
                  IsRead[i] = 1;
                  printf("遍历顶点:%c\n",G->vertex[i]);
                  EnterQueue(Q,i);
              }
          }
      }
      free(Q);
  }
  
  void BFS(Graph G){
      if(G->kind == DG || G->kind == UDG){  		//图
          BFS1(G,0);
      }else if(G->kind == DN || G->kind == UDN){ 	//网
          BFS2(G,0);
      }
  }
  
  int main(){
      int i = 0;
      Graph G = NULL;
      Init(G);
      BuildGraph(G);
      for(i = 0; i<MVNum; i++){
          IsRead[i] = 0;  //未被遍历
      }
      printf("\n深度优先搜索:\n");
      DFS(G);
      printf("\n广度优先搜索:\n");
      BFS(G);
      return 0;
  }

  创建如图所示的图：
  

  • 运行结果：

    
    
    返回目录

• 邻接表表示法总的代码：

  #include <iostream>
  #include<queue>
  using namespace std;
  
  #define MVNum 100									    //最大顶点信息
  int IsRead[MVNum];
  
  typedef char VerTexType;
  typedef int OtherInfo;
  
     //----------图的邻接表存储表示-----------
  typedef struct ArcNode {								//边结点
  	int adjvex;											//该边所指向顶点的位置
  	struct ArcNode *nextarc;							//指向下一条边的指针
  	OtherInfo info;										//和边相关的信息
  													
  }ArcNode;
  
  typedef struct VNode {
  	VerTexType data;									//顶点信息
  	ArcNode *fristarrc;							    	//指向第一条依附该顶点的边 
  	                                                                                                                                                                                                                                                                
  } VNode,AdjList[MVNum];
  
  typedef struct {
  	AdjList vertices;									// 邻接表
  	int vexnum;                                         //图的当前顶点数
  	int arcnum;											//图的当前边数	
  }ALGraph;
  
  int LocateVex(ALGraph G,VerTexType v) {
  	for (int i = 0; i < G.vexnum; i++) 
  		if (G.vertices[i].data == v)
  			return i;	      
  		return -1;	
  }
  
  void CreateUDG(ALGraph &G) {								//采用邻接表表示法，创建无向图G
  			
  	int i, k;
  	
  	cout << "请输入总顶点数和总边数："  ;				//输出总顶点数，总边数
  	cin >> G.vexnum >> G.arcnum;
  	cout << endl;
  	
  	cout << "请输入顶点：" << endl;
  	for (i = 0 ; i < G.vexnum; i++) {					//输入各点，构建表头结点
  		cout << "请输入第" << (i + 1) << "个顶点的名称：";
  		cin >> G.vertices[i].data;
  		G.vertices[i].fristarrc = NULL;                 //初始化表头结点的指针域为NULL
  	}
  	
  	cout << endl;
  	cout << "请输入一条边依附的顶点:" <<endl;
  	for (k = 0; k < G.arcnum; k++) {
  		VerTexType v1, v2;
  		int i, j;
  		cout << "请输入第" << (k+1) << "条边依附的顶点";
  		cin >> v1 >> v2;								//输入一条边依附的两个顶点
  		i = LocateVex(G, v1);							//确定v1和v2在G中的位置，
  		j = LocateVex(G, v2);							//即顶点在G.vertices(邻接表)中的序号
  												
  		ArcNode *p1 = new ArcNode;						//生成一个新的边结点*p1
  		p1->adjvex = j;									//邻接点序号为j
  		p1->nextarc = G.vertices[i].fristarrc;	
  		G.vertices[i].fristarrc = p1;					//将新节点*p1插入vi的边表
  		  
  		ArcNode *p2 = new ArcNode;						//生成另一个对称的新的边结点*p2
          p2->adjvex = i;									//邻接点序号为i
  		p2->nextarc = G.vertices[j].fristarrc;	
  		G.vertices[j].fristarrc = p2;					//将新结点*p2插入顶点Vj的边表
  				
  	}
  }
  
  void CreateUDN(ALGraph &G) {							//采用邻接表表示法，创建无向网G
  			
  	int i, k;
  	
  	cout << "请输入总顶点数和总边数："  ;				//输出总顶点数，总边数
  	cin >> G.vexnum >> G.arcnum;
  	cout << endl;
  	
  	cout << "请输入顶点：" << endl;
  	for (i = 0 ; i < G.vexnum; i++) {					//输入各点，构建表头结点
  		cout << "请输入第" << (i + 1) << "个顶点的名称：";
  		cin >> G.vertices[i].data;
  		G.vertices[i].fristarrc = NULL;                 //初始化表头结点的指针域为NULL
  	}
  	
  	cout << endl;
  	cout << "请输入一条边依附的顶点,和权值" <<endl;
  	for (k = 0; k < G.arcnum; k++) {
  		VerTexType v1, v2;
  		int i, j,weight;
  		cout << "请输入第" << (k+1) << "条边依附的顶点";
  		cin >> v1 >> v2>>weight;						//输入一条边依附的两个顶点
  		i = LocateVex(G, v1);							//确定v1和v2在G中的位置，
  		j = LocateVex(G, v2);							//即顶点在G.vertices(邻接表)中的序号
  												
  		ArcNode *p1 = new ArcNode;						//生成一个新的边结点*p1
  		p1->adjvex = j;	
  		p1->info = weight;								//邻接点序号为j
  		p1->nextarc = G.vertices[i].fristarrc;	
  		G.vertices[i].fristarrc = p1;					//将新节点*p1插入vi的边表
  		  
  		ArcNode *p2 = new ArcNode;						//生成另一个对称的新的边结点*p2
          p2->adjvex = i;		
  		p2->info = weight;								//邻接点序号为i
  		p2->nextarc = G.vertices[j].fristarrc;	
  		G.vertices[j].fristarrc = p2;					//将新结点*p2插入顶点Vj的边表
  				
  	}
  }
  
  void DepthFS(ALGraph G,int pos){ 		/*深度优先搜索for图*/
  	ArcNode *p=NULL;
      int i = 0,j = 0;
      if(IsRead[pos] == 0){
          IsRead[pos] = 1; 				//被访问过，打卡 
          printf("遍历顶点%c\n",G.vertices[pos].data);
          p= G.vertices[pos].fristarrc; //指向依赖该点的边。边又有三个域：邻接点的位置，权重，指向下一条边的指针。 
      }
  	 
  	while(p!=NULL){
  		if(!IsRead[p->adjvex]){
  			DepthFS(G,p->adjvex);			
  		}						
  		p=p->nextarc;
  	}
  }
  
  void BFS(ALGraph G,int pos){ 		//广度优先搜索for图
      int i = 0,temp;
      ArcNode * p = NULL;
      queue<char>Q;
      
      for(i = 0; i <G.vexnum;i++){ 	 //清零
          IsRead[i] = 0;
      }
      
      if(IsRead[pos] ==0){
          IsRead[pos] = 1;
          printf("遍历顶点:%c\n",G.vertices[pos].data);
      }
      
      Q.push(pos);
      while(!Q.empty()){			//当队列不为空
          temp=Q.front();
          Q.pop();
          p=G.vertices[temp].fristarrc;
          while(p)
          {
              if(!IsRead[p->adjvex])
              {
                  IsRead[p->adjvex]=true;
                  printf("遍历顶点:%c\n",G.vertices[p->adjvex].data);
                  Q.push(p->adjvex);
              }
              p=p->nextarc;
          }
      }
  }
  
  int main(){
  	ALGraph G;
  	CreateUDG(G);
  	
  	int i;
  	cout << endl;
  	for (i = 0; i < G.vexnum; i++) {
  		VNode temp = G.vertices[i];					 //将G的顶点信息付给temp
  		ArcNode *p = temp.fristarrc;				 //将顶点信息temp中的边信息给p
  		if ( p ==  NULL){
  			cout << G.vertices[i].data;
  			cout << endl;
  		}
  		else {
  			cout << temp.data;
  			while (p)
  			{
  				cout << "->";
  				cout << p->adjvex;
  				p = p->nextarc;
  
  			}
  //			if(!p){
  //				cout<<"->^";
  //			} 
  		}
  		cout << endl;
  	}
  	cout<<"深度遍历:"<<endl; 
  	DepthFS(G,0);
  	cout<<"广度遍历:"<<endl; 
  	BFS(G,0); 
  	return 0;
  }

  • 运行结果：

    创建上图所示的图
    
    
    返回目录