精华内容
下载资源
问答
  • 花了点时间,写了下 无向图lingjieb
    花了点时间,写了下 无向图邻接表的代码 还有2中遍历,和教科书上差不多
    
    #include<iostream>
    #include<queue>
    using namespace std;
    # define MVNum 100
    
    
    
    int visited[MVNum];
    queue<int>q;
    struct ArcNode
    {
    	int adjvex;
        ArcNode *nextarc;
    };
    
     typedef struct VNode
    {
    	char data;
        ArcNode *firstarc;
    }Adjlist[MVNum];
    
    struct ALGraph
    {
    	Adjlist vertices;
    	int vexnum;
    	int arcnum;
    };
    
    ALGraph G;
    
    int locatevex(ALGraph G,char x)
    {
    	int i=0;
    	while(i<G.vexnum && x!=G.vertices[i].data)
    		i++;
    	if(i<G.vexnum)
    	return i;
    }
    
    void CreateUDG(ALGraph &G)
    {
    	cout<<"请输入图的顶点数:\n";
    	cin>>G.vexnum;
    	cout<<"请输入图的弧数:\n";
    	cin>>G.arcnum;
    	char v1;
    	char v2;
    	int v1locate;
    	int v2locate;
    	ArcNode * p,* q;
    	cout<<"---------------输入图的信息---------------\n"<<endl;
    	cout<<"输入顶点信息(点对边)"<<endl;
    	for(int i=0;i<G.vexnum;i++)
    	{  
    		cin>>G.vertices[i].data;
    		G.vertices[i].firstarc=NULL;
    	}
    		for(int k=1;k<=G.arcnum;k++)
    		{
    			cout<<"输入相关的边"<<endl;
    			cin>>v1>>v2;
                v1locate=locatevex(G,v1);
                v2locate=locatevex(G,v2);
    			p=new ArcNode;
    			p->adjvex=v2locate;
    			p->nextarc=G.vertices[v1locate].firstarc;
    			G.vertices[v1locate].firstarc=p;
                q=new ArcNode;
    
    			q->adjvex=v1locate;
    			q->nextarc=G.vertices[v2locate].firstarc;
    			G.vertices[v2locate].firstarc=q;
    		}
    }
    
    void DFS(ALGraph G,int v)
    {
        visited[v]=1;
    	cout<<G.vertices[v].data<<"  ";
    	for(ArcNode *p=G.vertices[v].firstarc;p;p=p->nextarc)
    	{
    		if(!visited[p->adjvex])
             DFS(G,p->adjvex);					
    	}
    }
    
    void dfstraverse(ALGraph G,int vex)
    {
    	for(int i = 0;i < G.vexnum;i++)
    		visited[i]=0;				
    	DFS(G,vex);						
    	for(int v = 0;v < G.vexnum;v ++)	
    		if(!visited[v]) 
    			DFS(G,v);
    }  
    
    
    
    
    int BFS(ALGraph G)
    {
        for(int i = 0;i < G.vexnum;i++)	
    		visited[i]=0;				
    	q.empty();
        int v;
    	int u;
    	for(v=0;v<G.vexnum;v++)
    		if(!visited[v])
    		{
    			visited[v]=1;
    			cout<<G.vertices[v].data<<"  ";
    			q.push(v);
    			while(!q.empty())
    			{
    				u=q.front();
    				q.pop();
    				for(ArcNode *p=G.vertices[v].firstarc;p;p=p->nextarc)
    					if(!visited[p->adjvex])
    					{
    						visited[p->adjvex]=1;
    						cout<<G.vertices[p->adjvex].data<<"  ";
    						q.push(p->adjvex);
    					}
    			}
    		}
    		return 1;
    }
    
    	int isBegin()
    	 {
        
    	 int m=0;
        cout<<"是否开始图的创建及遍历(0表示否)?\n";
    	cin>>m;
    	return m;
    	}
    int  main()
    
    { 
    	
    
    
    	while(isBegin())
    	{
    	int a;
    	int t=0;
        CreateUDG(G);
    	
        cout<<"输入图深度遍历的起点"<<endl;
        cin>>a;
        cout<<"深度优先遍历 :"<<endl;
        DFS(G,a);
        cout<<'\n';
        cout<<"广度优先遍历 :"<<endl;
        BFS(G);
    	cout<<'\n';
    
    
    	cout<<"是否清屏(0表示不) ?";
    	cin>>t;
    	if(t!=0)
    	{
    	system("cls");
    	}
    	
    	
    	}
    	return 0;
    }
    

    展开全文
  • 邻接表 建立 深度遍历 广度遍历

    分享一下我老师大神的人工智能教程!零基础,通俗易懂!http://blog.csdn.net/jiangjunshow

    也欢迎大家转载本篇文章。分享知识,造福人民,实现我们中华民族伟大复兴!

                   

         图的邻接表表示法类似于树的孩子链表表示法。对于图G中的每个顶点vi,该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表,这个单链表就称为顶点vi的邻接表(Adjacency List)。

    以下代码测试过,为图的邻接表表示方式。

     C++ Code 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    /************************************************************************/
    /* 图的邻接表存储结构                                                    */
    /************************************************************************/
    #ifdef _MSC_VER
    #define _CRTDBG_MAP_ALLOC
    #include <stdlib.h>
    #include <crtdbg.h>
    #ifdef _DEBUG
    #define  new  new(_NORMAL_BLOCK, __FILE__, __LINE__) 
    #endif
    #endif

    #include <stdio.h>
    #define MaxVertexNum  100
    #define QueueSize  30 
    typedef  enum{ FALSE, TRUE }Boolean;
    Boolean visited[MaxVertexNum];
    typedef  char VertexType;
    typedef  int EdgeType;
    typedef  struct node      //边表结点
    {
         int adjvex;          //邻接点域
         struct node *next;   //域链
         //若是要表示边上的权,则应增加一个数据域
    }EdgeNode;
    typedef  struct vnode     //顶点边结点
    {
        VertexType vertex;   //顶点域
        EdgeNode *firstedge; //边表头指针
    }VertexNode;
    typedef VertexNode AdjList[MaxVertexNum];    //AdjList是邻接表类型
    typedef  struct
    {
        AdjList adjlist;     //邻接表
         int n, e;            //图中当前顶点数和边数
    }ALGraph;                //对于简单的应用,无须定义此类型,可直接使用AdjList类型
    /************************************************************************/
    /* 建立无向图的邻接表算法                                               */
    /************************************************************************/
    void CreateGraphAL(ALGraph *G)
    {
         int i, j, k;
        EdgeNode * s;
        printf( "请输入顶点数和边数(输入格式为:顶点数,边数):\n");
        scanf( "%d,%d", &(G->n), &(G->e));        // 读入顶点数和边数   
        printf( "请输入顶点信息(输入格式为:顶点号<CR>)每个顶点以回车作为结束:\n");
         for (i =  0; i < G->n; i++)               // 立有n个顶点的顶点表   
        {
            scanf( "\n%c", &(G->adjlist[i].vertex));  // 读入顶点信息   
            G->adjlist[i].firstedge =  NULL;             // 点的边表头指针设为空   
        }
        printf( "请输入边的信息(输入格式为:i,j):\n");
         for (k =  0; k < G->e; k++)       // 建立边表   
        {
            scanf( "\n%d,%d", &i, &j);  // 读入边<Vi,Vj>的顶点对应序号   
            s =  new EdgeNode;          // 生成新边表结点s   
            s->adjvex = j;          // 邻接点序号为j   
            s->next = G->adjlist[i].firstedge;  // 将新边表结点s插入到顶点Vi的边表头部   
            G->adjlist[i].firstedge = s;
            s =  new EdgeNode;
            s->adjvex = i;
            s->next = G->adjlist[j].firstedge;
            G->adjlist[j].firstedge = s;
        }
    }
    /************************************************************************/
    /* 深度优先遍历                                                         */
    /************************************************************************/
    void DFS(ALGraph *G,  int i)
    {
         //以vi为出发点对邻接表表示的图G进行深度优先搜索
        EdgeNode *p;
        printf( "visit vertex:%c\n", G->adjlist[i].vertex);   // 访问顶点vi
        visited[i] = TRUE;               //标记vi已访问
        p = G->adjlist[i].firstedge;         //取vi边表的头指针
         while (p)
        {                                //依次搜索vi的邻接点vj,这里j=p->adjvex
             if (!visited[p->adjvex])     //若vi尚未被访问
                DFS(G, p->adjvex);       //则以Vj为出发点向纵深搜索
            p = p->next;                      //找vi的下一邻接点
        }
    }
    void DFSTraverseM(ALGraph *G)
    {
         int i;
         for (i =  0; i < G->n; i++)
            visited[i] = FALSE;
         for (i =  0; i < G->n; i++)
             if (!visited[i])
                DFS(G, i);
    }
    /************************************************************************/
    /* 广度优先遍历                                                         */
    /************************************************************************/
    typedef  struct
    {
         int front;
         int rear;
         int count;
         int data[QueueSize];
    }CirQueue;
    void InitQueue(CirQueue *Q)
    {
        Q->front = Q->rear =  0;
        Q->count =  0;
    }
    int QueueEmpty(CirQueue *Q)
    {
         return Q->count ==  0;
    }
    int QueueFull(CirQueue *Q)
    {
         return Q->count == QueueSize;
    }
    void EnQueue(CirQueue *Q,  int x)
    {
         if (QueueFull(Q))
            printf( "Queue overflow");
         else
        {
            Q->count++;
            Q->data[Q->rear] = x;
            Q->rear = (Q->rear +  1) % QueueSize;
        }
    }
    int DeQueue(CirQueue *Q)
    {
         int temp;
         if (QueueEmpty(Q))
        {
            printf( "Queue underflow");
             return  NULL;
        }
         else
        {
            temp = Q->data[Q->front];
            Q->count--;
            Q->front = (Q->front +  1) % QueueSize;
             return temp;
        }
    }
    void BFS(ALGraph*G,  int k)
    {    // 以vk为源点对用邻接表表示的图G进行广度优先搜索
         int i;
        CirQueue Q;              //须将队列定义中DataType改为int
        EdgeNode *p;
        InitQueue(&Q);           //队列初始化
        printf( "visit vertex:%c\n", G->adjlist[k].vertex);       //访问源点vk
        visited[k] = TRUE;
        EnQueue(&Q, k);          //vk已访问,将其人队。(实际上是将其序号人队)
         while (!QueueEmpty(&Q))
        {                                    //队非空则执行
            i = DeQueue(&Q);                     //相当于vi出队
            p = G->adjlist[i].firstedge;         //取vi的边表头指针
             while (p)
            {                                //依次搜索vi的邻接点vj(令p->adjvex=j)
                 if (!visited[p->adjvex])
                {                            //若vj未访问过
                    printf( "visit vertex:%c\n", G->adjlist[p->adjvex].vertex);       //访问vj
                    visited[p->adjvex] = TRUE;
                    EnQueue(&Q, p->adjvex);  //访问过的vj人队
                }
                p = p->next;                     //找vi的下一邻接点
            }
        }
    }
    void BFSTraverseM(ALGraph *G)
    {
         int i;
         for (i =  0; i < G->n; i++)
            visited[i] = FALSE;
         for (i =  0; i < G->n; i++)
             if (!visited[i])
                BFS(G, i);
    }
    /************************************************************************/
    /* 打印邻接表                                                     */
    /************************************************************************/
    void PrintfGraphAL(ALGraph *G)
    {
         for ( int i =  0; i < G->n; i++)
        {
            printf( "vertex:%c", G->adjlist[i].vertex);
            EdgeNode *p = G->adjlist[i].firstedge;
             while (p)
            {
                printf( "→:%d", p->adjvex);
                p = p->next;
            }
            printf( "\n");
        }
    }
    /************************************************************************/
    /* 删除邻接表                                                     */
    /************************************************************************/
    void DeleteGraphAL(ALGraph *G)
    {
         for ( int i =  0; i < G->n; i++)
        {
            EdgeNode *q;
            EdgeNode *p = G->adjlist[i].firstedge;
             while (p)
            {
                q = p;
                p = p->next;
                 delete q;
            }
            G->adjlist[i].firstedge =  NULL;
        }
    }
    /************************************************************************/
    /* 主函数调用                                                           */
    /************************************************************************/
    int main()
    {
    #ifdef _MSC_VER
        _CrtSetDbgFlag(_CRTDBG_LEAK_CHECK_DF | _CrtSetDbgFlag(_CRTDBG_REPORT_FLAG));
        _CrtDumpMemoryLeaks();
    #endif

        ALGraph G;
        CreateGraphAL(&G);
        printf( "深度优先遍历:\n");
        DFSTraverseM(&G);
        printf( "广度优先遍历:\n");
        BFSTraverseM(&G);
        printf( "邻接表:\n");
        PrintfGraphAL(&G);
        DeleteGraphAL(&G);

         return  0;
    }

    测试结果如下:

     NormalText Code 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    请输入顶点数和边数(输入格式为:顶点数,边数):
    8,9
    请输入顶点信息(输入格式为:顶点号<CR>)每个顶点以回车作为结束:
    A
    B
    C
    D
    E
    F
    G
    H
    请输入边的信息(输入格式为:i,j):
    0,1
    0,2
    1,3
    1,4
    2,5
    2,6
    3,7
    4,7
    5,6
    深度优先遍历:
    visit vertex:A
    visit vertex:C
    visit vertex:G
    visit vertex:F
    visit vertex:B
    visit vertex:E
    visit vertex:H
    visit vertex:D
    广度优先遍历:
    visit vertex:A
    visit vertex:C
    visit vertex:B
    visit vertex:G
    visit vertex:F
    visit vertex:E
    visit vertex:D
    visit vertex:H
    邻接表:
    vertex:A→:2→:1
    vertex:B→:4→:3→:0
    vertex:C→:6→:5→:0
    vertex:D→:7→:1
    vertex:E→:7→:1
    vertex:F→:6→:2
    vertex:G→:5→:2
    vertex:H→:4→:3
    请按任意键继续. . .


     

    如果测试有误,若是代码有错,请指出,共同学习。

               

    给我老师的人工智能教程打call!http://blog.csdn.net/jiangjunshow

    这里写图片描述
    展开全文
  • 有关深度优先遍历的概念请参考我的前一篇博文。 #include <iostream> #include <cstring> using namespace std; typedef char VertexType; typedef int EdgeType; const int MAXVEX = 110; typedef ...

    话不多说,直接上代码。有关深度优先遍历的概念请参考我的前一篇博文。

    #include <iostream>
    #include <cstring>
    using namespace std;
    typedef char VertexType;
    typedef int EdgeType;
    const int MAXVEX = 110;
    typedef struct EdgeNode{ //存储边表节点 
     int adjvex;    //邻接点域,存储该顶点对应的下标。 
     EdgeType weight;  //存储权值 
     struct EdgeNode *next; //指向下一个邻接点 
    }EdgeNode;
    typedef struct VertexNode{ //存储表顶点,实现方法位将表顶点存放在数组中 
     VertexType data;  //存储顶点信息(权值) 
     EdgeNode *firstedge; //边表头指针 
    }VertexNode,AdjList[MAXVEX];//实现方法为数组 
    typedef struct{    //存储图的结构体 
     AdjList adjList;  /*adjList存储一个图的邻接表数组,相当于一个GraphAdjList 
     变量存储一张图*/ 
     int numVertexe,numEdges;//图中顶点的总个数与边的总个数 
    }GraphAdjList;
    void CreateALGraph(GraphAdjList *G){
     int i,j,k;
     EdgeNode *e;
     //i,j,k,*e均为一会儿建立图时需用到的变量,此处提前声明
     cout<<"请输入顶点数和边数:";
     cin>>G->numVertexe>>G->numEdges;
     cout<<"请输入"<<G->numVertexe<<"个顶点存储的信息";
     for(i=0;i<G->numVertexe;i++){//输入顶点信息,建立顶点表 
      cin>>G->adjList[i].data;
      G->adjList[i].firstedge=NULL;//将边表置为空 
     } 
     for(k=0;k<G->numEdges;k++){//建立边表 
      cout<<"输入边(vi,vj)上的顶点序号:";
      cin>>i>>j;//输入边(vi,vj)上的顶点序号
      e = new EdgeNode;  //生成边表结点 
      e->adjvex = j;//邻接序号为j 
      e->next = G->adjList[i].firstedge;//第一步 
      G->adjList[i].firstedge=e;//第二步
      /*由于建立的是一个无向图,因此两个结点间都应有关联,第一步与第二步的作用 
      就是使两个方向均有关联,下同。*/
      /*!*/e = new EdgeNode;
      e->adjvex=i;
      e->next=G->adjList[j].firstedge;
      G->adjList[j].firstedge=e;/*!*/ 
      /*双叹号注释的区间,看似与上面的代码如初一辙,实际上这正是实现邻接表的关
      键。邻接表的表头是存放在数组当中的,数组中的下标已经存放了每一个顶点的信
      息。而此处建立的是一个无向图,举个例子来说,我们建立的是由i到j的无向图,
      那么显然先建立i到j的关系,在头数组中找到节点i,在其后建立边表节点j。而反
      过来,j与i也有关联,也需要在头数组中找到节点j,在其后建立边表节点i,如此
      ,才能建立一个无向图的邻接表。*/ 
      
      /*!主函数略,此处仅给出邻接表的声明与建立邻接表的函数。!*/ 
     }
    }
    bool visited[MAXVEX];
    void DFS(GraphAdjList GL,int i){
     EdgeNode *p;//边表结点temp变量 
     visited[i] = true;
     cout<<GL.adjList[i].data;
     p=GL.adjList[i].firstedge;
     while(p){
      if(!visited[p->adjvex]){
       DFS(GL,p->adjvex);
      }
      p=p->next;
     }
    } 
    void DFSTraverse(GraphAdjList GL){
     memset(visited,false,sizeof(visited));
     for(int i=0;i<GL.numVertexe;i++){
      if(!visited[i]){
       DFS(GL,i);
      }
     }
    }
    int main()
    {
     GraphAdjList GL;
     CreateALGraph(&GL);
     DFSTraverse(GL);
     return 0;
    }
    展开全文
  • 数据结构——无向图创建邻接表以及深度遍历、广度遍历一、邻接表概念二、创建邻接表 一、邻接表概念 在无向图中,顶点存储在顶点表中,以一个顶点为标记,指向边链表,两者组合在一起,称为 邻接表无向图的每...

    一、邻接表概念

    在无向图中,顶点存储在顶点表中,以一个顶点为标记,指向边链表,两者组合在一起,称为 邻接表

    1. 对无向图的每个顶点vi建立一个单链表,第i个单链表中的结点表示依附于顶点vi的边(对于有向图则是以顶点vi为尾的弧)。这个单链表就称为顶点vi的边表(对于有向图则称为出边表)
    2. 边表的头指针和顶点的数据信息采用顺序存储(称为顶点表)
    3. 邻接表中存在两种结点:顶点表结点和边表结点
    4. 顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc)构成
    5. 边表(邻接表)结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc)构成

    如图:

    在这里插入图片描述

    在这里插入图片描述

    二、邻接表实现

    具体样例

    在这里插入图片描述

    基本每一步,都有注释!!可认真看并理解!!!

    (1)准备前提——结构体定义

    #define MAXSIZE 100
    
    //深度遍历标记数组 
    int DfsVist[MAXSIZE]; 
    //广度遍历标记数组 
    int BfsVist[MAXSIZE];
    
    //	边链表 
    typedef struct EdgeLink{
    	
    	int Local;					//	存放该顶点对应边链表中数据 						 
    	
    	struct EdgeLink *next;		//	边链表节点指针  
    	
    }Edge,*ELINK;
    
    //	顶点表 
    typedef struct VertexLink{
    	
    	int Vertex;					//	存放一条边链表对应的顶点 
    	ELINK FirstNode;			//	指向该顶点对应边链表的头节点 
    	
    }Vertex[MAXSIZE],*VLINK;
    
    //	存放顶点和边,指向顶点表结构体数组 
    typedef struct MyGraph{
    	
    	int Vnum;	//	存放顶点数 
    	int Enum;	//	存放边数 
    	
    	Vertex List;	//	边链表对应的顶点表中顶点结构体 
    	
    }MyGraph;
    
    

    (2)创建边链表

    //	创建边链表
    void CreateLink(MyGraph *T)
    {
    	int i,j;
    	int v1,v2;
    	ELINK p;		//	边链表指针 
    	ELINK q;
    	
    	printf("请输入顶点数和边数(空格隔开):\n");
    	
    	scanf("%d%d",&(T->Vnum),&(T->Enum));
    	
    	
    	//	初始化顶点表结构体数组 
    	for(i=0;i<T->Vnum;i++)
    	{
    		printf("请输入第%d个顶点的信息:\n",i+1);
    		
    		scanf("%d",&(T->List[i].Vertex));		//	存放顶点在顶点表中 
    		
    		T->List[i].FirstNode = NULL; 		//	让每个顶点表第一个指向边链表的指针为NULL 
    	}
    	
    	//	打印顶点坐标和顶点表中顶点数据 
    	printf("---------------------------\n"); 
    	for(i=0;i<T->Vnum;i++)
    	{
    		printf("顶点下标为:%d   顶点数据为: %d\n",i,T->List[i].Vertex); 	
    	}
    	printf("---------------------------\n");
    	
    	//	插入边链表数据	
    	for(i=0;i<T->Enum;i++)
    	{
    		//	因为顶点表为顺序表,所以要按顶点顺序输入相连边 
    		printf("请输入两个连接顶点下标(空格隔开):\n");
    		
    		scanf("%d%d",&v1,&v2);
    		getchar(); 
    		
    		q = (ELINK)malloc(sizeof(Edge));	//	创建边链表节点,分配内存 
    				
    		q->Local = v2;	//	记录与该顶点连接边的顶点坐标
    				
    		q->next = NULL;						//	让尾巴指向NULL 
    				
    		if(!T->List[v1].FirstNode){	//	判断是否为这个顶点第一个指向的数据 
    					
    			T->List[v1].FirstNode = q;
    					
    		}else{
    				//	这个顶点已经指向了一条边,以这条边为头节点,尾插法 
    			p = T->List[v1].FirstNode;	//	临时存放头节点 
    			while(p->next)	//	让节点指针遍历到尾巴上 
    			{
    				p = p->next;
    			}
    			p->next = q;	//	让新插的节点连接到之前边节点的尾巴上 
    		}
    			
    		q = (ELINK)malloc(sizeof(Edge));	//	创建边链表节点,分配内存 
    				
    		q->Local = v1;	//	记录与该顶点连接边的顶点坐标
    			
    		q->next = NULL;						//	让尾巴指向NULL 
    				
    		if(!T->List[v2].FirstNode){	//	判断是否为这个顶点第一个指向的数据 
    					
    			T->List[v2].FirstNode = q;
    					
    		}else{
    					//	这个顶点已经指向了一条边,以这条边为头节点,尾插法 
    			p = T->List[v2].FirstNode;	//	临时存放头节点 
    			while(p->next)	//	让节点指针遍历到尾巴上 
    			{
    				p = p->next;
    			}
    			p->next = q;	//	让新插的节点连接到之前边节点的尾巴上 
    		}
    			
    	} 
    	
    }
    

    (3)打印边链表

    //	打印邻接表 
    void PrintLink(MyGraph *S) 
    {
    	MyGraph *T = S;
    	ELINK Q;			//	防止边链表指针指到NULL ,用临时指针代替遍历打印 
    		
    	int i;
    	printf("打印邻接表结果如下:\n");
    	for(i=0;i<T->Vnum;i++)
    	{
    		Q = T->List[i].FirstNode;	//	接受每个顶点指向对应边链表的头节点指针 
    		printf("%d--->",i);
    		
    		while(1)
    		{
    			if(Q == NULL)	//	指针指到尾巴 NULL
    			{
    				putchar('\n');
    				break;
    			}
    			printf("------->%3d",Q->Local);
    			
    			Q = Q->next;	
    		}
    	}
    	putchar('\n');
    }
    
    

    (4)深度优先遍历

    //*****************	深度优先遍历算法—邻接表 *****************//
    void DFS_Link(MyGraph *T,int n)
    {	
    	int i,j;
    	ELINK q;	//	指向边链表节点指针 
    	
    	if(n<0 || n>=T->Vnum)
    	{
    		printf("输入有误\n");
    		return;	
    	}
    		DfsVist[n] = 1;		//	遍历一个顶点,做下标记 1  
    
    		printf(" %d",T->List[n].Vertex);
    		
    		q = T->List[n].FirstNode;	//q指向下标为i所对顶点 对应的边链表的第一个边结点	
    		
    		while(q!=NULL)	
    		{	
    			if(DfsVist[q->Local]!=1)
    			{
    			
    				j = q->Local;
    				DFS_Link(T,j);
    			} 
    			
    			q = q->next;
    		}
    	
    	
    	 
    } 
    //	初始化深度遍历—邻接表 
    void Init_DFSLINK(MyGraph *Q)
    {
    	int i;
    	for(i=0;i<Q->Vnum;i++)
    	{
    		DfsVist[i] = 0;
    	}
    		
    	for(i=0;i<Q->Vnum;i++)
    	{
    		if(!DfsVist[i])
    		{
    		 DFS_Link(Q,i);	//	此顶点没有被标记,开始递归遍历
    		}
    	}
    	putchar('\n'); 
    	
    }
    
    

    (5)广度优先搜索

    //	广度遍历 
    void BFS(MyGraph *S,int t)
    {
    	ELINK P; 			//	指向顶点所对应的边链表中 
    	
    	int i;
    	int v;		//	用来接收边链表对应的顶点
    	
    	
    	//	创建一个数组队列 
    	int Queue[MAXSIZE];
    	int front = 0;			//	队头 
    	int rear = 0;			//	队尾 
    		
    	printf("%d ",S->List[t].Vertex);	//	输出当前遍历边链表的顶点 
    	BfsVist[t] = 1;		//	将该顶点作标记
    	
    	rear = (rear+1)%MAXSIZE;	//	入队一个让队尾指向后移一位
    	Queue[rear] = t;	 		//	将该顶点入队 
    
    	while(front != rear)	//	若front == rear,表明这个顶点在边链表上连接的顶点已经遍历完毕 
    	{
    		front = (front+1)%MAXSIZE;		//	出队 
    	
    		v = Queue[front];			//	得到此时遍历到顶点坐标 
    		
    		P = S->List[v].FirstNode;	//	遍历当前顶点指向边链表中连接的其他顶点
    									//	也就是换个顶点的边链表继续遍历查找剩余顶点 
    		while(P!=NULL)
    		{
    			
    			if(BfsVist[P->Local] == 0)
    			{			
    				printf("%d ",P->Local+1);	//	输出连接边顶点 
    				
    				BfsVist[P->Local] = 1;		//	作标记,表示这个顶点已经搜索过 
    				
    				rear = (rear+1)%MAXSIZE;		//	将该下标入队 
    				
    				Queue[rear] = P->Local;	//	把遍历到新的边链表对应的顶点坐标入队 
    			}
    			
    			P = P->next;	//	遍历这个顶点的边链表 
    		}	
    	} 
    } 
    
    //	BFS广度遍历初始化
    void Init_BFS(MyGraph *S)
    {
    	int i;
    	
    	for(i=0;i<S->Vnum;i++)
    	{
    		BfsVist[i] = 0;	//	初始化标记符 
    	}
    	
    	for(i=0;i<S->Vnum;i++)
    	{
    		if(BfsVist[i]==0)
    			BFS(S,i);
    	}
    	
    } 
    

    (6)全部代码

    #include<stdio.h>
    #include<stdlib.h>
    
    #define MAXSIZE 100
    
    //深度遍历标记数组 
    int DfsVist[MAXSIZE]; 
    //广度遍历标记数组 
    int BfsVist[MAXSIZE];
    
    //	边链表 
    typedef struct EdgeLink{
    	
    	int Local;					//	存放该顶点对应边链表中数据 						 
    	
    	struct EdgeLink *next;		//	边链表节点指针  
    	
    }Edge,*ELINK;
    
    //	顶点表 
    typedef struct VertexLink{
    	
    	int Vertex;					//	存放一条边链表对应的顶点 
    	ELINK FirstNode;			//	指向该顶点对应边链表的头节点 
    	
    }Vertex[MAXSIZE],*VLINK;
    
    //	存放顶点和边,指向顶点表结构体数组 
    typedef struct MyGraph{
    	
    	int Vnum;	//	存放顶点数 
    	int Enum;	//	存放边数 
    	
    	Vertex List;	//	边链表对应的顶点表中顶点结构体 
    	
    }MyGraph;
    
    //	创建边链表
    void CreateLink(MyGraph *T)
    {
    	int i,j;
    	int v1,v2;
    	ELINK p;		//	边链表指针 
    	ELINK q;
    	
    	printf("请输入顶点数和边数(空格隔开):\n");
    	
    	scanf("%d%d",&(T->Vnum),&(T->Enum));
    	
    	
    	//	初始化顶点表结构体数组 
    	for(i=0;i<T->Vnum;i++)
    	{
    		printf("请输入第%d个顶点的信息:\n",i+1);
    		
    		scanf("%d",&(T->List[i].Vertex));		//	存放顶点在顶点表中 
    		
    		T->List[i].FirstNode = NULL; 		//	让每个顶点表第一个指向边链表的指针为NULL 
    	}
    	
    	//	打印顶点坐标和顶点表中顶点数据 
    	printf("---------------------------\n"); 
    	for(i=0;i<T->Vnum;i++)
    	{
    		printf("顶点下标为:%d   顶点数据为: %d\n",i,T->List[i].Vertex); 	
    	}
    	printf("---------------------------\n");
    	
    	//	插入边链表数据	
    	for(i=0;i<T->Enum;i++)
    	{
    		//	因为顶点表为顺序表,所以要按顶点顺序输入相连边 
    		printf("请输入两个连接顶点下标(空格隔开):\n");
    		
    		scanf("%d%d",&v1,&v2);
    		getchar(); 
    		
    		q = (ELINK)malloc(sizeof(Edge));	//	创建边链表节点,分配内存 
    				
    		q->Local = v2;	//	记录与该顶点连接边的顶点坐标
    				
    		q->next = NULL;						//	让尾巴指向NULL 
    				
    		if(!T->List[v1].FirstNode){	//	判断是否为这个顶点第一个指向的数据 
    					
    			T->List[v1].FirstNode = q;
    					
    		}else{
    				//	这个顶点已经指向了一条边,以这条边为头节点,尾插法 
    			p = T->List[v1].FirstNode;	//	临时存放头节点 
    			while(p->next)	//	让节点指针遍历到尾巴上 
    			{
    				p = p->next;
    			}
    			p->next = q;	//	让新插的节点连接到之前边节点的尾巴上 
    		}
    			
    		q = (ELINK)malloc(sizeof(Edge));	//	创建边链表节点,分配内存 
    				
    		q->Local = v1;	//	记录与该顶点连接边的顶点坐标
    			
    		q->next = NULL;						//	让尾巴指向NULL 
    				
    		if(!T->List[v2].FirstNode){	//	判断是否为这个顶点第一个指向的数据 
    					
    			T->List[v2].FirstNode = q;
    					
    		}else{
    					//	这个顶点已经指向了一条边,以这条边为头节点,尾插法 
    			p = T->List[v2].FirstNode;	//	临时存放头节点 
    			while(p->next)	//	让节点指针遍历到尾巴上 
    			{
    				p = p->next;
    			}
    			p->next = q;	//	让新插的节点连接到之前边节点的尾巴上 
    		}
    			
    	} 
    	
    }
    
    //	打印邻接表 
    void PrintLink(MyGraph *S) 
    {
    	MyGraph *T = S;
    	ELINK Q;			//	防止边链表指针指到NULL ,用临时指针代替遍历打印 
    		
    	int i;
    	printf("打印邻接表结果如下:\n");
    	for(i=0;i<T->Vnum;i++)
    	{
    		Q = T->List[i].FirstNode;	//	接受每个顶点指向对应边链表的头节点指针 
    		printf("%d--->",i);
    		
    		while(1)
    		{
    			if(Q == NULL)
    			{
    				putchar('\n');
    				break;
    			}
    			printf("------->%3d",Q->Local);
    			
    			Q = Q->next;	//!!BUG 
    		}
    	}
    	putchar('\n');
    }
    
    //*****************	深度优先遍历算法—邻接表 *****************//
    void DFS_Link(MyGraph *T,int n)
    {	
    	int i,j;
    	ELINK q;	//	指向边链表节点指针 
    	
    	if(n<0 || n>=T->Vnum)
    	{
    		printf("输入有误\n");
    		return;	
    	}
    		DfsVist[n] = 1;		//	遍历一个顶点,做下标记 1  
    
    		printf(" %d",T->List[n].Vertex);
    		
    		q = T->List[n].FirstNode;	//q指向下标为i所对顶点 对应的边链表的第一个边结点	
    		
    		while(q!=NULL)	
    		{	
    			if(DfsVist[q->Local]!=1)
    			{
    			
    				j = q->Local;
    				DFS_Link(T,j);
    			} 
    			
    			q = q->next;
    		}
    	
    	
    	 
    } 
    //	初始化深度遍历—邻接表 
    void Init_DFSLINK(MyGraph *Q)
    {
    	int i;
    	for(i=0;i<Q->Vnum;i++)
    	{
    		DfsVist[i] = 0;
    	}
    		
    	for(i=0;i<Q->Vnum;i++)
    	{
    		if(!DfsVist[i])
    		{
    		 DFS_Link(Q,i);	//	此顶点没有被标记,开始递归遍历
    		}
    	}
    	putchar('\n'); 
    	
    }
    
    
    //	广度遍历 
    void BFS(MyGraph *S,int t)
    {
    	ELINK P; 			//	指向顶点所对应的边链表中 
    	
    	int i;
    	int v;		//	用来接收边链表对应的顶点
    	
    	//	为了不和广度搜素—邻接矩阵冲突
    	//	创建一个数组队列 
    	int Queue[MAXSIZE];
    	int front = 0;			//	队头 
    	int rear = 0;			//	队尾 
    		
    	printf("%d ",S->List[t].Vertex);	//	输出当前遍历边链表的顶点 
    	BfsVist[t] = 1;		//	将该顶点作标记
    	
    	rear = (rear+1)%MAXSIZE;	//	入队一个让队尾指向后移一位
    	Queue[rear] = t;	 		//	将该顶点入队 
    
    	while(front != rear)	//	若front == rear,表明这个顶点在边链表上连接的顶点已经遍历完毕 
    	{
    		front = (front+1)%MAXSIZE;		//	出队 
    	
    		v = Queue[front];			//	得到此时遍历到顶点坐标 
    		
    		P = S->List[v].FirstNode;	//	遍历当前顶点指向边链表中连接的其他顶点
    									//	也就是换个顶点的边链表继续遍历查找剩余顶点 
    		while(P!=NULL)
    		{
    			
    			if(BfsVist[P->Local] == 0)
    			{			
    				printf("%d ",P->Local+1);	//	输出连接边顶点 
    				
    				BfsVist[P->Local] = 1;		//	作标记,表示这个顶点已经搜索过 
    				
    				rear = (rear+1)%MAXSIZE;		//	将该下标入队 
    				
    				Queue[rear] = P->Local;	//	把遍历到新的边链表对应的顶点坐标入队 
    			}
    			
    			P = P->next;	//	遍历这个顶点的边链表 
    		}	
    	} 
    } 
    
    //	BFS广度遍历初始化
    void Init_BFS(MyGraph *S)
    {
    	int i;
    	
    	for(i=0;i<S->Vnum;i++)
    	{
    		BfsVist[i] = 0;	//	初始化标记符 
    	}
    	
    	for(i=0;i<S->Vnum;i++)
    	{
    		if(BfsVist[i]==0)
    			BFS(S,i);
    	}
    	
    } 
    
    int main()
    {
    	MyGraph *S;
    	S = (MyGraph *)malloc(sizeof(MyGraph));
    	
    	//	创建边链表 
    	CreateLink(S);
    	
    	//	打印边链表 
    	PrintLink(S);
    	
    	//	深度遍历
    	Init_DFSLINK(S); 
    	
    	//	广度遍历 
    	Init_BFS(S);
    	 
    	return 0;	
    } 
    
    

    运行结果:
    在这里插入图片描述

    展开全文
  • 无向图邻接表遍历

    2018-12-27 18:19:36
    给出一个无向图的各个点之间的邻接关系,要求采用邻接表对图进行存储,并输出遍历序列。  Input 有多组数据,每组数据第一行有两个整数n和m(0&lt;n,m&lt;100),n表示是有n个点(记为1~n)形成的图,接...
  • C语言建立有向图邻接表及其遍历操作

    千次阅读 多人点赞 2018-12-29 17:27:32
    C语言建立有向图邻接表及其遍历操作 1 /*C语言建立有向图邻接表及其遍历操作*/ 2 #include"stdio.h" 3 #include"stdlib.h" 4 //图的邻接矩阵储存结构 5 typedef char elemtype; 6 #...
  • #include<stdio.h> #include<iostream.h> #define MaxInt 32767 #define MVNum 100 #define OK 1 typedef char VerTexType;...typedef struct ArcNode//边 { int adjvex; ...
  • 邻接表无向图深度、广度遍历,测试通过 基本构建图的邻接表结构以及深度广度遍历 public class ALGraph { AdjList[] vertices; int vexNum; int arcNum; boolean[] visited; public ALGraph(int vexNum,...
  • //用邻接表存储无向图深度优先遍历 #define MaxSize 10 #define inf 0x3f3f3f int n,m; //顶点数 边数 bool book[MaxSize]; //标记数组 queue<int>q; //边 struct ArcNode{ int data; ArcNode *next; }...
  • 邻接表的方式建立一个无向图,并且对图进行深度优先遍历和广度优先遍历 1.无向图的建立 需要两种节点: 头结点,表结点 2.深度优先遍历dfs 是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽...
  • 无向图邻接表构建和两种遍历,存储表示,邻接表的创建,深度优先和广度优先遍历
  • 无向图邻接表深度优先遍历

    千次阅读 2016-11-23 22:45:04
    #include #include #define Max 50 ...//边节点 typedef struct EdgeNode { int adjvex;//储存对应顶点的下标 int weight;//用于储存权值 struct EdgeNode * p;//指向下一个边节点 }EdgeNode;
  • 数据结构 -邻接表-遍历 #include <iostream> #include <fstream> #include <stdlib.h> using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 ...
  • 的链式存储有多种,有邻接表、十字链表和邻接多重表,下面注意说明邻接表邻接表邻接表由两部分组 成:表头结点表和边表。 例: 深度优先遍历: 为了避免同一顶点被访问多次,在遍历图的过程中,必须记下每...
  • C语言实现邻接表表示法创建图及深度遍历邻接表表示法创建图创建无向图存储表示定位顶点位置创建无向图邻接表无向图深度优先遍历深度优先遍历基本操作测试代码整合深度遍历结果创建无向网代码表示深度遍历结果创建有...
  • 采用邻接表表示法创建无向图,并将其顶点表和邻接表进行存盘和读盘处理,最后对该无向图进行深度优先遍历 存盘和读盘的文件路径需根据个人来更改 //算法6.2 采用邻接表表示法创建无向图 #include <iostream>...
  • int creatadj(algraph &gra)//用邻接表存储 {  int i,n,m;  char cha;  cout输如结点个数:";  cin>>n;  cout输如弧个数:";  cin>>m; arcnode *arc,*tem;  for(i=0;i;i++)  {  cout输如结点信息:";  ...
  • 无向图邻接表深度优先遍历(DFS)

    千次阅读 2011-11-15 10:05:18
    邻接表的一种链式存储结构。对图的每个顶点建立一个单链表(n个顶点建立n个单链表)   头文件:Graph.h #ifndef GRAPH_H #define GRAPH_H #define MAXSIZE 50 typedef char VertexType; //顶点数据类型 ...
  • 无向图-邻接链表的深度优先遍历-DFS

    千次阅读 2018-02-20 21:05:27
    一、DFS思想本算法以无向网为例,存储方式采用邻接链表1)将该网以...深度优先遍历图,直到中所有和v有路径相通的顶点都被访问到二、算法复杂度:O(n+e) 邻接矩阵和邻接表都是实现BFS和DFS的方法,邻接矩阵时间...
  • 给定无向图请用邻接矩阵表示法表示该图v4 v4 v5 v3 v2 v1 #include<iostream> #include<string> using namespace std; #define MAX 20 typedef int Adj[MAX][MAX]; typedef struct{ string vexs[MAX]; //顶点 Adj ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,813
精华内容 3,925
关键字:

无向图邻接表的深度遍历