精华内容
下载资源
问答
  • 邻接矩阵深度优先遍历

    千次阅读 2013-06-27 18:00:09
    void DFSM(MatrixGraph *G,int i) //从第一个结点开始深度遍历图 { int j; G->isTrav[i]=1; //标志该结点已遍历过 printf("%d->",i); for(j=0;j<G->VertexNum;j++) { if(G->Edges[i][j]!=MAXVALUE&&!G->...
    #include<stdio.h>
    #define VERTEX_MAX 26
    #define MAXVALUE 32767
    struct MatrixGraph
    {
    	int Vertex[VERTEX_MAX];                                    //保存顶点信息(序号或字母)
    	int Edges[VERTEX_MAX][VERTEX_MAX];                 //保存边的权
    	int isTrav[VERTEX_MAX];                                     //遍历标志
    	int VertexNum;                                                  //顶点数量
    	int EdgeNum;                                                    //边数量
    	int GraphType;                                                  //图的类型
    };
    
    void DFSM(MatrixGraph *G,int i)                                 //从第一个结点开始深度遍历图
    {
    	int j;
    	G->isTrav[i]=1;                                                  //标志该结点已遍历过
    	printf("%d->",i);
    	for(j=0;j<G->VertexNum;j++)                     
    	{
    		if(G->Edges[i][j]!=MAXVALUE&&!G->isTrav[i])
    			DFSM(G,j);                                                //递归进行遍历
    	}
    }
    void DFSTraverse(MatrixGraph *G)                              //深度优先遍历
    { 
    	int i;
    	for(i=1;i<=G->VertexNum;i++)                                //清除各项顶点遍历标志
    	{     
    		G->isTrav[i]=0;
    	}
    	printf("深度优先遍历结点:");
    	for(i=1;i<=G->VertexNum;i++)
    	{
    		if(!G->isTrav[i])                                           //若该点未遍历
    		{
    			DFSM(G,i);                                               //调用函数遍历
    		}  
    	}
    	printf("\n");
    }
    
    void CreateMatrixGraph(MatrixGraph *G)
    {
    	int i,j,k,weight;
    	int start,end;
    	printf("输入各顶点信息\n");
    	for(i=0;i<G->VertexNum;i++)                                 //输入顶点
    	{
    		printf("\n第%d个顶点",i+1);
    		scanf("%d",&G->Vertex[i]);
    	}
    	printf("输入构成各边的两个顶点及权值\n");
    	for(k=0;k<G->EdgeNum;k++)
    	{
    		printf("第%d条边:",k+1);
    		scanf("%d,%d,%d",&start,&end,&weight);
    		for(i=0;start!=G->Vertex[i];i++);                     //输入边的信息
    			for(j=0;end!=G->Vertex[j];j++);
    				G->Edges[i][j]=weight;
    				if(G->GraphType==0)                           //若是无向图
    				{
    					G->Edges[j][i]=weight;                   //在对角位置保存权值
    				}
    	}
    }
    void OutMatrix(MatrixGraph *G)
    {
    	int i,j;
    	for(j=0;j<G->VertexNum;j++)
    	{
    		printf("\t%d",G->Vertex[j]);                            //在第一行输出顶点信息
    	}
    	printf("\n");
    	for(i=0;i<G->VertexNum;i++)
    	{
    		printf("%d",G->Vertex[i]);
    		for(j=0;j<G->VertexNum;j++)
    		{
    			if(G->Edges[i][j]==MAXVALUE)                    //若权值为最大值
    				printf("\t#");                                      //输出#号
    			else
    				printf("\t%d",G->Edges[i][j]);
    		}
    		printf("\n");
    	}
    }
    int main()
    {
    	MatrixGraph G;
    	int i,j;
    	printf("输入生成图类型(0:无向图,1:有向图):");
    	scanf("%d",&G.GraphType);
    	printf("输入图的顶点数量和各边数量:");
    	scanf("%d,%d",&G.VertexNum,&G.EdgeNum);           //输入图顶点数和边数
    	for(i=0;i<G.VertexNum;i++)
    	     for(j=0;j<G.VertexNum;j++)
    	          G.Edges[i][j]=MAXVALUE;
    	CreateMatrixGraph(&G);
    	printf("邻接矩阵数据如下:\n");
    	OutMatrix(&G);
    	DFSTraverse(&G);
    	printf("图遍历完毕");
    	return 0;
    }

    展开全文
  • Eclipse java工程: 图的深度优先遍历、广度优先遍历 demo:http://download.csdn.net/detail/keen_zuxwang/9875848 import java.util.ArrayList; import java.util.LinkedList; /** * @description 邻接矩阵...

    Eclipse java工程: 图的深度优先遍历、广度优先遍历
    demo:http://download.csdn.net/detail/keen_zuxwang/9875848

    import java.util.ArrayList;
    import java.util.LinkedList;
    /**
    * @description 邻接矩阵模型类
    */
    public class Graph {
    private ArrayList vertexList;//存储点的链表
    private int[][] edges;//邻接矩阵,用来存储边
    private int numOfEdges;//边的数目
    private int n;

    public Graph(int n) {
        //初始化矩阵,一维数组,和边的数目
        this.n = n;
        edges=new int[n][n];
        vertexList=new ArrayList(n);
        numOfEdges=0;
    }
    
    //得到结点的个数
    public int getNumOfVertex() {
        return vertexList.size();
    }
    
    //得到边的数目
    public int getNumOfEdges() {
        return numOfEdges;
    }
    
    //返回结点i的数据
    public Object getValueByIndex(int i) {
        return vertexList.get(i);
    }
    
    //返回v1,v2的权值
    public int getWeight(int v1,int v2) {
        if((v1>=0 && v1<n) && (v2>=0 && v2<n)){
            return edges[v1][v2];
        }else{
            return -1;
        }
    }
    
    //插入结点
    public void insertVertex(Object vertex) {
        vertexList.add(vertexList.size(),vertex);
    }
    
    //插入边
    public void insertEdge(int v1,int v2,int weight) {
        edges[v1][v2]=weight;
        numOfEdges++;
    }
    
    //删除边
    public void deleteEdge(int v1,int v2) {
        edges[v1][v2]=0;
        numOfEdges--;
    }
    
    //得到第一个邻接结点的下标
    public int getFirstNeighbor(int index) {
        for(int j=0;j<vertexList.size();j++) {
            if (edges[index][j]>0) {
                return j;
            }
        }
        return -1;
    }
    
    //根据前一个邻接结点的下标来取得下一个邻接结点
    public int getNextNeighbor(int v1,int v2) {
        for (int j=v2+1;j<vertexList.size();j++) {
            if (edges[v1][j]>0) {
                return j;
            }
        }
        return -1;
    }
    
    public static void main(String args[]) {
        int n=4,e=4;//分别代表结点个数和边的数目
        int i = 0, j;
        int idx;
        String labels[]={"V0","V1","V2","V3"};//结点的标识
        Graph graph=new Graph(n);
    
        for(String label:labels) {
            graph.insertVertex(label);//插入结点
            System.out.print("结点"+i+", 标识"+label+"\n");
            i++;
        }
        System.out.print("\n");
    
        //插入四条边
        graph.insertEdge(0, 1, 2); //v0 v1 边
        graph.insertEdge(0, 2, 5); //v0 v2 边
        graph.insertEdge(0, 3, 1); //v0 v3 边
        graph.insertEdge(2, 3, 8); //v2 v3 边
        graph.insertEdge(3, 0, 7); //v3 v0 边
    
        System.out.println("结点个数是:"+graph.getNumOfVertex());
        System.out.println("边的个数是:"+graph.getNumOfEdges());
    
        System.out.print("\n");
        System.out.print("邻接矩阵 \n");
        for(i=0; i<n; i++){
            for(j=0; j<n; j++){
                System.out.print(graph.edges[i][j]+"  ");
            }
            System.out.print("\n");
        }
        System.out.print("\n");
    
        idx = graph.getFirstNeighbor(0);    
        System.out.print("结点0: 第一个邻接点"+idx+", 权重"+graph.getWeight(0,idx));
        System.out.print("\n");
        if(idx>0){
            idx = graph.getNextNeighbor(0, idx);
            System.out.print("结点0: 第二个邻接点"+idx+", 权重"+graph.getWeight(0,idx));
            System.out.print("\n");
            if(idx>0){
                idx = graph.getNextNeighbor(0, idx);
                System.out.print("结点0: 第三个邻接点"+idx+", 权重"+graph.getWeight(0,idx));
                System.out.print("\n");
    
                if(idx>0){
                    graph.deleteEdge(0, idx);//删除<V0,V3>边
                    System.out.print("删除<V0,V3>边后, ");
                    idx = graph.getNextNeighbor(0, idx);
                    System.out.print("结点0: 第三个邻接点"+idx+", 权重"+graph.getWeight(0,idx)); // -1 表示没有
                    System.out.print("\n");
    
                    System.out.print("\n邻接矩阵\n");
                    for(i=0; i<n; i++){
                        for(j=0; j<n; j++){
                            System.out.print(graph.edges[i][j]+"  ");
                        }
                        System.out.print("\n");
                    }
                    System.out.print("\n");
                }
            }
        }
    
        idx = graph.getFirstNeighbor(1);
        System.out.print("结点1的邻接点"+idx);
        System.out.print("\n");
    
        idx = graph.getFirstNeighbor(2);
        System.out.print("结点2的邻接点"+idx);
        System.out.print("\n");
    
        idx = graph.getFirstNeighbor(3);
        System.out.print("结点3的邻接点"+idx);
        System.out.print("\n");
    }
    

    }

    这里写图片描述

    这里写图片描述

    展开全文
  • 马踏棋盘算法(回溯算法、X*Y图的邻接矩阵深度优先遍历)#include #include <time.h>#define X 8 #define Y 8int chess[X][Y]; //找到基于(x,y)位置的下一个可走的位置 int nextxy(int* x,int* y,int count) { ...

    马踏棋盘算法(回溯算法、X*Y图的邻接矩阵深度优先遍历)

    #include <stdio.h>
    #include <time.h>
    
    #define X 8
    #define Y 8
    
    int chess[X][Y];
    //找到基于(x,y)位置的下一个可走的位置
    int nextxy(int* x,int* y,int count)
    {
        switch(count)
        {
        case 0:
            if(*x+2<=X-1&&*y-1>=0&&chess[*x+2][*y-1]==0)
            {
                *x+=2;
                *y-=1;
                return 1;
            }
            break;
        case 1:
            if(*x+2<=X-1&&*y+1<=Y-1&&chess[*x+2][*y+1]==0)
            {
                *x+=2;
                *y+=1;
                return 1;
            }
            break;
        case 2:
            if(*x+1<=X-1&&*y-2>=0&&chess[*x+1][*y-2]==0)
            {
                *x+=1;
                *y-=2;
                return 1;
            }
            break;
        case 3:
            if(*x+1<=X-1&&*y+2<=Y-1&&chess[*x+1][*y+2]==0)
            {
                *x+=1;
                *y+=2;
                return 1;
            }
            break;
        case 4:
            if(*x-2>=0&&*y-1>=0&&chess[*x-2][*y-1]==0)
            {
                *x-=2;
                *y-=1;
                return 1;
            }
            break;
        case 5:
            if(*x-2>=0&&*y+1<=Y-1&&chess[*x-2][*y+1]==0)
            {
                *x-=2;
                *y+=1;
                return 1;
            }
            break;
        case 6:
            if(*x-1>=0&&*y-2>=0&&chess[*x-1][*y-2]==0)
            {
                *x-=1;
                *y-=2;
                return 1;
            }
            break;
        case 7:
            if(*x-1>=0&&*y+2<=Y-1&&chess[*x-1][*y+2]==0)
            {
                *x-=1;
                *y+=2;
                return 1;
            }
            break;
    
        default:
            break;
        }
        return 0;
    }
    void print()
    {
        int i,j;
        for(i=0;i<X;i++)
        {
            for(j=0;j<Y;j++)
            {
                printf("%2d\t",chess[i][j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    //深度优先遍历棋盘算法
    //(x,y)为位置坐标
    //tag是标记变量,每走一步,tag+1
    int TravelChessBoard(int x,int y,int tag)
    {
        int x1=x,y1=y,flag=0,count=0;
        chess[x][y]=tag;
    
        if(X*Y==tag)
        {
            print();
            //打印棋盘
            return 1;
        }
    
        //找到马的下一个可走的坐标(x1,y1),如果找到flag=1,否则为0
        flag = nextxy(&x1,&y1,count);
        while(0==flag && count <7)
        {
            count++;
            flag = nextxy(&x1,&y1,count);
        }
    
        while(flag)
        {
            if(TravelChessBoard(x1,y1,tag+1))
            {
                return 1;
            }
            //继续找到马的下一个可走的坐标(x1,y1),如果找到flag=1,否则为0
            x1=x;
            y1=y;
            count++;
            flag = nextxy(&x1,&y1,count);
            while(0==flag && count <7)
            {
                count++;
                flag = nextxy(&x1,&y1,count);
            }
        }
        if(0==flag)
        {
            chess[x][y]=0;
        }
        return 0;
    }
    int main()
    {
        int i,j;
        clock_t start,finsh;
        start=clock();
        for(i=0;i<X;i++)
            for(j=0;j<Y;j++)
                {
                    chess[i][j]=0;
                }
        if(!TravelChessBoard(2,0,1))
        {
            printf("抱歉,马踏棋盘失败鸟\n");
        }
        finsh=clock();
        printf("本次计算用时%f秒\n\n",(double)(finsh-start)/CLOCKS_PER_SEC);
        return 0;
    }
    
    展开全文
  • 无向图-邻接矩阵深度优先遍历-DFS

    千次阅读 2018-02-20 21:11:27
    一、算法思想【DFS】本算法以无向网为例,存储方式采用邻接矩阵1)将该...true表示已访问)3)从A的未被访问的邻接点出发,深度优先遍历图,直到图中所有和v有路径相通的顶点都被访问到二、算法复杂度:O(n^2) 存储...

    一、算法思想

    【DFS】

    本算法以无向网为例,存储方式采用邻接矩阵

    1)将该网以邻接矩阵的方式存储,由于这里的示例采用无向图,因此它是一个对称阵
    2)选取A点为起始点,访问此顶点,用一个visit的bool型数组记录访问状态(false表示未被访问,true表示已访问)
    3)从A的未被访问的邻接点出发,深度优先遍历图,直到图中所有和v有路径相通的顶点都被访问到

    二、算法复杂度:O(n^2)

            存储方式采用邻接矩阵,本身是一个二维数组,要查找每个顶点的邻接点都需要访问矩阵中的所有元素,因此需要O(n^2)的时间


    三、算法测试用例

        本算法的测试用例为《大话数据结构》p239中的图7-5-2,如下图所示:


    四、C代码邻接矩阵的DFS实现

    /*******************************************************************************************
    【DFS】
    Author:tmw
    date:2018-2-19
    ********************************************************************************************/
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    
    #define MAX_VERTEX 100
    #define inf 65535  //表示两点之间没有边相连
    
    int visit[MAX_VERTEX];   //标记顶点是否被访问
    
    /**图的邻接矩阵的建立**/
    //邻接矩阵数据结构定义
    typedef struct Martrix_Graph
    {
        char vertex[MAX_VERTEX]; //存储顶点信息
        int edge[MAX_VERTEX][MAX_VERTEX]; //存储边信息
        int vertex_number,edge_number;//存储顶点数和边数
    }Martrix_Graph;
    
    void Create_non_direction_martrix_Graph( Martrix_Graph *G )
    {
        int i,j,k,m;
        printf("请输入构造的无向图的顶点数和边数:\n");
        scanf("%d %d",&G->vertex_number,&G->edge_number);
    
        printf("请输入无向图顶点信息(如ABCDEF....):\n");
        char ch;
        while( ( ch = getchar() != '\n' ) );  //过滤掉前面的\n,防止\n被scanf进去
        for(i=0;i<G->vertex_number;i++)
            scanf("%c",&G->vertex[i]);
    
        //不相连的顶点之间的权值设为inf,包括顶点自身
        //初始化邻接矩阵
        for(i=0;i<G->vertex_number;i++)
            for(j=0;j<G->vertex_number;j++)
                G->edge[i][j] = inf;
    
        //更新无向图边信息
        printf("请输入无向图邻接矩阵相连的边信息,相连标记为1\n");
        for(k=0;k<G->edge_number;k++)
        {
            scanf("%d %d %d",&i,&j,&m);
            G->edge[i][j] = m;
            G->edge[j][i] = G->edge[i][j];//无向图是对称阵
        }
    
    
        //打印邻接矩阵存储信息,检查正确性
        printf("---------------------构造出来的无向图邻接矩阵如下---------------------\n");
        for(i=0;i<G->vertex_number;i++)
        {
            for(j=0;j<G->vertex_number;j++)
                printf("%d\t",G->edge[i][j]);
            printf("\n");
        }
    }
    
    //从当前第i个顶点出发,DFS遍历
    void DFS(Martrix_Graph G, int i)
    {
        int j;
        //标记当前顶点为已访问状态
        visit[i] = true;
        printf("%c ",G.vertex[i]);
    
        //对与该顶点相连的其他未访问顶点进行DFS
        for(j=0;j<G.vertex_number;j++)
        {
            if( G.edge[i][j]==1 && !visit[j] )
                DFS(G,j);
        }
    }
    //对整个图进行DFS
    void DFS_Travel(Martrix_Graph G)
    {
        //初始化visit数组
        int i;
        for(i=0;i<G.vertex_number;i++)
            visit[i] = false;
    
        //整张图的DFS
        printf("对该无向图进行DFS的结果如下:\n");
        for(i=0;i<G.vertex_number;i++)
        {
            if( !visit[i] )
                DFS(G,i);
        }
    }

    五、测试程序及运行结果

    int main()
    {
        printf("测试代码\n");
        Martrix_Graph G;
        Create_non_direction_martrix_Graph(&G);
        DFS_Travel(G);
        return 0;
    }

    运行结果:



    展开全文
  • 邻接矩阵 深度优先遍历 与广度优先

    千次阅读 2018-03-24 17:36:50
    /*图的存储结构 邻接矩阵用一个一维数组 存放图中所有的顶点信息用一个二维数组 存放边的信息 有向图称为弧 无向图称为边*/#include &lt;iostream&gt;#include &lt;vector&gt;#include &lt;...
  • 深度优先遍历其实就是一个递归的过程,其详细过程可以表述为:从图中某个顶点v出发,访问此顶点,然后从v的未被访问的邻接点深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到。(注:此处用文字表述不太...
  • 栈实现的图邻接矩阵深度优先遍历

    千次阅读 2016-10-09 21:40:15
    // 深度优先遍历 void DFS_Traverse(bool adjmatrix[][N], int v0, void (*f)(int)) { bool visited[N] = {true};// v0设为已访问 int stack[N] = {v0};// 栈添加v0 int size = 1; f(v0); while (size
  • 邻接表的深度优先遍历   void DFSTraverse(ALGraph* G) { int i; for (i=0;in;i++) visited[i]=false; for (i=0;in;i++) //确保每一个顶点都遍历过,如果有孤立的也可以
  • /****深度优先 非递归算法***/——————————运行环境 DEV-- C++5.0#includeusing namespace std;const int maxsize=20; templateclass MGraph{ public: MGraph(T a[],int n,int e);//够着函数 
  • 由于比较仓促所以直接以代码的形式来讲解,所用为c++中的模板类。· 首先是此代码中用到的头文件:#include&lt;iostream&gt; #include&...· 因为邻接矩阵的广度优先遍历会用到队列,所以我...
  • 图的邻接表转邻接矩阵深度遍历,自己编写的啦!
  • 邻接矩阵深度优先遍历和广度优先遍历(无向图) #include<stdio.h> #include<stdlib.h> #include<string.h> #include<queue> #include<iostream> using namespace std; #define ...
  • c语言表述数据结构 无向图用邻接矩阵深度优先遍历程序
  • 下面简单实现一个邻接矩阵表示的方法的图,以及遍历的两种方式。 Graph.h #pragma once #define MAX_SIZE 30 templateclass T,class E> class Graph { public: Graph(size_t size); virtual ~
  • 3 强连通图的邻接矩阵存储图; 4 强连通图的深度优先遍历(递归方式实现) 5 强连通图的广度优先遍历(递归+非递归实现) 6 */ 7 #include <stdio.h> 8 #include <string.h> 9 #defin...
  • /*(1)输入一组顶点,建立无向图的邻接矩阵。 进行DFS(深度优先遍历)和BFS(广度优先遍历)。 写出深度优先遍历的递归和非递归算法。*/ #include #define max 40 //最大顶点个数 #define M 10000 //无穷 #...
  • 深度优先遍历连通图 从图中某个顶点v出发,访问v,并置visited[v]的值为true。 依次检查v 的所有邻接点w,如果visited[w]的值为false,再从w出发进行递归遍历,直至图中所有顶点都被访问过。 bool visited[MVNum]...
  • 无向图创建邻接矩阵、深度优先遍历和广度优先遍历一、概念解析:(1)无向图:(2)邻接矩阵:二、创建邻接矩阵:三、深度遍历、广度遍历(1)深度遍历概念:(2)广度遍历概念:四、实例展示 一、概念解析: (1)...
  • 邻接矩阵深度遍历和广度遍历 图的定义 #ifndef G_H #include<iostream> using namespace std; #define OK 1 #define ERROR -1 #define MaxInt 32767 #define MVNum 100 typedef int Status; typedef char ...
  • void ShowAdjMat(Mgraph G) //邻接矩阵的显示 { int i,j; printf("The adjacent matrix is:\n"); for(i=0;i;i++) { for(j=0;j;j++) { printf("%d ",G.arcs[i][j].adj); } printf("\n"); } ...
  • (2)设计并实现一个算法,应用递归的程序设计方法,对一个已存在的图进行深度优先遍历(DFS),并输出遍历的顶点线性序列。遍历的起点通过输入指定。注意:遍历时,仅从该点出发遍历整个图,如果图不连通,则只
  • #include<iostream> const int MAX_VERTEX = 10; using namespace std; int visitd[MAX_VERTEX] = {0};//设置标志变量,并且初始化 0 ...//定义邻接矩阵 int vertexNum,arcNum;//定义顶点个数,和边
  • C++实现,数据结构,图的邻接矩阵表示,深度优先遍历,广度优先遍历,DFS,BFS,为什么要五十个字才能上传啊
  • /*(1)输入一组顶点,建立无向图的邻接矩阵。 进行DFS(深度优先遍历)和BFS(广度优先遍历)。 写出深度优先遍历的递归和非递归算法。*/ #include #define max 40 //最大顶点个数 #define M 10000 //无穷 #...
  • 设计算法输无向图邻接矩阵, 并利用邻接矩阵作为存储结构实现无向图的深度优先遍历; 2.实现无向图邻接表的创建;设计算法输无向图邻接表,并利用邻接表作为存储结构实现无向图的广度优先遍历; #include <stdio.h...
  • 邻接表一样,依葫芦画瓢。#include &lt;bits/stdc++.h&gt; using namespace std; #define MAXSIZE 100 int v[MAXSIZE]; int m[MAXSIZE][MAXSIZE]; int n,e; void Init() { int a,b; for(int i=1;i&...
  • 以下是用邻接矩阵存储表示,实现图的深度优先遍历的示例。 用于遍历的有向图如下: //递归实现 #include #define MaxVertexNum 6 using namespace std; //抽象数据类型 typedef char vertextype;//顶点类型 ...
  • 数据结构——图的邻接矩阵遍历

空空如也

空空如也

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

邻接矩阵深度优先遍历