精华内容
下载资源
问答
  • 无向图邻接表的存储结构

    千次阅读 2011-06-16 11:20:00
     printf("/n图的邻接表结构为:/n");  for(i=0;i,i++)  {  printf("i=%d,i");  v1=graph[i].vertex;  printf("Vertex:%d",v1);  p=graph[i].firstarc;  while(p!=NULL)  {  v2=p->adjvertex ;  printf("-...

    #define maxnode 30
    #include <stdio.h>
    typedef int elemtype
    typedef struct arc
    {
     int adjvertex;
     struct arc *nextarc;
    }arctype;
    typedef struct{
     elemtype vertex;
     arctype *fistarc;
    }vertextype;
    typedef vertextype adjlisttype[maxnode];
    main()
    {
     int i,j,n,e,k;
     int v1,v2;
     arctype *p,*q;
     adjlisttype graph;
     printf("/n输入图中顶点的个数n和边数e:/n");
     scanf("%d%d",&n,&e);
     printf("/n输入图中顶点的数据:/n");
     for(k=0;k<n;k++)
     {
      scanf("%d",&graph[k].vertex);
      graph[k].firstarc=NULL;
     }
     printf("/n输入图中的各边,次序为弧尾编号,弧头编号:/n")
      for(k=0;k<e;k++)
      {
       scanf("%d%d",&v1,&v2);
       i=locvertex(graph,v1);
       i=locvertex(graph,v2);
       q=(arctype*)malloc(sizeof(arctype));
       q->adjvertex=j;
       q->nextarc=graph[i].firstarc;
       graph[i].firstarc=q;
       p=(arctype*)malloc(sizeof(arctype));
       p->adjvertex =i;
       p->nextarc =graph[j].firstarc;
       graph[j].firstarc=p;
      }
      printf("/n图的邻接表结构为:/n");
      for(i=0;i<n,i++)
      {
       printf("i=%d,i");
       v1=graph[i].vertex;
       printf("Vertex:%d",v1);
       p=graph[i].firstarc;
       while(p!=NULL)
       {
        v2=p->adjvertex ;
        printf("-->%d",v2);
        p=p->nextarc ;
       }
       printf("/n");
      }
    }
    int LocVertex(adjlisttype graph,int v)
    {
     int k;
     for(k=0;k<maxnode;k++)
     {
      if(graph[k].vertex==v)
       ruturn(k);
     }
    }

    展开全文
  • //创建图 link_Node为节点链表,其结点第二个值为空 link_weight为权值链表 bool ShortPath_Dijkatral(VexType v,int distance[]); bool Less(ArcType x,ArcType y); bool Less(ArcType x,ArcType y,ArcType ...

    展开全文
  • 建立图邻接矩阵或邻接表存储结构并以邻接矩阵或邻接表存储结构实现图深度优先或广度优先遍历算法。 算法思想: 创建一个邻接矩阵储存结构,vertex数组代表顶点向量集,arc二维数组储存邻接矩阵弧权值,...

    实验目的
    掌握图的结构特征,以及邻接矩阵和邻接表存储结构的特点和建立方法;掌握在邻接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法的设计方法。
    实验条件:计算机一台,vc++6.0
    实验内容与算法思想:
    内容:
    建立图的邻接矩阵或邻接表存储结构并以邻接矩阵或邻接表为存储结构实现图的深度优先或广度优先遍历算法。
    算法思想
    创建一个邻接矩阵的储存结构,vertex数组代表顶点向量集,arc二维数组储存邻接矩阵弧的权值,创建vexnum和arcnum整型变量代表顶点数和弧数。用邻接矩阵表示法创建无向图,CreateDN函数中,将顶点数、弧数和顶点名称储存进一维数组,通过一个for循环输入弧两边的顶点,再通过LocateVertex函数得出顶点的在二维数组邻接矩阵的位置,其值赋予1,表示两个顶点互相连接组成一个弧,设置一个访问数组visited,首先实现对v0所在连通子图的深度优先搜索,访问出发点v0,依次以v0未被访问的作为邻接点出发点,深度优先搜索图,直至图中所有与v0有路径相通的顶点都被访问。若非连通图,则图中一定还有顶点未被访问,需要从图中的另一个未被访问的顶点作为起始点,重复上述深度优先搜索过程,直至图中所有的顶点均被访问为止。
    运行结果:
    在这里插入图片描述
    代码实现:

    #include <stdio.h> 
    #include <string.h> 
    #define MaxVertexNum 50  /*最多顶点个数*/  
    #define True  1
    #define False 0
    #define Error -1
    #define OK    1
    typedef enum {DG, DN, UDG, UDN} GraphKind;  /*枚举类型*/
    typedef struct ArcNode {
        int adj;            /*对于无权图,用1或0表示是否相邻;对带权图,则为权值类型*/
        int info;
    } ArcNode;
    
    int visited[MaxVertexNum];  /*访问数组标志*/ 
                                                       
    typedef struct    //图的邻接矩阵存储结构
    {  
     
        char vertex[MaxVertexNum];                 //顶点向量  
     
        ArcNode arcs[MaxVertexNum][MaxVertexNum];     //邻接矩阵  
     
        int vexnum,arcnum;                         //图中当前的顶点数和边数   
        
        GraphKind kind;                            //图的种类 
     
    }AdjMatrix;  
     
    /* 邻接矩阵的建立*/ 
     
    //邻接矩阵表示法创建无向图
    int LocateVertex(AdjMatrix* G, char v)    /*求顶点位置函数*/ 
    {
    	int j = 0, k;
    	for (k = 0; k < G->vexnum; k++)
    		if (G->vertex[k] == v)
    		{
    			j = k;
    			break;
    		}
    	return j;
    }
    
    void CreateDN(AdjMatrix* G)   //创建一个无向图
    {
    	int i, j,k,m,w;
    	char v1, v2;
    	printf("请输入图的顶点数和弧数,用“,”隔开:\n");
    	scanf("%d,%d", &G->vexnum, &G->arcnum);
    	for (i = 0; i < G->vexnum; i++)
    		for (j = 0; j < G->vexnum; j++)
    			G->arcs[i][j].adj = 0;
    	printf("请输入图的各个顶点,以,隔开:\n");
    	for (i = 0; i < G->vexnum; i++)
    	{   getchar();
    		scanf("%c", &G->vertex[i]);
    		} 
        printf("请输入弧两边的顶点,用“,”隔开:\n");
    	for (k = 0; k < G->arcnum; k++)
    	{	
    	    getchar();
    	    printf("请输入第%d条边的两个顶点名称:",k+1); 
    		scanf("%c,%c", &v1, &v2);
    		m = LocateVertex(G, v1);
    		w = LocateVertex(G, v2);
    		G->arcs[w][m].adj = 1;
    		G->arcs[m][w].adj = 1;
    	}
    	printf("打印出用邻接矩阵创建的无向图\n");
    	for (i = 0; i < G->vexnum; i++)
    	{
    		for (j = 0; j < G->vexnum; j++)
    			printf("%d ", G->arcs[i][j].adj);
    		printf("\n");
    	}
    }
    
    /* 深度优先遍历 */ 
    void DepthFirstSearch(AdjMatrix *G,int v0)  
    {  
        int vj;  
       
        printf("%c  ",G->vertex[v0]);   //访问顶点v0  
    
        visited[v0]=True;          
     
        for(vj=0;vj<G->vexnum;vj++)           //依次搜索v0邻接点  
            if(G->arcs[v0][vj].adj==1 && !visited[vj])  
              DepthFirstSearch(G,vj);  
    }  
     
    void TraverseGraph(AdjMatrix *G)  
    {  
     
        int vi;  
     
        for(vi=0;vi<G->vexnum;vi++)  
            visited[vi]=False;     
     
        for(vi=0;vi<G->vexnum;vi++)  
            if(!visited[vi])   
                DepthFirstSearch(G,vi);  
    }  
     
    
    int main()  
    {  
        AdjMatrix G;  
        CreateDN(&G);
        printf("深度优先搜索结果为:");
        printf("\n");  
        TraverseGraph(&G);
         
    }
    
    
    
    
    
    
    
    
    展开全文
  • 这是用邻接链表作存储结构的图类源代码,下面是图类声明部分: struct ArcNode //弧节点结构 { int adjvex; ArcNode *nextarc; }; struct VexNode //顶点结构 { int vexdata; ArcNode *firstarc; }; //邻接...
  • 自行实现图邻接矩阵和邻接表存储结构 邻接矩阵类和邻接表实现及测试函数 功能全 代码易理解 可直接运行
  • 二、邻接表的存储结构(ADJacency List) //邻接表(Adjacency List) //链表中结点的类型 typedef struct ArcNode{ int adjvex; //该弧指向的顶点的位置 struct ArcNode *nextarc; //指向下一个弧结点的指针 ...

    邻接表的存储结构(ADJacency List)

    //邻接表(Adjacency List) 
    //链表中结点的类型 
    typedef struct ArcNode{
    	int adjvex; //该弧指向的顶点的位置 
    	struct ArcNode *nextarc; //指向下一个弧结点的指针
    	InfoType info; //该弧的相关信息的指针 
    }ArcNode;
    //头结点的类型 
    typedef struct VNode{
    	ElemType data; //顶点的信息 
    	ArcNode *firstarc; //指向第一条依附该顶点的弧的指针 
    	int degree; //存放顶点的入度 
    }VNode, AdjList[N+1]; //AdjList[0]可以不存放顶点信息 
    typedef struct {
    	AdjList adjlist; //邻接表 
    	int vexnum, arcnum; //图的顶点数和弧数 
    }ALGraph;
    

    邻接表的方式构造图(无向图)

    //邻接表的方式构造无向图
    int LocateVex_AL(ALGraph G, ElemType v)
    { //找到顶点v在邻接表中的位置
    	int i;
    	for(i = 1; i<=G.vexnum; i++)
    	{
    		if(v == G.adjlist[i].data)
    			return i;
    	}
    	return -1;
    }
    void Create_ALGraph(ALGraph &G)
    {
    	int i, j;
    	ElemType v1, v2;
    	int a1, a2;
    	scanf("%d %d", &G.vexnum, &G.arcnum);//输入顶点数和边数
    	//读入顶点信息,同时将顶点下一个指针初始化为空,入度初始化为零 
    	for(i = 1;i<=G.vexnum; i++)
    	{
    		scanf("%d", &G.adjlist[i]);
    		G.adjlist[i].firstarc = NULL;
    		G.adjlist[i].degree = 0; 
    	}	
    
    	//读入边的信息
    	for(i = 1; i<=G.arcnum; i++)
    	{
    		scanf("%d %d", &v1, &v2);
    		a1 = LocateVex_AL(G, v1);
    		a2 = LocateVex_AL(G, v2);
    		
    		ArcNode * p;
    		p = (ArcNode*)malloc(sizeof(ArcNode)); 
    		p->adjvex = a2;
    		p->nextarc = G.adjlist[a1].firstarc;
    		G.adjlist[a1].firstarc = p;
    		G.adjlist[a2].degree++;
    		//图为无向图,所以弧要做两次插入 
    		ArcNode * q;
    		q = (ArcNode*)malloc(sizeof(ArcNode)); 
    		q->adjvex = a1;
    		q->nextarc = G.adjlist[a2].firstarc;
    		G.adjlist[a2].firstarc = q;
    		G.adjlist[a1].degree++;
    	}
    }
    

    图的遍历

    一、深度优先遍历(Depth_First Search)

    算法思想:
    1.从图中某一个顶点v出发,访问此顶点,然后依次从v的未被访问过的邻接顶点出发深度遍历图,直到图中所有与v连通的顶点都被访问过;
    2.若此时图中还有顶点未被访问(即非连通图),则另选一个未被访问过的顶点起始点,重复此过程,直到所有顶点都被访问过。

    //深度优先搜索
    void DFS(ALGraph G, int visited[], int v)
    {
    	int i;
    	int t;
    	ArcNode *p;
    	p = G.adjlist[v].firstArc;
    	printf("%c ", G.adjlist[v].data);
    	visited[v] = 1;
    	while(p)
    	{
    		if(visited[p->adjvex] == 0)
    			DFS(G, visited, p->adjvex);
    		p = p->nextArc;
    	}
    }
    
    void DFSTravel(ALGraph G)
    {
    	int i;
    	int visited[N]= {0}; //值为1表示该店访问过
    	for(i = 0; i<G.vexnum; i++)
    	{
    		if(visited[i] == 0)
    			DFS(G, visited, i);
    	}
    }
    

    二、广度优先遍历(Broadth_First Search)

    //广度优先搜索,类似于树的层次遍历
    void BFSTravel(ALGraph G)
    {
    	//利用队列
    	int i;
    	int visited[N] = {0};
    	int Q[N];
    	int rear = 0; //队尾指针 
    	int front = 0; //队头指针 
    	int t; //用来接收出队元素 
    	for(i = 0; i<G.vexnum; i++)
    	{
    		if(visited[i] == 0)
    		{
    			printf("%c ", G.adjlist[i].data);
    			visited[i] = 1;
    			Q[rear++] = i;//进队
    			while(rear != front)//队不空 
    			{
    				t = Q[front++];
    				ArcNode *p;
    				p = (ArcNode*)malloc(sizeof(ArcNode));
    				p = G.adjlist[t].firstArc;
    				while(p)
    				{
    					if(visited[p->adjvex]==0)
    					{
    						printf("%c ", G.adjlist[p->adjvex].data);
    						visited[p->adjvex] = 1;
    						Q[rear++] = p->adjvex;
    					}
    					p = p->nextArc;
    				}
    			}
    		}
    	}
    }
    

    图的常见算法

    最小生成树

    • 构造连通网的一棵生成树,使得总的代价最少——最小生成树的问题。
    一、普利姆算法(Prim)

    算法思想:

    1. 定义一个辅助结构数组 closege[n],记录从U 到 V-U 具有最小代价的边。 对每个还没有加入到生成树的顶点vi ∈V-U , 计算:

      closege[i-1].lowcost = Min{ cost(vi , u) | u∈U  }
      closege[i-1].vexs =  { u | 若 cost(vi  , u ) 最小  }
      
    2. 求 closege[k].lowcost 最小的顶点vk+1,并加入到U中,同时把 边( vk+1 , closege[k].vexs )加入到生成树中;

    3. 重复1,2过程。直到 U = V。

    //最小生成树 
    //普利姆算法(Prim) 
    struct {
    	int lowcost; //closedge[i].lowcost表示当前与第i个顶点相连的的权值最小的边
    	int vex; //closedeg[i].vex表示与第i个顶点相连的顶点的位置 
    }closedge[N];
    void MiniTree_Prim(ALGraph G, int v) //从第v个顶点开始
    {
    	int i;
    	int j;
    	int visited[N]={0}; //0表示未访问,1表示已访问 
    	printf("%c\n", G.adjlist[v].data);
    	visited[v] = 1;
    	//初始化closedge
    	for(i = 0; i<=G.vexnum; i++)
    	{
    		closedge[i].lowcost = MAX;
    		closedge[i].vex = v;
    	}
    	ArcNode *p;
    	p = G.adjlist[v].firstArc;
    	while(p)
    	{
    		closedge[p->adjvex].lowcost = p->info;
    		p = p->nextArc;
    		while(p)
    		{
    			closedge[p->adjvex].lowcost = p->info;
    			p = p->nextArc;
    		}
    	}
    	//找出closedge中最小的边,输出并进行更新
    	for(j = 1; j<G.vexnum; j++)
    	{
    		int min = MAX;
    		int t;
    		for(i = 0; i<G.vexnum; i++)
    		{
    			if(closedge[i].lowcost < min && visited[i] == 0)
    			{
    				min = closedge[i].lowcost;
    				t = i;
    			}
    		}
    		printf("%c,%d,%c\n", G.adjlist[t].data,closedge[t].lowcost, G.adjlist[closedge[t].vex].data);
    		visited[t] = 1;
    		
    		//更新 
    		p = G.adjlist[t].firstArc;
    		while(p)
    		{
    			if(closedge[p->adjvex].lowcost>p->info)
    			{
    				closedge[p->adjvex].lowcost = p->info;
    				closedge[p->adjvex].vex = t;
    			}
    			p = p->nextArc;
    		}
    	}
    }
    
    二、克鲁斯卡尔算法(Kruskal)

    算法思想:

    1. 设T=(V,{E})是一个连通图,则令最小生成树的初始状态为只有n个顶点而无边的非连通图 ,即:T=( V,{ } ) 图中每个顶点自成一个连通分量。
    2. 在E中选择代价最小的边。约束条件:若此边依附的顶点落在T的不同连通分量上,将此边加入T中。否则舍去此边另选下一条代价最小的边。
    3. 依次类推,直到T中所有顶点都在同一个连通分量中。

    拓扑排序(Topological Sort),AOV-网

    算法思想:

    • 在有向图中选一个没有前驱的顶点且输出之。
    • 从图中删除此顶点及所有以它为尾的弧。
    • 重复1.2过程,直到所有顶点均已输出,或当前图中不再有无前驱的顶点为止,此种情况表示图中有环。
    //拓扑排序 (Topological Sort)
    void TopologicalSort(ALGraph G)
    {
    	//统计每个顶点的入度
    	//建立栈,存入每个入度为零的顶点
    	//当栈不空,删除入度为零以及以它为尾的弧
    	int i,t;
    	int indegree[N]={0}; //存放入度的数组
    	int S[N];
    	int top = 0;
    	ArcNode *p;
    	int count = 0; //记录输出顶点的个数 
    	for(i = 0; i<G.vexnum; i++) //统计入度 
    	{
    		p = G.adjlist[i].firstArc;
    		while(p)
    		{
    			indegree[p->adjvex]++;
    			p = p->nextArc;
    		}
    	}
    	for(i = 0; i<G.vexnum; i++) //对入度为零的顶点进栈并访问 
    	{
    		if(indegree[i] == 0)
    		{
    			S[top++] = i;
    			count++; 
    			printf("%c,", G.adjlist[i].data);
    		}
    	}
    	
    	while(top != 0) //当栈不空 
    	{
    		t = S[--top];
    		//进行更新
    		p = G.adjlist[t].firstArc;
    		while(p)
    		{
    			indegree[p->adjvex]--;
    			if(indegree[p->adjvex] == 0)
    			{
    				S[top++] = p->adjvex; //进栈的同时标记已访问
    				count++;
    				printf("%c,", G.adjlist[p->adjvex].data);
    			}
    			p = p->nextArc;
    		}
    	}
    	if(count == G.vexnum)
    		printf("\n该图中无回路");
    }
    

    关键路径问题,AOE-网

    • 从开始点到完成点的最长路径的长度.即路径上各活动持续时间之和

    算法思想:

    1. 输入e条弧,建立AOE-网的存储结构;
    2. 从源点V0出发,令ve[0]=0;按拓扑有序求其余各顶点的ve[i];若得到的序列中顶点的个数小于网中的顶点总数,则不能求关键路径,算法终止;否则执行步骤(3);
    3. 从汇点Vn出发,令vL[n-1]=ve[n-1],按逆拓扑有序求其余各顶点的vL[i];
    4. 根据各顶点的ve和vL,求每条弧s的e[s]和L[s],若满足e[s]=L[s],则为关键活动。
    int ve[N] = {0}; //ve[i]表示最早开始时间
    int vl[N] = {0}; //vl[i]表示最晚开始时间
    int T[N],S[N];
    int topS = 0;
    int topT = 0;
    void TopologicalOrder(ALGraph G)
    {
    	int i, t;
    	int indegree[N] = {0}; 
    	ArcNode *p;
    	
    	for(i = 0; i<G.vexnum; i++) //统计入度 
    	{
    		p = G.adjlist[i].firstArc;
    		while(p)
    		{
    			indegree[p->adjvex]++;
    			p = p->nextArc;
    		}
    	}
    	for(i = 0; i<G.vexnum; i++) //对入度为零的顶点进栈 
    	{
    		if(indegree[i] == 0)
    		{
    			S[topS++] = i;
    			T[topT++] = i;
    		}
    	}
    	
    	while(topS != 0) //当栈不空 
    	{
    		t = S[--topS];
    		p = G.adjlist[t].firstArc;
    		while(p) //求出当前最早开始时间,并对入度进行更新 
    		{
    			if(ve[t] + p->info > ve[p->adjvex])
    				ve[p->adjvex] = ve[t]+p->info;
    			indegree[p->adjvex]--;
    			if(indegree[p->adjvex] == 0)
    			{
    				S[topS++] = p->adjvex;
    				T[topT++] = p->adjvex;
    			}
    			p = p->nextArc;
    		}
    	}
    }
    
    void CriticalPath(ALGraph G)
    {
    	int i,t;
    	ArcNode *p;
    	TopologicalOrder(G);
    	t = T[--topT];
    	for(i = 0; i<G.vexnum ;i++)
    	{
    		vl[i] = ve[t];
    	}
    	
    	while(topT != 0)
    	{
    		t = T[--topT];
    		p = G.adjlist[t].firstArc;
    		while(p)
    		{
    			if(vl[p->adjvex]-p->info < vl[t])
    				vl[t] = vl[p->adjvex]-p->info;
    			p = p->nextArc;
    		}
    	}
    	
    	for(i = 0; i<G.vexnum; i++)
    	{
    		if(ve[i] == vl[i])
    			printf("%c,", G.adjlist[i].data);
    	}
    }
    

    最短路径问题

    一、迪杰斯特拉算法(Dijkstra)
    • 目的:求源点到其余各顶点的最短路径

    算法思想:

    1. 1.定义D[i]:表示当前所找到的从源点V0到Vi的最短路径的长度。初态:D[i] = G.arcs[v0][vi] 即弧<v , vi>的权值。
    2. D[j] = Min( D[i] ) (i=1,…., n-1)。显然:Vj 就是从V0出发最早到达的长度最短的顶点。
    3. 下一条最短路径为 D[k] = min(D[k] , D[j]+G.arcs[j][k]);
    4. 同理,求出接下来的每个最短路径。
    //迪杰斯特拉算法(Dijkstra),求v0到各顶点的最短距离 
    void ShortestPath_DIJ(ALGraph G, int v0)
    {
    	//从v0求直接到其他顶点的距离,其中最小的为最短距离
    	//再从该点找直接相连的
    	int i, j, t;
    	int visited[N] = {0};
    	int D[N]; //D[i]表示当前v0到第i个顶点的最短距离 
    	int P[N] = {0}; //P[i]表示v0到第i个顶点最短路径所经过的上一个顶点 
    	ArcNode *p;
    	int min;
    	for(i = 0; i<G.vexnum; i++)
    		D[i] = MAX;
    	
    	p = G.adjlist[v0].firstArc;
    	while(p)
    	{
    		D[p->adjvex] = p->info;
    		P[p->adjvex] = v0;
    		p = p->nextArc;
    	}
    	D[v0] = 0; //v0到v0点的距离为0 
    	for(i = 1; i<G.vexnum; i++)
    	{
    		//找出D[]中的最小值D[t]
    		min = MAX;
    		for(j = 0; j<G.vexnum; j++)
    		{
    			if(D[j] < min && visited[j] == 0)
    			{
    				min = D[j];
    				t = j;
    			}
    		}
    		visited[t] = 1;
    		p = G.adjlist[t].firstArc;
    		while(p)
    		{
    			if(D[t] + p->info < D[p->adjvex] && visited[p->adjvex] == 0)
    			{
    				D[p->adjvex] = D[t] + p->info;
    				P[p->adjvex] = t;
    			}
    			p = p->nextArc;
    		}
    	}
    	
    	for(i = 0; i<G.vexnum; i++)
    	{
    		printf("%d, %d\n",D[i], P[i]);	
    	}
    }
    
    一、弗洛伊德算法(Floyd)
    • 目的:求每一对顶点之间的最短路径
    //弗洛伊德算法(Floyd),求每一对顶点之间的最短距离 
    void ShortestPath_FLOYD(ALGraph G)
    {
    	int i, j, k;
    	int D[N][N]; //D[i][j]表示当前第i个顶点到第j个顶点的最短距离
    	int P[N][N] = {0}; //P[i][j]表示第i个顶点到第j个顶点最短路径所经过的上一个顶点
    	ArcNode *p;
    	//初始化D[][]
    	for(i = 0;i<G.vexnum; i++)
    	{
    		for(j = 0; j<G.vexnum; j++)
    			D[i][j] = MAX;
    	}
    	for(i = 0; i<G.vexnum; i++)
    	{
    		p = G.adjlist[i].firstArc;
    		while(p)
    		{
    			D[i][p->adjvex] = p->info;
    			P[i][p->adjvex] = i;
    			p = p->nextArc;
    		}
    		D[i][i] = 0;
    	}
    	
    	for(i = 0;i<G.vexnum; i++)
    	{
    		for(j = 0; j<G.vexnum; j++)
    		{
    			for(k = 0; k<G.vexnum; k++)
    			{
    				if(D[j][i] + D[i][k] < D[j][k])
    				{
    					D[j][k] = D[j][i] + D[i][k];
    					P[j][k] = i;
    				}
    			}
    		}
    	}
    	for(i = 0;i<G.vexnum; i++)
    	{
    		for(j = 0; j<G.vexnum; j++)
    		{
    			printf("%d, %d\n", D[i][j],P[i][j]);
    		}
    	}
    }
    
    展开全文
  • 题目:以实验3.3所示邻接表为存储结构,编写程序,实现图的深度、宽度优先遍历。 部分代码: 邻接表的单一顶点DFS: //邻接表的单一顶点DFS void DFS(int v,int visited[],LGraph g){ ENode *w; printf("...
  • 程序设计任务: 设计一个程序,实现以邻接表或者邻接矩阵为存储结构,实现连通无向图深度优先和广度优先遍历。基本要求:以邻接表或者邻接矩阵为存储结构,实现连通无向图深度优先和广度优先遍历。以用户指定...
  •   我们知道图的存储结构有邻接矩阵存储方法和邻接表存储方法,而对于邻接矩阵我们已经学习过了,本篇将主要介绍图的邻接表存储结构。 图1-图的邻接表存储结构 1. 邻接表存储有向图 图2-邻接表存储有向图 ...
  • 我们知道,数据之间关系有 3 种,分别是 “一对一”、“一对多” 和 “多对多”,前两种关系数据可分别用线性表和树结构存储,最后一种具有"多对多"逻辑关系数据结构 ——图存储结构 既然大家都来到这看了,...
  • 分别采用邻接矩阵、邻接表存储结构实现图遍历
  • 邻接表存储结构,实现连通无向图深度优先和广度优先遍历。以用户指定结点为起点,分别输出每种遍历下结点访问序列和相应生成树边集。 三、实现提示 设图结点不超过30个,每个结点用一个编号表示(如果...
  • 假设图中各边权值都相等,以邻接矩阵和邻接表存储结构,分别写出算法:  (1)求顶点vi到顶点vj(i<>j)最短路径  (2)求源点vi到其余各顶点最短路径  要求输出路径上所有顶点(利用BFS遍历思想)
  • 邻接表作为存储结构,采用深度优先遍历,输出图所有顶点值 测试数据 输入: 6 6 A B C D E F A B A C B E C E A D D F 输出:BACEDF #include&amp;lt;iostream&amp;gt; using namespace std; #...
  • 存储结构邻接表; 实现功能:广度遍历; 为发布博客代码实现
  • 数据结构void DFS_PostOrder() { top = -1;//栈顶指针初始化 vertexNum=n;//顶点个数 for(i=0;i&lt;vertexNum;i++)//遍历所有顶点,以防遗漏 { if(visited[i]==0)//增设一数组visited记录遍历过...
  • 分别在领接上实现了DFS和BFS,以及在邻接矩阵上面实现了DFS,BFS。 #include<bits/stdc++.h> using namespace std; const int MaxVertexNum=100; typedef int VexType;//节点类型 typedef int EdgeType;//边...
  • 邻接表的存储结构

    2016-08-25 16:12:57
    算法 邻接表 图论
  • 的邻接表存储结构

    2019-09-28 21:50:38
    Define typedef struct Anode { int no;//该节点编号 int weight;//该边信息,如权值 ...//邻接表边类型 即指向结点边 typedef struct Vnode { char info;//头结点信息 注意不是结点编号 ArcNode *firs...
  • 无向图的邻接多重表存储结构

    千次阅读 2014-08-29 21:12:32
    // c7-4.h 无向图的邻接多重表存储结构(见图7.42) #define MAX_VERTEX_NUM 20 enum VisitIf{unvisited,visited}; struct EBox { VisitIf mark; // 访问标记 int ivex,jvex; // 该边依附两个顶点位置 EBox *...
  • 文章目录邻接表1、邻接表表示法2、无向图的邻接表3、有向图的邻接表4、练习5、邻接表的结构类型定义6、采用邻接表表示法创建无向网7、邻接表特点8、邻接矩阵与邻接表表示法的关系十字链表邻接多重表 邻接表 1、邻接...
  • 主要介绍了java实现图的邻接表存储结构的两种方式及实例应用详解,邻接表构建图是必须需要一个Graph对象,也就是图对象!该对象包含属性有:顶点数、边数以及图顶点集合,需要朋友可以参考下
  • 因为之前一篇博客图十字链表存储结构的实现及其遍历是图的邻接表存储结构的延伸,所以这里只是简单谈一下。 邻接表存储结构的定义: #define MaxVex 20 typedef char VertexType ; // 顶点类型 typedef...
  • 无向网图的邻接表存储结构

    千次阅读 2014-12-25 22:10:49
    邻接矩阵的存储结构中,当边比较少的时候,这种结构很浪费存储空间,因此我们考虑用链表来代替二维矩阵存储边的信息,顶点信息还是用一维数组表示。 此时,我们的顶点信息不只是自己的名称等,还要指向自己的第一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,510
精华内容 1,404
关键字:

邻接表的存储结构