精华内容
下载资源
问答
  • 无向图邻接表遍历

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

    Problem Description

    给出一个无向图的各个点之间的邻接关系,要求采用邻接表对图进行存储,并输出遍历序列。

     Input

    有多组数据,每组数据第一行有两个整数n和m(0<n,m<100),n表示是有n个点(记为1~n)形成的图,接下来有m行数据,每一行有两个整数(表示点的序号,从1开始),说明这两点之间有一条边,要求采用头插法建立边表。

     Output

    对于每组数据,分别输出从序号为1的点开始的深度和广度优先搜索序列,每个序列分别占一行,每个数之后有一个空格。

    要求在选取下一未被访问的邻接点时,按边表中邻接点的存储顺序进行选取。

     Sample Input

    8 9
    1 2
    1 3
    2 4
    2 5
    3 6
    3 7
    4 5
    4 8
    6 7

     Sample Output

    1 3 7 6 2 5 4 8
    1 3 2 7 6 5 4 8
    #include <iostream>
    #include <stdlib.h>
    #define maxvex 20
    #include<stdio.h>
    using namespace std;
    
    typedef struct {
        int adjvex;
    
    } ArcCell[maxvex][maxvex];
    
    typedef struct {
        ArcCell arc;
        int vertexnum,arcnum;
        char vex[maxvex];
    } MatrixGraph;
    
    struct ArcNode {
        int adjvex;
        ArcNode* next;
    };
    typedef struct Edge {
        char vertex;
        int vex;
        ArcNode *firstedge;
    } EdgeList[maxvex];
    
    typedef struct {
        EdgeList adjlist;
        int vertexnum,arcnum;
    } GraphList;
    
    
    bool visited[maxvex];
    
    void init() {
        for(int i=0; i<maxvex; i++) {
            visited[i]=false;
        }
    
    }
    
    void CreatList(GraphList &G,int n,int e) {
        G.arcnum=e;
        G.vertexnum=n;
        for(int i=0; i<G.vertexnum; i++) {
            //    cin>>G.adjlist[i].vertex;
            G.adjlist[i].firstedge=NULL;
        }
        for(int i=0; i<G.arcnum; i++) {
            int a,b;
            cin>>a>>b;
            a--;
            b--;
            ArcNode* p=new ArcNode;
            p->adjvex=b;
            p->next=G.adjlist[a].firstedge;
            G.adjlist[a].firstedge=p;
            p=new ArcNode;
            p->adjvex=a;
            p->next=G.adjlist[b].firstedge;
            G.adjlist[b].firstedge=p;
        }
    
    }
    
    
    
    
    void DFSTraverse(GraphList g,int v) {
        cout<<(v+1)<<" ";
        visited[v]=true;
    //for(int i=0;i<g.vertexnum;i++){
        ArcNode* p=g.adjlist[v].firstedge;
        while(p) {
            if(!visited[p->adjvex]) DFSTraverse(g,p->adjvex);
            p=p->next;
        }
    
    
    }
    
    void BFSTraverse(GraphList g,int v) {
        int rear=-1;
        int front =-1;
        int Q[maxvex];
        cout<<(v+1)<<" ";
        visited[v]=true;
        Q[++rear]=v;
        while(rear!=front) {
            v=Q[++front];
            ArcNode* p=g.adjlist[v].firstedge;
            while(p) {
                if(!visited[p->adjvex]) {
                    cout<<(p->adjvex+1)<<" ";
                    visited[p->adjvex]=true;
                    Q[++rear]=p->adjvex;
                }
                p=p->next;
            }
        }
    }
    
    
    int main() {
      
        int n,e;
    
        while(cin>>n>>e) {
            GraphList g;
            CreatList(g,n,e);
            init();
            DFSTraverse(g,0);
            cout<<endl;
            init();
            BFSTraverse(g,0);
            cout<<endl;
    
        }
        return 0;
    }
    
    
    
    
    
    

     

    展开全文
  • 主要介绍了Python根据已知邻接矩阵绘制无向图操作,涉及Python使用networkx、matplotlib进行数值运算与图形绘制相关操作技巧,需要的朋友可以参考下
  • 已知邻接表存储一个无向图,设计一个算法来统计度为2的顶点个数</p>
  • 邻接表无向图 C++详解

    千次阅读 2017-03-23 14:02:10
    ...邻接表无向图是指通过邻接表表示的无向图。 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边。 上图右边的矩阵是G1在内

    转载请注明出处:http://www.cnblogs.com/skywang12345/



    邻接表无向图的介绍

    邻接表无向图是指通过邻接表表示的无向图。

    上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边。

    上图右边的矩阵是G1在内存中的邻接表示意图。每一个顶点都包含一条链表,该链表记录了"该顶点的邻接点的序号"。例如,第2个顶点(顶点C)包含的链表所包含的节点的数据分别是"0,1,3";而这"0,1,3"分别对应"A,B,D"的序号,"A,B,D"都是C的邻接点。就是通过这种方式记录图的信息的。

    邻接表无向图的代码说明

    1. 基本定义

    复制代码
    #define MAX 100
    // 邻接表
    class ListUDG
    {
        private: // 内部类
            // 邻接表中表对应的链表的顶点
            class ENode
            {
                public:
                    int ivex;           // 该边所指向的顶点的位置
                    ENode *nextEdge;    // 指向下一条弧的指针
            };
    
            // 邻接表中表的顶点
            class VNode
            {
                public:
                    char data;          // 顶点信息
                    ENode *firstEdge;   // 指向第一条依附该顶点的弧
            };
    
        private: // 私有成员
            int mVexNum;             // 图的顶点的数目
            int mEdgNum;             // 图的边的数目
            VNode mVexs[MAX];
    
        public:
            // 创建邻接表对应的图(自己输入)
            ListUDG();
            // 创建邻接表对应的图(用已提供的数据)
            ListUDG(char vexs[], int vlen, char edges[][2], int elen);
            ~ListUDG();
    
            // 打印邻接表图
            void print();
    
        private:
            // 读取一个输入字符
            char readChar();
            // 返回ch的位置
            int getPosition(char ch);
            // 将node节点链接到list的最后
            void linkLast(ENode *list, ENode *node);
    };
    
    复制代码

    (01) ListUDG是邻接表对应的结构体。 
    mVexNum是顶点数,mEdgNum是边数;mVexs则是保存顶点信息的一维数组。

    (02) VNode是邻接表顶点对应的结构体。 
    data是顶点所包含的数据,而firstEdge是该顶点所包含链表的表头指针。

    (03) ENode是邻接表顶点所包含的链表的节点对应的结构体。 
    ivex是该节点所对应的顶点在vexs中的索引,而nextEdge是指向下一个节点的。

    2. 创建矩阵

    这里介绍提供了两个创建矩阵的方法。一个是用已知数据,另一个则需要用户手动输入数据

    2.1 创建图(用已提供的矩阵)

    复制代码
    /*
     * 创建邻接表对应的图(用已提供的数据)
     */
    ListUDG::ListUDG(char vexs[], int vlen, char edges[][2], int elen)
    {
        char c1, c2;
        int i, p1, p2;
        ENode *node1, *node2;
    
        // 初始化"顶点数"和"边数"
        mVexNum = vlen;
        mEdgNum = elen;
        // 初始化"邻接表"的顶点
        for(i=0; i<mVexNum; i++)
        {
            mVexs[i].data = vexs[i];
            mVexs[i].firstEdge = NULL;
        }
    
        // 初始化"邻接表"的边
        for(i=0; i<mEdgNum; i++)
        {
            // 读取边的起始顶点和结束顶点
            c1 = edges[i][0];
            c2 = edges[i][1];
    
            p1 = getPosition(c1);
            p2 = getPosition(c2);
            // 初始化node1
            node1 = new ENode();
            node1->ivex = p2;
            // 将node1链接到"p1所在链表的末尾"
            if(mVexs[p1].firstEdge == NULL)
              mVexs[p1].firstEdge = node1;
            else
                linkLast(mVexs[p1].firstEdge, node1);
            // 初始化node2
            node2 = new ENode();
            node2->ivex = p1;
            // 将node2链接到"p2所在链表的末尾"
            if(mVexs[p2].firstEdge == NULL)
              mVexs[p2].firstEdge = node2;
            else
                linkLast(mVexs[p2].firstEdge, node2);
        }
    }
    
    复制代码

    该函数的作用是创建一个邻接表无向图。实际上,该方法创建的无向图,就是上面图G1。调用代码如下:

    复制代码
    char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    char edges[][2] = {
        {'A', 'C'}, 
        {'A', 'D'}, 
        {'A', 'F'}, 
        {'B', 'C'}, 
        {'C', 'D'}, 
        {'E', 'G'}, 
        {'F', 'G'}};
    int vlen = sizeof(vexs)/sizeof(vexs[0]);
    int elen = sizeof(edges)/sizeof(edges[0]);
    ListUDG* pG;
    
    pG = new ListUDG(vexs, vlen, edges, elen);
    
    复制代码

    2.2 创建图(自己输入)

    复制代码
    /*
     * 创建邻接表对应的图(自己输入)
     */
    ListUDG::ListUDG()
    {
        char c1, c2;
        int v, e;
        int i, p1, p2;
        ENode *node1, *node2;
    
        // 输入"顶点数"和"边数"
        cout << "input vertex number: ";
        cin >> mVexNum;
        cout << "input edge number: ";
        cin >> mEdgNum;
        if ( mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum-1))))
        {
            cout << "input error: invalid parameters!" << endl;
            return ;
        }
    
        // 初始化"邻接表"的顶点
        for(i=0; i<mVexNum; i++)
        {
            cout << "vertex(" << i << "): ";
            mVexs[i].data = readChar();
            mVexs[i].firstEdge = NULL;
        }
    
        // 初始化"邻接表"的边
        for(i=0; i<mEdgNum; i++)
        {
            // 读取边的起始顶点和结束顶点
            cout << "edge(" << i << "): ";
            c1 = readChar();
            c2 = readChar();
    
            p1 = getPosition(c1);
            p2 = getPosition(c2);
            // 初始化node1
            node1 = new ENode();
            node1->ivex = p2;
            // 将node1链接到"p1所在链表的末尾"
            if(mVexs[p1].firstEdge == NULL)
              mVexs[p1].firstEdge = node1;
            else
                linkLast(mVexs[p1].firstEdge, node1);
            // 初始化node2
            node2 = new ENode();
            node2->ivex = p1;
            // 将node2链接到"p2所在链表的末尾"
            if(mVexs[p2].firstEdge == NULL)
              mVexs[p2].firstEdge = node2;
            else
                linkLast(mVexs[p2].firstEdge, node2);
        }
    }
    
    复制代码

    该函数是读取用户的输入,将输入的数据转换成对应的无向图。

    邻接表无向图的完整源码

    /**
     * C++: 邻接表表示的"无向图(List Undirected Graph)"
     *
     * @author skywang
     * @date 2014/04/19
     */
    
    #include <iomanip>
    #include <iostream>
    #include <vector>
    using namespace std;
    
    #define MAX 100
    // 邻接表
    class ListUDG
    {
        private: // 内部类
            // 邻接表中表对应的链表的顶点
            class ENode
            {
                public:
                    int ivex;           // 该边所指向的顶点的位置
                    ENode *nextEdge;    // 指向下一条弧的指针
            };
    
            // 邻接表中表的顶点
            class VNode
            {
                public:
                    char data;          // 顶点信息
                    ENode *firstEdge;   // 指向第一条依附该顶点的弧
            };
    
    	private: // 私有成员
            int mVexNum;             // 图的顶点的数目
            int mEdgNum;             // 图的边的数目
            VNode mVexs[MAX];
    
        public:
            // 创建邻接表对应的图(自己输入)
    		ListUDG();
            // 创建邻接表对应的图(用已提供的数据)
            ListUDG(char vexs[], int vlen, char edges[][2], int elen);
    		~ListUDG();
    
            // 打印邻接表图
            void print();
    
    	private:
            // 读取一个输入字符
            char readChar();
            // 返回ch的位置
            int getPosition(char ch);
            // 将node节点链接到list的最后
            void linkLast(ENode *list, ENode *node);
    };
    
    /*
     * 创建邻接表对应的图(自己输入)
     */
    ListUDG::ListUDG()
    {
        char c1, c2;
        int v, e;
        int i, p1, p2;
        ENode *node1, *node2;
    
        // 输入"顶点数"和"边数"
        cout << "input vertex number: ";
        cin >> mVexNum;
        cout << "input edge number: ";
        cin >> mEdgNum;
        if ( mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum-1))))
        {
            cout << "input error: invalid parameters!" << endl;
            return ;
        }
     
        // 初始化"邻接表"的顶点
        for(i=0; i<mVexNum; i++)
        {
            cout << "vertex(" << i << "): ";
            mVexs[i].data = readChar();
            mVexs[i].firstEdge = NULL;
        }
    
        // 初始化"邻接表"的边
        for(i=0; i<mEdgNum; i++)
        {
            // 读取边的起始顶点和结束顶点
            cout << "edge(" << i << "): ";
            c1 = readChar();
            c2 = readChar();
    
            p1 = getPosition(c1);
            p2 = getPosition(c2);
            // 初始化node1
            node1 = new ENode();
            node1->ivex = p2;
            // 将node1链接到"p1所在链表的末尾"
            if(mVexs[p1].firstEdge == NULL)
              mVexs[p1].firstEdge = node1;
            else
                linkLast(mVexs[p1].firstEdge, node1);
            // 初始化node2
            node2 = new ENode();
            node2->ivex = p1;
            // 将node2链接到"p2所在链表的末尾"
            if(mVexs[p2].firstEdge == NULL)
              mVexs[p2].firstEdge = node2;
            else
                linkLast(mVexs[p2].firstEdge, node2);
        }
    }
    
    /*
     * 创建邻接表对应的图(用已提供的数据)
     */
    ListUDG::ListUDG(char vexs[], int vlen, char edges[][2], int elen)
    {
        char c1, c2;
        int i, p1, p2;
        ENode *node1, *node2;
    
        // 初始化"顶点数"和"边数"
        mVexNum = vlen;
        mEdgNum = elen;
        // 初始化"邻接表"的顶点
        for(i=0; i<mVexNum; i++)
        {
            mVexs[i].data = vexs[i];
            mVexs[i].firstEdge = NULL;
        }
    
        // 初始化"邻接表"的边
        for(i=0; i<mEdgNum; i++)
        {
            // 读取边的起始顶点和结束顶点
            c1 = edges[i][0];
            c2 = edges[i][1];
    
            p1 = getPosition(c1);
            p2 = getPosition(c2);
            // 初始化node1
            node1 = new ENode();
            node1->ivex = p2;
            // 将node1链接到"p1所在链表的末尾"
            if(mVexs[p1].firstEdge == NULL)
              mVexs[p1].firstEdge = node1;
            else
                linkLast(mVexs[p1].firstEdge, node1);
            // 初始化node2
            node2 = new ENode();
            node2->ivex = p1;
            // 将node2链接到"p2所在链表的末尾"
            if(mVexs[p2].firstEdge == NULL)
              mVexs[p2].firstEdge = node2;
            else
                linkLast(mVexs[p2].firstEdge, node2);
        }
    }
    
    /* 
     * 析构函数
     */
    ListUDG::~ListUDG() 
    {
    }
    
    /*
     * 将node节点链接到list的最后
     */
    void ListUDG::linkLast(ENode *list, ENode *node)
    {
        ENode *p = list;
    
        while(p->nextEdge)
            p = p->nextEdge;
        p->nextEdge = node;
    }
    
    /*
     * 返回ch的位置
     */
    int ListUDG::getPosition(char ch)
    {
        int i;
        for(i=0; i<mVexNum; i++)
            if(mVexs[i].data==ch)
                return i;
        return -1;
    }
    
    /*
     * 读取一个输入字符
     */
    char ListUDG::readChar()
    {
        char ch;
    
        do {
            cin >> ch;
        } while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
    
        return ch;
    }
    
    /*
     * 打印邻接表图
     */
    void ListUDG::print()
    {
        int i,j;
        ENode *node;
    
        cout << "List Graph:" << endl;
        for (i = 0; i < mVexNum; i++)
        {
            cout << i << "(" << mVexs[i].data << "): ";
            node = mVexs[i].firstEdge;
            while (node != NULL)
            {
                cout << node->ivex << "(" << mVexs[node->ivex].data << ") ";
                node = node->nextEdge;
            }
            cout << endl;
        }
    }
    
    int main()
    {
        char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        char edges[][2] = {
            {'A', 'C'}, 
            {'A', 'D'}, 
            {'A', 'F'}, 
            {'B', 'C'}, 
            {'C', 'D'}, 
            {'E', 'G'}, 
            {'F', 'G'}};
        int vlen = sizeof(vexs)/sizeof(vexs[0]);
        int elen = sizeof(edges)/sizeof(edges[0]);
        ListUDG* pG;
    
        // 自定义"图"(输入矩阵队列)
        //pG = new ListUDG();
        // 采用已有的"图"
        pG = new ListUDG(vexs, vlen, edges, elen);
    
        pG->print();   // 打印图
    
        return 0;
    }


    展开全文
  • 邻接表无向图-- Java

    2016-08-26 17:22:39
    邻接表无向图是指通过邻接表表示的无向图。 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边。 上图右边的矩阵是G1在内存中的...

    邻接表无向图的介绍

    邻接表无向图是指通过邻接表表示的无向图。

    上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边。

    上图右边的矩阵是G1在内存中的邻接表示意图。每一个顶点都包含一条链表,该链表记录了"该顶点的邻接点的序号"。例如,第2个顶点(顶点C)包含的链表所包含的节点的数据分别是"0,1,3";而这"0,1,3"分别对应"A,B,D"的序号,"A,B,D"都是C的邻接点。就是通过这种方式记录图的信息的。

    邻接表无向图的代码说明

    1. 基本定义

    复制代码
    public class ListUDG {
        // 邻接表中表对应的链表的顶点
        private class ENode {
            int ivex;       // 该边所指向的顶点的位置
            ENode nextEdge; // 指向下一条弧的指针
        }
    
        // 邻接表中表的顶点
        private class VNode {
            char data;          // 顶点信息
            ENode firstEdge;    // 指向第一条依附该顶点的弧
        };
    
        private VNode[] mVexs;  // 顶点数组
    
        ...
    }
    
    复制代码

    (01) ListUDG是邻接表对应的结构体。mVexs则是保存顶点信息的一维数组。 
    (02) VNode是邻接表顶点对应的结构体。 data是顶点所包含的数据,而firstEdge是该顶点所包含链表的表头指针。 
    (03) ENode是邻接表顶点所包含的链表的节点对应的结构体。 ivex是该节点所对应的顶点在vexs中的索引,而nextEdge是指向下一个节点的。

    2. 创建矩阵

    这里介绍提供了两个创建矩阵的方法。一个是用已知数据,另一个则需要用户手动输入数据

    2.1 创建图(用已提供的矩阵)

    复制代码
    /*
     * 创建图(用已提供的矩阵)
     *
     * 参数说明:
     *     vexs  -- 顶点数组
     *     edges -- 边数组
     */
    public ListUDG(char[] vexs, char[][] edges) {
    
        // 初始化"顶点数"和"边数"
        int vlen = vexs.length;
        int elen = edges.length;
    
        // 初始化"顶点"
        mVexs = new VNode[vlen];
        for (int i = 0; i < mVexs.length; i++) {
            mVexs[i] = new VNode();
            mVexs[i].data = vexs[i];
            mVexs[i].firstEdge = null;
        }
    
        // 初始化"边"
        for (int i = 0; i < elen; i++) {
            // 读取边的起始顶点和结束顶点
            char c1 = edges[i][0];
            char c2 = edges[i][1];
            // 读取边的起始顶点和结束顶点
            int p1 = getPosition(edges[i][0]);
            int p2 = getPosition(edges[i][1]);
            // 初始化node1
            ENode node1 = new ENode();
            node1.ivex = p2;
            // 将node1链接到"p1所在链表的末尾"
            if(mVexs[p1].firstEdge == null)
              mVexs[p1].firstEdge = node1;
            else
                linkLast(mVexs[p1].firstEdge, node1);
            // 初始化node2
            ENode node2 = new ENode();
            node2.ivex = p1;
            // 将node2链接到"p2所在链表的末尾"
            if(mVexs[p2].firstEdge == null)
              mVexs[p2].firstEdge = node2;
            else
                linkLast(mVexs[p2].firstEdge, node2);
    
        }
    }
    
    复制代码

    该函数的作用是创建一个邻接表无向图。实际上,该方法创建的无向图,就是上面图G1。调用代码如下:

    复制代码
    char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    char[][] edges = new char[][]{
        {'A', 'C'}, 
        {'A', 'D'}, 
        {'A', 'F'}, 
        {'B', 'C'}, 
        {'C', 'D'}, 
        {'E', 'G'}, 
        {'F', 'G'}};
    ListUDG pG;
    
    pG = new ListUDG(vexs, edges);
    
    复制代码

    2.2 创建图(自己输入)

    复制代码
    /* 
     * 创建图(自己输入数据)
     */
    public ListUDG() {
    
        // 输入"顶点数"和"边数"
        System.out.printf("input vertex number: ");
        int vlen = readInt();
        System.out.printf("input edge number: ");
        int elen = readInt();
        if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {
            System.out.printf("input error: invalid parameters!\n");
            return ;
        }
    
        // 初始化"顶点"
        mVexs = new VNode[vlen];
        for (int i = 0; i < mVexs.length; i++) {
            System.out.printf("vertex(%d): ", i);
            mVexs[i] = new VNode();
            mVexs[i].data = readChar();
            mVexs[i].firstEdge = null;
        }
    
        // 初始化"边"
        //mMatrix = new int[vlen][vlen];
        for (int i = 0; i < elen; i++) {
            // 读取边的起始顶点和结束顶点
            System.out.printf("edge(%d):", i);
            char c1 = readChar();
            char c2 = readChar();
            int p1 = getPosition(c1);
            int p2 = getPosition(c2);
            // 初始化node1
            ENode node1 = new ENode();
            node1.ivex = p2;
            // 将node1链接到"p1所在链表的末尾"
            if(mVexs[p1].firstEdge == null)
              mVexs[p1].firstEdge = node1;
            else
                linkLast(mVexs[p1].firstEdge, node1);
            // 初始化node2
            ENode node2 = new ENode();
            node2.ivex = p1;
            // 将node2链接到"p2所在链表的末尾"
            if(mVexs[p2].firstEdge == null)
              mVexs[p2].firstEdge = node2;
            else
                linkLast(mVexs[p2].firstEdge, node2);
        }
    }
    
    复制代码

     

    该函数是读取用户的输入,将输入的数据转换成对应的无向图。

    源码:https://github.com/wangkuiwu/datastructs_and_algorithm/blob/master/source/graph/iterator/udg/java/ListUDG.java

    http://www.cnblogs.com/skywang12345/p/3707612.html

    展开全文
  • 邻接表创建无向图

    2020-12-12 15:22:02
    采用邻接表创建无向图G ,依次输出各顶点的度。 输入格式: 输入第一行中给出2个整数i(0<i≤10),j(j≥0),分别为图G的顶点数和边数。 输入第二行为顶点的信息,每个顶点只能用一个字符表示。 依次输入j行,每行...

    采用邻接表创建无向图G ,依次输出各顶点的度。
    输入格式:
    输入第一行中给出2个整数i(0<i≤10),j(j≥0),分别为图G的顶点数和边数。 输入第二行为顶点的信息,每个顶点只能用一个字符表示。 依次输入j行,每行输入一条边依附的顶点。
    输出格式:
    依次输出各顶点的度,行末没有最后的空格。
    5 7
    ABCDE
    AB
    AD
    BC
    BE
    CD
    CE
    DE

    代码实现如下:

    #include<iostream>
    using namespace std;
    typedef int Status;
    typedef char VerTexType;
    #define MVNum 100   //最大顶点数
    #define OK 1
    typedef struct ArcNode{
    	int adjvex;		//该边所指向的顶点的位置
    	struct ArcNode *nextarc;		//	指向下一条边的指针
    	
    }ArcNode;
    typedef struct VNode{  		//顶点的信息
    	VerTexType data;
    	ArcNode *firstarc;  		//指向第一条依附该顶点的边的指针
    }VNode,AdjList[MVNum];  			//AdjList表示邻接表类型
    typedef struct{   			//邻接表
    	AdjList vertices;
    	int vexnum,arcnum;				//图的当前顶点数和边数
    }ALGraph;
    Status LocateVex(ALGraph G,VerTexType x) 
    //CreateUDG里面用到的查找函数
    {
    	for(int i=0;i<G.vexnum;i++)
         {
             if(G.vertices[i].data== x)
                 return i;
         }
        return -1;
    }
    Status CreateUDG(ALGraph &G)
    {	//采用邻接表表示法,创建无向图
    	int i,j,k;
    	char v1,v2;
    	ArcNode *p1,*p2;
    	cin>>G.vexnum>>G.arcnum;		//输入总的顶点数,总的边数
    	for(i=0;i<G.vexnum;i++)		//输入各个点,构造表头结点表
    	{
    		cin>>G.vertices[i].data;		//输入顶点值
    		G.vertices[i].firstarc=NULL;		//初始化表头结点的指针域为NULL
    	}
    	for(k=0;k<G.arcnum;++k)
    	{
    		cin>>v1>>v2;			//输入一条边依附的两个顶点
    		i=LocateVex(G,v1);
    		j=LocateVex(G,v2);
    		p1=new ArcNode;		//生成一个新的结点*p1
    		p1->adjvex=j;				//邻接点的序号为i
    		p1->nextarc=G.vertices[i].firstarc;
    		G.vertices[i].firstarc=p1;
    		//将新的结点插入顶点v1的边表头部
    		p2=new ArcNode;
    		p2->adjvex=i;
    		p2->nextarc=G.vertices[j].firstarc;
    		G.vertices[j].firstarc=p2;
    		//将新的结点*p2插入顶点vj的边表头部
    	}
    	return OK;
    } 
    void Printf(ALGraph G)			//打印函数,每个顶点关联的边数
    {
    	int cnt,i;
    	ArcNode *p;
    	for(i=0;i<G.vexnum;i++)
    	{
    		cnt=0;
    		p=G.vertices[i].firstarc;
    		while(p!=NULL)
    		{
    			cnt++;
    			p=p->nextarc;
    		}
    		if(i==0)
    		cout<<cnt;
    		else
    		cout<<" "<<cnt;
    	}
    }
    int main()
    {
    	ALGraph G;
    	CreateUDG (G);
    	Printf(G);
        cout<<endl;
    	return 0;
    }
    
    展开全文
  • 已知无向图如图所示,给出它的邻接矩阵 B E / \ / \ A D G \ / \ / C F
  • 邻接表无向图的介绍

    千次阅读 2019-04-22 22:16:41
    邻接表无向图是指通过邻接表表示的无向图。 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边。 上图右边的矩阵是G1在内存中的邻接表示意图。每一个...
  • 实现《算法》无向图邻接表)的部分算法 参考文章:算法☞《图》java实现 图的抽象类实现Graph class; 无向图的实现图的抽象类接口,UndriGraph class; 深度优先搜索类DepthFirstSearch class; 深度优先搜索寻找两...
  • 图的表示(建立)有两种方法: ①邻接矩阵:A(i,j)=1表示i,j存在一条边,空间复杂度O(n^2),稠密图 ...有向图 注意理解头插入节点的过程 int n,m;//n表示城镇个数,m表示道路条数 struct LinkNode//列表
  • 无向图的构建及广度优先遍历---邻接表实现
  • 无向图的表示:邻接矩阵和邻接表

    万次阅读 2015-06-14 06:01:07
    这里将一个无向图邻接表和邻接矩阵表示。 输入:顶底个数n,图中的各个边(用两个顶点表示)。 输出:这个无线图的邻接矩阵和邻接表,其中邻接表中的链接按元素大小升序排列。 先给出一个例子说明。假设有无向...
  • 本章是通过C++实现邻接表无向图。 目录 1. 邻接表无向图的介绍 2. 邻接表无向图的代码说明 3. 邻接表无向图的完整源码 转载请注明出处:http://www.cnblogs.com/skywang12345/ 更多内容:数据结构与算法...
  • 前面分别介绍了邻接表无向图的C和C++实现,本文通过Java实现邻接表无向图。 目录 1. 邻接表无向图的介绍 2. 邻接表无向图的代码说明 3. 邻接表无向图的完整源码 转载请注明出处:...
  • 邻接表无向图 之 Java详解

    千次阅读 2015-08-18 10:43:38
    邻接表无向图的介绍邻接表无向图是指通过邻接表表示的无向图。上面的图G1包含了”A,B,C,D,E,F,G”共7个顶点,而且包含了”(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)”共7条边。上图右边的矩阵是G1在内存中的邻接...
  • 邻接表无向图--- C++

    2016-08-26 16:51:37
    邻接表无向图的介绍 邻接表无向图是指通过邻接表表示的无向图。 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边。 上图右边的...
  • 邻接表无向图---C语言

    2016-08-26 16:06:01
    邻接表无向图是指通过邻接表表示的无向图。 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边。 上图右边的矩阵是G1在内存中的...
  • 一、邻接矩阵无向图 1、基本定义 2、创建矩阵 2.1 创建图(用已提供的矩阵) 2.2 创建图(自己输入...二、邻接表无向图 1、基本定义 2、创建矩阵 2.1 创建图(用已提供的矩阵) 2.2 创建图(自己输入) ...
  • 邻接表无向图

    2013-05-04 21:10:00
    邻接表无向图) 转载于:https://www.cnblogs.com/LoveFishC/archive/2013/05/04/3845866.html
  • 邻接表法创建无向图(C语言)

    千次阅读 多人点赞 2020-06-09 13:24:18
    本题要求建立一个无向图,采用邻接表做为存储结构。 例如: 输入信息为:第一行给出图的顶点数n和边数e。第二行给出n个字符,表示n个顶点的数据元素的值。后面是e行,给出每一条边的两个顶点编号。 输出每个顶点的...
  • #include #include #include #include #define MAXVERTEX 10 //最大顶点数 ...typedef struct ArcNode //结点的类型定义 { int adjvex; //边指向的顶点的位置 struct ArcNode *nextarc; //指示下一个与该顶
  • 邻接表无向图是指通过邻接表表示的无向图。 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边。 上图右边的矩阵是G1在内存中的邻接表示意图。每一个...
  • 邻接表无向图(一)之 C语言详解

    千次阅读 2014-05-08 17:20:00
    本章介绍邻接表无向图。在"图的理论基础"中已经对图进行了理论介绍,这里就不再对图的概念进行重复说明了。和以往一样,本文会先给出C语言的实现;后续再分别给出C++和Java版本的实现。实现的语言虽不同,但是原理...
  • 无向图的构建及深度遍历---临接实现
  • 无向图的实现(邻接表) 图的遍历

    千次阅读 2012-07-31 16:08:16
    邻接表实现了一个无向图,在实现时,包含了添加和删除顶点,添加和删除边,size方法(顶点个数),isEmpty方法,广度和深度优先迭代器 1,成员变量,构造方法,数组扩展 private VNode[] VNodes; //将顶点放在...
  • 邻接表无向图之 C语言详解

    千次阅读 2014-12-01 11:42:40
    右边的矩阵是G1在内存中的邻接表示意图。每一个顶点都包含一条链表,该链表记录了"该顶点的邻接点的序号"。例如,第2个顶点(顶点C)包含的链表所包含的节点的数据分别是"0,1,3";而这"0,1,3"分别对应"A,B,D"的

空空如也

空空如也

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

已知无向图的邻接表