数据结构|图的构建和遍历 c++

1、图的两种构建方式

邻接矩阵（数组）和临接表（链表）

邻接矩阵：dfs 深度搜索：按照一条路一直走到头再找另一条路（），构造辅助数组visited[]；递归算法

邻接表：bfs 广度搜索：看到分叉口就搜索，像二叉树的非递归算法层搜索一样，使用队列，构造辅助数组visited[]；

                                                                          图一  邻接矩阵 

                                                                        图二 邻接表 

                                                                         图三 邻接表说明

2、邻接矩阵代码

1.  
    
2.  
   // 用临接矩阵表示
3.  
   #define maxnum 100 // 最大可存储100个点
4.  
   struct adGraph
5.  
   {
6.  
   char vexs[maxnum]; //顶点表
7.  
   int arcs[maxnum][maxnum]; // 临接表
8.  
   int vexnum; //当前点数
9.  
   int arcnum; // 当前边数；
10.  
    };
11.  
     
12.  
    class Graph //图
13.  
    {
14.  
    public:
15.  
     
16.  
    Graph(int vexnum,int arcnum)
17.  
    {
18.  
    creat_nodir(vexnum, arcnum);
19.  
    initvisted();
20.  
    }
21.  
    void creat_nodir(int vexnum,int arcnum);
22.  
    void creat_dir(int vexnum, int arcnum);
23.  
    void dfs(char ch); //深度遍历查找ch
24.  
    void initvisted(); //初始化visited
25.  
    int findindex(char v);
26.  
     
27.  
     
28.  
    int* visted = new int[this->g.vexnum]; //开辟辅助数组visited
29.  
    adGraph g; //建立图g
30.  
     
31.  
    };
32.  
    void Graph::initvisted()
33.  
    {
34.  
    for (int i = 0; i < this->g.vexnum; i )
35.  
    {
36.  
    visted[i] = 0;//初始化visited
37.  
    }
38.  
    }
39.  
    //1输入总顶点数和总边数；将点的信息存入顶点表；初始化临接矩阵；构造邻接矩阵
40.  
    void Graph::creat_nodir(int vexnum, int arcnum)//无向图
41.  
    {
42.  
    g.vexnum = vexnum; // 总顶点数 总边数
43.  
    g.arcnum = arcnum;
44.  
    char input;
45.  
    for (int i = 0; i < g.vexnum; i ) //给顶点表赋值
46.  
    {
47.  
    cout << "给第" << i 1 << "个顶点赋值:";
48.  
    cin >> input;
49.  
    g.vexs[i] = input;
50.  
    }
51.  
    //初始化邻接矩阵
52.  
    for (int i = 0; i < g.vexnum; i )
53.  
    {
54.  
    for (int j = i; j < g.vexnum; j )
55.  
    {
56.  
    g.arcs[i][j] = 0;
57.  
    g.arcs[j][i] = g.arcs[i][j];
58.  
    }
59.  
    }
60.  
    //构造邻接矩阵
61.  
    int flag = 0;
62.  
    for (int i = 0; i < g.vexnum; i )
63.  
    {
64.  
    for (int j = i; j < g.vexnum; j )
65.  
    {
66.  
    cout << "第" << i 1 << "个顶点与第" << j 1 << "个顶点有无连接？（有请输入1；无输入0）";
67.  
    cin >> flag;
68.  
    g.arcs[i][j] = flag;
69.  
    g.arcs[j][i] = g.arcs[i][j];
70.  
    }
71.  
    }
72.  
    }
73.  
    void Graph::creat_dir(int vexnum, int arcnum) //有向图
74.  
    {
75.  
    g.vexnum = vexnum; // 总顶点数 总边数
76.  
    g.arcnum = arcnum;
77.  
    char input;
78.  
    for (int i = 0; i < g.vexnum; i ) //给顶点表赋值
79.  
    {
80.  
    cout << "给第" << i 1 << "个顶点赋值:";
81.  
    cin >> input;
82.  
    g.vexs[i] = input;
83.  
    }
84.  
    //初始化邻接矩阵
85.  
    for (int i = 0; i < g.vexnum; i )
86.  
    {
87.  
    for (int j = 0; j < g.vexnum; j )
88.  
    {
89.  
    g.arcs[i][j] = 0;
90.  
    }
91.  
    }
92.  
    //构造邻接矩阵
93.  
    int flag = 0;
94.  
    for (int i = 0; i < g.vexnum; i )
95.  
    {
96.  
    for (int j = 0; j < g.vexnum; j )
97.  
    {
98.  
    cout << "第" << i 1 << "个顶点到第" << j 1 << "个顶点有无连接？（有请输入1；无输入0）";
99.  
    cin >> flag;
100.  
     g.arcs[i][j] = flag;
101.  
     }
102.  
     }
103.  
     }
104.  
     int Graph::findindex(char v)
105.  
     {
106.  
     for (int i = 0; i < this->g.vexnum; i )
107.  
     {
108.  
     if (g.vexs[i] == v)
109.  
     {
110.  
     return i;
111.  
     }
112.  
     }
113.  
     return -1;
114.  
     }
115.  
     void Graph::dfs(char ch) // 深度搜索 ，循着一条路走到头
116.  
     {
117.  
     int i = findindex(ch); // 随便选择一个点开始找
118.  
     cout << ch;
119.  
     visted[i] = 1; //辅助数组visited置1，代表已经找到过
120.  
     for (int w = 0; w < g.vexnum; w )
121.  
     {
122.  
     if ((g.arcs[i][w] == 1) && (visted[w] == 0))
123.  
     {
124.  
     dfs(g.vexs[w]);
125.  
     }
126.  
     }
127.  
     }

3、临接表代码

1.  
   #include<queue>
2.  
   #define maxnum 100
3.  
   //顶点类型，临接类型
4.  
    
5.  
   struct arcnode
6.  
   {
7.  
   int index;
8.  
   arcnode* next;
9.  
   };
10.  
    struct vexnode
11.  
    {
12.  
    char data;
13.  
    arcnode* first;
14.  
     
15.  
    };
16.  
     
17.  
    class Graph_link
18.  
    {
19.  
     
20.  
    public:
21.  
    Graph_link(int vexnum, int arcnum)
22.  
    {
23.  
    creat_nodir(vexnum, arcnum);
24.  
    initvisited();
25.  
    }
26.  
    void creat_nodir(int vexnum, int arcnum);
27.  
    int find_index(char v);
28.  
    void bfs(char ch);
29.  
    void initvisited();
30.  
     
31.  
     
32.  
    int vexnum; //当前顶点数目
33.  
    int arcnum;
34.  
    vexnode* vexarr = new vexnode[vexnum]; //开辟空间 数组形式
35.  
    int* visited = new int[vexnum];
36.  
     
37.  
    };
38.  
    void Graph_link::initvisited()
39.  
    {
40.  
    for (int i = 0; i < vexnum; i )
41.  
    {
42.  
    visited[i] = 0;
43.  
    }
44.  
    }
45.  
     
46.  
    int Graph_link::find_index(char v)
47.  
    {
48.  
    for (int i = 0; i < this->vexnum; i )
49.  
    {
50.  
    if (this->vexarr[i].data == v)
51.  
    {
52.  
    return i;
53.  
    }
54.  
    }
55.  
    return -1;
56.  
     
57.  
     
58.  
    }
59.  
    //建立节点，根据边数一根一根建立
60.  
    void Graph_link::creat_nodir(int vexnum, int arcnum) // 点数 边数
61.  
    {
62.  
    this->vexnum = vexnum;
63.  
    this->arcnum = arcnum;
64.  
    char input;
65.  
    //构建顶点表
66.  
    for (int i = 0; i < this->vexnum; i )
67.  
    {
68.  
    cout << "第" << i 1 << "个顶点的值为：";
69.  
    cin >> input;
70.  
    this->vexarr[i].data = input;
71.  
    this->vexarr[i].first = NULL;
72.  
     
73.  
    }
74.  
    //构件边
75.  
    char v1;
76.  
    char v2;
77.  
    for (int k = 0; k < this->arcnum; k )
78.  
    {
79.  
    cout << "第" << k 1 << "条边的两个端点:";
80.  
    cin >> v1 >> v2;
81.  
    int i = find_index(v1);
82.  
    int j = find_index(v2);
83.  
    arcnode* p = new arcnode;
84.  
    p->index = j;
85.  
    p->next = vexarr[i].first;
86.  
    vexarr[i].first = p;
87.  
    arcnode* q = new arcnode;
88.  
    q->index = i;
89.  
    q->next = vexarr[j].first;
90.  
    vexarr[j].first = q;
91.  
    }
92.  
    }
93.  
    void Graph_link::bfs(char ch) //广度优先遍历 无递归 使用队列思想
94.  
    {
95.  
    queue<int> q;
96.  
    int i = find_index(ch); //ch 的位置
97.  
    visited[i] = 1;
98.  
     
99.  
    q.push(i);
100.  
     while (!q.empty())
101.  
     {
102.  
     cout << vexarr[q.front()].data;
103.  
     arcnode* p=vexarr[q.front()].first;
104.  
     while (p != NULL)
105.  
     {
106.  
     int w = p->index;
107.  
     if (visited[w] == 0)
108.  
     {
109.  
     q.push(w);
110.  
     visited[w] = 1;
111.  
     }
112.  
     p = p->next;
113.  
     }
114.  
     q.pop();
115.  
      
116.  
     }
117.  
     }
118.  
      
119.  
      
120.  
     int main()
121.  
     {
122.  
      
123.  
     Graph_link g(8,9);
124.  
     g.bfs('a');
125.  
      
126.  
      
127.  
      
128.  
      
129.  
     system("pause");
130.  
     return 0;
131.  
      
132.  
      
133.  
     }

这篇好文章是转载于：学新通技术网