精华内容
下载资源
问答
  • 邻接表和邻接矩阵

    千次阅读 2018-09-19 16:20:31
    进入图论的大门(深渊)之前,不会存图可不行,来来来,邻接表和邻接矩阵拿去花

    进入图论的大门(深渊)之前,我们一定要掌握的两种必备手段——邻接表和邻接矩阵,此刻将成为我们的巨大帮手(其实做不来题还是做不来),下面让我们来学习一下,这两种存图方式在计算机中,该如何应用

    1.邻接矩阵:就是一个二维数组,大小为dis[n][n](n为顶点数),其中dis[i][j]表示顶点i到顶点j的距离,可以看出,邻接表的空间复杂度为O(n^2),那怎么存边呢?如下:

    for(int i = 0; i < m; i++)
    {
        cin>>u>>v>>w;
        dis[u][v] = w;
        dis[v][u] = w;    //不是双向图可以把这句注释掉
    }

    以上表示在有m条边的图中,顶点u->v有一条权值为w的边,双向图加上v->u权值也为w

    可以写一个邻接矩阵的初始化:

    #define inf 0x3f3f3f3f
    memset(dis,inf,sizeof dis);    //距离初始化为正无穷
    for(int i = 1; i <= n; i++)    //边从1开始编号,1~n
        dis[i][i] = 0;            //自己到自己的距离为0

    2.邻接表:邻接表是一部分人理解的难点,它的思想是,对每一个顶点,创建一个表,链接其所有出边,如下图: 

     假设存在这样的图:(u v w一组数表示顶点u到顶点v存在一条权值为w的边)

    4 5        //4个顶点,5条边
    1 4 9
    4 3 8
    1 2 5
    2 4 6
    1 3 7

    于是我们可以画一个这样的图(图片来源:啊哈算法):

     

    这是个什么意思呢?这里我们用五个三个数组u[],v[],w[],first[],next[]来记录每一条边的信息,其实邻接表就是记录边的信息啊,所以我们来看看这些数组是什么意思:

    首先我们对所有m条边进行编号,1~m,first[i]用来存顶点i的最后一条出边的编号next[i]用来存编号为i的边的上一条边的编号,u[],v[]是顶点集合,w[]是边权集合,u[i],v[i],w[i]表示第i条边是从顶点v[i] -> 顶点u[i],权值为w[i]的边,其实现在也说不明白,那我们就一步步模拟此过程:

    根据输入的顺序,可以将边编号1~5:

    4 5        //4个顶点,5条边
    1 4 9        //1
    4 3 8        //2
    1 2 5        //3
    2 4 6        //4
    1 3 7        //5

     第一条边存入:u[1] = 1,v[1] = 4,w[1] = 9,next[1] = first[u[1]],(先保存上一条边编号),first[u[1]] = 1;

    第二条边存入:u[2] = 4,v[2] = 3,w[2] = 8,next[2] = first[u[2]],first[u[2]] = 2;

    第三条边存入:u[3] = 1,v[3] = 2,w[3] = 5,next[3] = first[u[3]],first[u[3]] = 3;

    第四条边存入:u[4] = 2,v[4] = 4,w[4] = 6,next[4] = first[u[4]],first[u[4]] = 4;

    第五条边存入:u[5] = 1,v[5] = 3,w[5] = 7,next[5] = first[u[5]],first[u[5]] = 5;

     

    最后解释一下,这么存的妙处在什么地方:

    首先我们说了,first[i]表示顶点u[i]的最后一条出边的编号,注意是编号!那么,对于每一条输入的边,first[u[i]]就是以顶点u[i]为起点的边的编号,那么next[i] = first[u[i]]则表示,对于第i条边,next[i]保存的是以u[i]为起点的上一条边的编号,为何是上一条边?因为注意语句顺序,在next[i] = first[u[i]]执行完立即执行first[u[i]] = i,也就是将上一条输入的边的编号信息从first[]转移到next[]数组上了,first[]就可以存当前边的信息了,这样,我们通过first[]和next[]就可以遍历整个图了,过程如下图:

    比如我们要找顶点1的所有出边,首先找到first[1],然后根据next[first[1]]找到上一条边的编号,再通过next[next[first[1]]找到再上一条边的编号,一直继续搜索下去直到next[1] = -1为止,说明此时已遍历1号顶点所有出边(因为在没插入边的时候,head[1] = -1,而-1的值赋给了next[1],找到-1说明不存在上一条边了)

    是不是很神奇!但是我们这里为了组织边的时候看起来更具有整体性,不用五个数组存边,我们用一个结构体+head[]的形式,其中head[]就是上文的first[],代码如下:

    #define maxn 5250    //最大边数
    #define vertex 505   //最大点数
    
    struct node
    {
        int to,v,next;
    }e[maxn];
    
    int head[vertex+1],cnt;
    
    void init()            //初始化操作
    {
        cnt = 0;
        memset(head,-1,sizeof head);
    }
    
    void addedge(int u,int v,int w)    //加边操作
    {
        e[cnt].to = v;
        e[cnt].v = w;
        e[cnt].next = head[u];
        head[u] = cnt++;
    }
    
    for(int i = 1; i <= vertex; i++)    //遍历所有顶点的所有出边;
    {
        for(int j = head[i]; j != -1; j = e[j].next)    //从head[i],通过不断找next[j],来遍历顶点i的所有出边;
        {
            cout<<i<<" "<<e[j].to<<" "<<e[j].v<<endl;
        }
    }

    看起来很高大上?其实并没有,只是将v[]换成结构体的to成员,w[]换成结构体的v成员,next[]换成结构体的next成员,(结构体数组相当于成员数组的集合嘛),first[]换成head[]而已, 那么有人就要问了,为什么不用u[]呢?因为这样存边在大多情况下,不需要用到u[],具体原因可以具体考虑,当然加上u成员也无妨只是多一点空间开销嘛,比如在Bellman-Ford算法中u成员将会带来很大的便利,还是要看使用情况而定的

     

    当然,还有更直接,更接近于链表形式的邻接表表示法,那就是利用STL中的vector存一个图,这样的邻接表更易理解和使用,但是传说中有些题目可能卡vector而必须用数组模拟的方式写过,目前我还没有遇见这样的题目,但是这里还是介绍一下vector存图的方法(并且建议使用该方法):

    首先明确,vector实质上是一个动态数组的玩意儿,就是不定长数组,根据需要分配空间的意思,关于vector的使用方法,由于篇幅有限,只介绍几个常用的:

    #include<vector>
    using namespace std;
    
    vector<int> a;
    
    a[0];                //直接按下标访问元素(不会检查是否越界)
    a.push_back(3);    //将元素3插入数组最后
    a.pop_back();     //删除数组中最后一个元素
    a.insert(a.begin(),5);        //两个参数,插入位置,插入元素值
    a.erase(a.end());          //一个参数,要删除的位置
    a.empty();        //判断数组是否为空
    a.clear();        //清空数组
    a.size();        //返回数组此刻长度
    a.begin();        //迭代器指针
    a.end();           //迭代器尾指针
    a.cbegin();        //常量头指针
    a.cend();            //常量尾指针
    

    根据邻接表和vector的特性,我只需要将顶点i的出边,都存在一个数组里vector[i],就好了!那么数组vector是什么类型的呢?应该是“边”这种类型,我们可以设一个结构体类型,如下:

    #define maxn 5250    //最大点数;
    
    struct node
    {
        int to,v;    //to代表到哪个顶点,v代表权值
    };
    
    vector<node> e[maxn];    //每个点都有自己的邻接表,vector是一个node类型的数组

    那么怎么插入边呢?

    void addedge(int u,int v,int w)    //u->v = w;
    {
        node tmp;
        tmp.to = v;
        tmp.v = w;
        e[u].push_back(tmp);    //关于顶点u的邻接表
    }

    是不是特别好理解?这样邻接表就建好了,那要怎么遍历一个顶点边的信息呢?

    for(int i = 0; i < e[1].size(); i++)    //遍历1号顶点所有出边
    {
        cout<<1<<e[1][i].to<<e[1][i].v<<endl;
    }
    //输出应该会是(根据上图):
    1 4 9
    1 2 5
    1 3 7

    将完整的模块拼在一起就是:

    #define n 5250    //最大点数;
    #include<vector>
    using namespace std;
    
    struct node
    {
        int to,v;    //to代表到哪个顶点,v代表权值
    };
    
    vector<node> e[n+1];    //每个点都有自己的邻接表,vector是一个node类型的数组
    
    void init()
    {
        for(int i = 0; i <= n; i++)
            e[i].clear();
    }
    
    void addedge(int u,int v,int w)    //u->v = w,加边
    {
        node tmp;
        tmp.to = v;
        tmp.v = w;
        e[u].push_back(tmp);    //关于顶点u的邻接表
    }
    
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < e[i].size(); j++)    //遍历i号顶点所有出边
        {
            cout<<i<<e[i][j].to<<e[i][j].v<<endl;    //顶点i的第j条出边
        }
    }
    
    //根据上图,输出应该是:
    1 4 9
    1 2 5
    1 3 7
    2 4 6
    4 3 8

    当然,只有两个成员的结构体,我们可以考虑用pair代替(万能的STL啊!),注意make_pair(a,b);的快捷操作:

    #define n 5250    //最大点数;
    #include<vector>
    using namespace std;
    typedef pair<int,int> pir;    //pir.first代表到哪个顶点,pir.second代表权值
    
    vector<pir> e[n+1];    //每个点都有自己的邻接表,vector是一个pair类型的数组
    
    void init()
    {
        for(int i = 0; i <= n; i++)
            e[i].clear();
    }
    
    void addedge(int u,int v,int w)    //u->v = w,加边
    {
        e[u].push_back(make_pair(v,w));    //关于顶点u的邻接表
    }
    
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < e[i].size(); j++)    //遍历i号顶点所有出边
        {
            cout<<i<<e[i][j].to<<e[i][j].v<<endl;    //顶点i的第j条出边
        }
    }
    
    //根据上图,输出应该是:
    1 4 9
    1 2 5
    1 3 7
    2 4 6
    4 3 8

    对了,也许有人要问,为什么是e[i][j]呢?显然e[n]是一个二维数组啊,因为每一个点的出边本身是一个数组啊,不止有一条出边,所以相当于往动态数组里存数组,当然是二维数组了,可以访问e[i][j],表示,顶点i的第j条出边,关于pair,本身没什么好讲的,很简单就不介绍了.

    今天关于存图的方法,就写到这里,相信该是够用了吧

    展开全文
  • 可以用邻接表和邻接矩阵求最短路径 实现图的邻接矩阵和邻接表存储结构; 完成基于邻接矩阵或邻接表的深度优先搜索遍历及广度优先搜索遍历; 实现从键盘输入任意一对顶点,求出顶点间的最短路径。
  • 用什么数据结构存储 (邻接表和邻接矩阵) 图有有两种类型。有向图无向图应该如何表示。 (无向图表示,两点互相有边指向,这样可以统一都用有向图的方式来储存) 储存结构 如果有n个点,m条边的图。他们可以用...

    图的储存

    图的建立有两个问题要解决。

    • 用什么数据结构存储 (邻接表和邻接矩阵)
    • 图有有两种类型。有向图和无向图应该如何表示。 (无向图表示,两点互相有边指向,这样可以统一都用有向图的方式来储存)

    储存结构

    如果有n个点,m条边的图。他们可以用邻接表和邻接矩阵表示。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hKfE5stk-1591067155541)(../../图库/1590206334933.png)]

    邻接矩阵

    g[a][b] 存储边a->b
    
    • 时间复杂度O(n^2)

    邻接表(用数组来模拟链表)

    其实和链式前向星是一回事,如果不明白。可以去看看那个笔记的图。

    • 用数组来模拟链表
    • head[i]表示以i为起点的头节点。也就是第一条边的序号
      • head数据,每个利用头插
    • e[i], ne[i], idx;
      • e[i] 代表边i 指向的节点的序号
      • ne[i] 代表边i 一条“兄弟边”的序号
      • idx 记录边的序号,从0开始

    邻接表的代码

    //邻接表,表示图
    //
    #include <bits/stdc++.h>
    const int N = 1e5 + 10;
    const int M = 1e5+10;
    using namespace std;
    // 对于每个点k,开一个单链表,存储k所有可以走到的点。h[k]存储这个单链表的头结点
    int h[N],e[N],ne[M],idx;
    // 添加一条边a->b
    void add(int a, int b){
        //线的序号从0开始
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;//头插
    }
    
    //遍历以a为首的直接边
    void print(int a ){
        for (int i = h[a]; i != -1 ; i = ne[i]) {
            cout << a << "" << i << endl;
        }
    }
    
    int n,m;//n个点,m个边
    int main(){
        //h初始化为-1
        memset(h,-1,sizeof h);
        cin >> n >> m;
        //加边操作
        while (m --){
            int a, b;
            cin >> a >> b;
            add(a,b);
        }
    
        //遍历以a为首的直接边
        print(1);
        return 0;
    }
    
    展开全文
  • 实现图的邻接表和邻接矩阵 代码: #include&amp;lt;stdlib.h&amp;gt; #include&amp;lt;stdio.h&amp;gt; #include &amp;lt;stdio.h&amp;gt; #include &amp;lt;malloc.h&amp;gt; ...

    在这里插入图片描述

    • 实现图的邻接表和邻接矩阵
    • 代码:
    #include<stdlib.h>
    #include<stdio.h>
    #include <stdio.h>
    #include <malloc.h>
    typedef int InfoType;
    #define	MAXV 100				//最大顶点个数
    #define INF 32767				//INF表示∞
    //以下定义邻接矩阵类型
    typedef struct 
    {  	int no;						//顶点编号
    	InfoType info;				//顶点其他信息
    } VertexType;					//顶点类型
    typedef struct  				//图的定义
    {  	int edges[MAXV][MAXV]; 		//邻接矩阵
       	int n,e;   					//顶点数,边数
    	VertexType vexs[MAXV];		//存放顶点信息
    } MGraph;						//图的邻接矩阵类型
    //以下定义邻接表类型
    typedef struct ANode           	//边的节点结构类型
    {	int adjvex;              	//该边的终点位置
       	struct ANode *nextarc; 		//指向下一条边的指针
       	InfoType info;           	//该边的相关信息,这里用于存放权值
    } ArcNode;
    typedef int Vertex;
    typedef struct Vnode      		//邻接表头节点的类型
    {	Vertex data;            	//顶点信息
        ArcNode *firstarc;     		//指向第一条边
    } VNode;
    typedef VNode AdjList[MAXV];	//AdjList是邻接表类型
    typedef struct 
    {	AdjList adjlist;         	//邻接表
        int n,e;                 	//图中顶点数n和边数e
    } ALGraph;                   	//图的邻接表类型
    
    int visited[MAXV];						//全局数组
    void DFS(ALGraph *G,int v) 
    {
    	ArcNode *p;
    	visited[v]=1;                   	//置已访问标记
    	printf("%3d",v); 					//输出被访问顶点的编号
    	p=G->adjlist[v].firstarc;      		//p指向顶点v的第一条弧的弧头结点
    	while (p!=NULL) 
    	{	
    		if (visited[p->adjvex]!=1)		//若p->adjvex顶点未访问,递归访问它
    			DFS(G,p->adjvex);    
    		p=p->nextarc;              		//p指向顶点v的下一条弧的弧头结点
    	}
    }
    void DFS1(ALGraph *G,int v)   //非递归深度优先算法
    {
    	ArcNode *p;
    	ArcNode *St[MAXV];
    	int top=-1,w,i;
        for (i=0;i<G->n;i++) 
    		visited[i]=0;		//顶点访问标志均置成0
    	printf("%3d",v);        //访问顶点v
    	visited[v]=1;
    	top++;                  //将顶点v的第一个相邻顶点进栈
    	St[top]=G->adjlist[v].firstarc;
    	while (top>-1)          //栈不空循环
    	{
    		p=St[top]; top--;   //出栈一个顶点作为当前顶点
    		while (p!=NULL)     //查找当前顶点的第一个未访问的顶点
    		{
    			w=p->adjvex;
    			if (visited[w]==0)
    			{
    				printf("%3d",w); //访问w
    				visited[w]=1;
    				top++;           //将顶点w的第一个顶点进栈
    				St[top]=G->adjlist[w].firstarc;
    				break;           //退出循环
    			}
    			p=p->nextarc;        //找下一个相邻顶点
    		}
    	}
    	printf("\n");
    }
    
    void BFS(ALGraph *G,int v)  
    {
    	ArcNode *p;
    	int queue[MAXV],front=0,rear=0;			//定义循环队列并初始化
    	int visited[MAXV];            			//定义存放结点的访问标志的数组
    	int w,i;
    	for (i=0;i<G->n;i++) visited[i]=0;		//访问标志数组初始化
    	printf("%3d",v); 						//输出被访问顶点的编号
    	visited[v]=1;              				//置已访问标记
    	rear=(rear+1)%MAXV;
    	queue[rear]=v;             				//v进队
    	while (front!=rear)       				//若队列不空时循环
    	{	
    		front=(front+1)%MAXV;
    		w=queue[front];       				//出队并赋给w
    		p=G->adjlist[w].firstarc; 			//找与顶点w邻接的第一个顶点
    		while (p!=NULL) 
    		{	
    			if (visited[p->adjvex]==0) 		//若当前邻接顶点未被访问
    			{	
    				printf("%3d",p->adjvex);  	//访问相邻顶点
    				visited[p->adjvex]=1;		//置该顶点已被访问的标志
    				rear=(rear+1)%MAXV;			//该顶点进队
    				queue[rear]=p->adjvex; 		
               	}
               	p=p->nextarc;              		//找下一个邻接顶点
    		}
    	}
    	printf("\n");
    }
    
    void MatToList1(MGraph g,ALGraph *&G)
    //将邻接矩阵g转换成邻接表G
    {
    	int i,j;
    	ArcNode *p;
    	G=(ALGraph *)malloc(sizeof(ALGraph));
    	for (i=0;i<g.n;i++)					//给邻接表中所有头节点的指针域置初值
    		G->adjlist[i].firstarc=NULL;
    	for (i=0;i<g.n;i++)					//检查邻接矩阵中每个元素
    		for (j=g.n-1;j>=0;j--)
    			if (g.edges[i][j]!=0 && g.edges[i][j]!=INF)	//存在一条边
    			{   
    			   	p=(ArcNode *)malloc(sizeof(ArcNode));	//创建一个节点*p
    				p->adjvex=j;
    				p->info=g.edges[i][j];
    				p->nextarc=G->adjlist[i].firstarc;		//将*p链到链表后
    				G->adjlist[i].firstarc=p;
    			}
    	G->n=g.n;G->e=g.e;
    }
    
    void DispAdj1(ALGraph *G)
    //输出邻接表G
    {
    	int i;
    	ArcNode *p;
    	for (i=0;i<G->n;i++)
    	{
    		p=G->adjlist[i].firstarc;
    		printf("%3d: ",i);
    		while (p!=NULL)
    		{
    			printf("%3d(%d)",p->adjvex,p->info);
    			p=p->nextarc;
    		}
    		printf("\n");
    	}
    }
    
    void DispMat1(MGraph g)
    //输出邻接矩阵g
    {
    	int i,j;
    	for (i=0;i<g.n;i++)
    	{
    		for (j=0;j<g.n;j++)
    			if (g.edges[i][j]==INF)
    				printf("%3s","∞");
    			else
    				printf("%3d",g.edges[i][j]);
    		printf("\n");
    	}
    }
    
    void ListToMat1(ALGraph *G,MGraph &g)
    //将邻接表G转换成邻接矩阵g
    {
    	int i,j;
    	ArcNode *p;
    	for (i=0;i<G->n;i++)      	//g.edges[i][j]赋初值0
    	   	for (j=0;j<G->n;j++)
    			if (i==j)
    				g.edges[i][j]=0;
    			else
    				g.edges[i][j]=INF;
    	for (i=0;i<G->n;i++) 
    	{	
    		p=G->adjlist[i].firstarc;
    	    while (p!=NULL) 
    		{	
    			g.edges[i][p->adjvex]=p->info;
    		    p=p->nextarc;
    		}
    	}
    	g.n=G->n;g.e=G->e;
    }
    
    void main()
    {
    	int i,j;
    	MGraph g,g1;
    	ALGraph *G;
    	int A[MAXV][6]={
    		{0,5,INF,7,INF,INF},
    		{INF,0,4,INF,INF,INF},
    		{8,INF,0,INF,INF,9},
    		{INF,INF,5,0,INF,6},
    		{INF,INF,INF,5,0,INF},
    		{3,INF,INF,INF,1,0}};
    	g.n=6;g.e=10;			//建立图8.1中有向带标图G的邻接矩阵
    	for (i=0;i<g.n;i++)	
    		for (j=0;j<g.n;j++)
    			g.edges[i][j]=A[i][j];
    	printf("有向图G的邻接矩阵:\n");
    	DispMat1(g);
    	G=(ALGraph *)malloc(sizeof(ALGraph));
    	printf("图G的邻接矩阵转换成邻接表:\n");
    	MatToList1(g,G);
    	DispAdj1(G);
    	printf("图G的邻接表转换成邻接邻阵:\n");
    	ListToMat1(G,g1);
    	DispMat1(g1);
    	system("pause");
    }
    
    
    展开全文
  • 图论是一个很重要的工具,这节主要是图的创建遍历的Java代码,不讲理论,只撸代码,理论网上很多,具体一步步该怎么走,... 图的创建 2.1 图的结构初始化 2.2 邻接矩阵 2.3 邻接表3. 邻接表的两种遍历 3.1 深...

    d9d4740fc0f62c16a76c2504eddceb5a.png
    图论是一个很重要的工具,这节主要是图的创建和遍历的Java代码,不讲理论,只撸代码,理论网上很多,具体一步步该怎么走,其他的贴子也都给全了,但是都是c语言,我们用Java实现和模拟图论。

    内容有点多,给个目录:

    目录:

    1. 图结点的创建

    2. 图的创建

    2.1 图的结构和初始化

    2.2 邻接矩阵

    2.3 邻接表

    3. 邻接表的两种遍历

    3.1 深度优先遍历(邻接表)

    3.1.1 递归算法(邻接表)

    3.1.2 非递归算法(邻接表)

    3.2 广度优先遍历(邻接表)

    4. 邻接矩阵的两种遍历

    4.1 深度优先遍历(邻接矩阵)

    4.1.1 递归算法(邻接矩阵)

    4.1.2 非递归算法(邻接矩阵)

    4.2 广度优先搜索(邻接矩阵)

    5. 项目完整代码

    1. 图结点的创建

    public 

    2. 图的创建

    2.1 图的结构和初始化

    import 

    2.2 邻接矩阵

    // 邻接矩阵创建(有向图)
    

    2.3 邻接表

    // 邻接表创建
    

    3. 邻接表的两种遍历

    flag属性用来标记结点有没有被访问过,所以需要初始化。

    // 初始化访问标记
    

    3.1 深度优先遍历(邻接表)

    3.1.1 递归算法(邻接表)

    // 深度优先遍历(从head结点开始) 递归算法 邻接表
    

    3.1.2 非递归算法(邻接表)

    用到的栈,定义在文章最后完整项目代码中有,这块只是引用。

    // 深度优先遍历(从head结点开始) 非递归算法 邻接表
    

    3.2 广度优先遍历(邻接表)

    因为广度优先遍历需要用到队列,所以不能递归,递归只能是用到栈时才能。

    用到的队列,定义在文章最后完整项目代码中有,这块只是引用。

    void 

    4. 邻接矩阵的两种遍历

    4.1 深度优先遍历(邻接矩阵)

    4.1.1 递归算法(邻接矩阵)

    // 深度优先遍历(从0号结点开始) 递归算法 邻接矩阵
    

    4.1.2 非递归算法(邻接矩阵)

    用到的栈,定义在文章最后完整项目代码中有,这块只是引用。

    // 深度优先遍历(从0号结点开始) 非递归算法 邻接矩阵
    

    4.2 广度优先搜索(邻接矩阵)

    因为广度优先遍历需要用到队列,所以不能递归,递归只能是用到栈时才能。

    用到的队列,定义在文章最后完整项目代码中有,这块只是引用。

    // 广度优先遍历(从0号结点开始) 非递归算法 邻接矩阵
    

    5. 项目完整代码

    项目的代码比较多,主要有下面几个类,防止查找麻烦,目录如下:

    目录:

    1. class Node 结点定义
    2. class Seqqueue 队列定义
    3. class Seqstack 栈的定义
    4. class Graph 图的定义及操作
    5. class Client 测试类

    内容:

    1. //class Node 结点定义
    package 

    2. //class Seqqueue 队列定义

    package 

    3. //class Seqstack 栈的定义

    package 

    4. //class Graph 图的定义及操作

    package 

    5. //class Client 测试类(里面有邻接表和邻接矩阵 的全部操作测试,需要那个,把剩余的注释就行)

    package 
    展开全文
  • 图有两种表示方法,邻接链表和邻接矩阵。  具体使用哪种表示方式更合适与图的属性有关。若是稀疏图(E  邻接链表的表示: struct node { int name; int length; struct node *next; }; typedef node * ...
  • 对比邻接矩阵邻接表 十字链表 邻接多重表   前言 在线性表中,数据元素之间仅有线性关系,每个数据元素只有一个直接前驱一个直接后继; 在树形结构中,数据元素之间有明显的层次关系,并且每一层中的数据...
  • //图,将实现图的两种存储,邻接表和邻接矩阵 //并实现图的创建,深度优先遍历(DFS),递归方法非递归方法,广度优先遍历(BFS) //两种存储方式,在使用深度优先遍历的使用上是一样的 #include&lt;iostream&...
  • 假设图中各边的权值都相等,以邻接矩阵和邻接表为存储结构,分别写出算法:  (1)求顶点vi到顶点vj(i<>j)的最短路径  (2)求源点vi到其余各顶点的最短路径  要求输出路径上的所有顶点(利用BFS遍历的思想)
  • 邻接矩阵#include&lt;iostream&gt; #include&lt;cstring&gt; #include&lt;cstdio&gt; #include&lt;cmath&gt; #include&lt;algorithm&gt; using namespace std; #define ms...
  • 图有两种表示方法,分别是邻接矩阵和邻接表。这里以有向图为例说明。 邻接矩阵 邻接矩阵是一个二维数组A。对于每条边 (u,v),置A[u][v]等于true;否则,数组元素为false。 如果边有一个权,那么可以置A[u][v]等于...
  • 用vector实现邻接矩阵存储图 用vector实现邻接表存储图
  • 这里我们的稀疏图用邻接表来存储会更好一点 稠密图的话用邻接矩阵来存储会更好一点 稠密图的邻接矩阵的实现 #ifndef DENSEGRAPH_MY_H_ #define DENSEGRAPH_MY_H_ #include<iostream> #include<vector> ...
  • 建立图的存储结构 :邻接表 邻接矩阵 const int n0 = 100; const int infinity = 32767; struct arcnode {//边节点  int vertext; //边上另外一个节点的存储位置  int weight; //边的权值  arcnode* ...
  • adt邻接表和邻接矩阵解决问题(数据结构实验)

    千次阅读 热门讨论 2019-11-20 17:24:43
    l 需要分别基于邻接矩阵和邻接表来实现图ADT l 需要实现图的各个基本操作 l 小明最近在学习数据结构中图的相关知识,他需要输出有向图的邻接矩阵并找出有向图中出度最大的点。你能帮他解决这个问题么? 【输入形式】...
  • 图的遍历是什么? 从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次.../*邻接矩阵的dfs*/ bool visited[Maxvex]; memset(visited,false,sizeof(visited));//初始化 void dfs(MGraph G,int i) { cout&
  • 求图的割点的方法我们就不细说了,详情可以百度,这里主要分析一下为什么要用邻接表而不用邻接矩阵来进行求割点 首先我们先来看这两种代码 1.邻接表 #include"iostream" #include"cstdio" #define inf 99999999...
  • 广度优先搜索,类似于一层一层往下(以树数据结构为例) 深度优先搜索,则可以比喻成中序遍历,先处理一条分支,再回过...邻接矩阵就是二维数组 邻接表就是用链表 http://blog.csdn.net/linxinyuluo/article/details
  • 在只使用内置函数lenprint的条件下,实现Python3中对无向图的创建以及遍历,以及邻接表和邻接矩阵的转换,用class来代替C中的structPS: 本文中的图均为无向图,转载需注明作者出处。图的数据结构邻接表构建邻接...
  • 本课程设计主要完成邻接矩阵和邻接表两种不同存储方式的图的建立和遍历,其中遍历部分分别进行了DFS和BFS两种不同形式的遍历。 #include<stdio.h> #include<stdlib.h> #include<string.h> #...
  • //5.2.3 建立图的存储结构 :邻接表 邻接矩阵const int n0 = 100;const int infinity = 32767;struct arcnode{//边节点 int vertext; //边上另外一个节点的存储位置 int weight; //边的权值 arcnode* next; ...
  • 邻接矩阵的基本操作。 */ #include #include #include #define MAXV 50 #define INF 32767 //INF表示∞ typedef int InfoType; typedef int Vertex; using namespace std; //邻接矩阵类型 typedef struct { int...
  • 这是通过邻接矩阵进行DFS#include #include #include #define Max_ver_num 20 using namespace std ; bool visit[Max_ver_num] ;//这个数组的用途是标记 struct HGraph{ string vexs [ Max_ver_num ] ; //放每个...
  • 求最短路,经典的dijkstra算法直接解决了,分别用邻接表和邻接矩阵存图。 邻接矩阵版: #include #include using namespace std; int Map[1005][1005]; int const MAXV=10000; void dijkstra(int...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,922
精华内容 13,568
关键字:

邻接表和邻接矩阵