`
xinklabi
  • 浏览: 1586681 次
  • 性别: Icon_minigender_1
  • 来自: 吉林
文章分类
社区版块
存档分类
最新评论

图相关内容(存储，遍历，最小生成树，最短路径等)的代码实现（C++和java）

 
阅读更多

一、图的存储结构

 

1.1 邻接矩阵

 

    图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。

 

    设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

 

    

 

    看一个实例，下图左就是一个无向图。

 

    

 

    从上面可以看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角相对应的元全都是相等的。

 

    从这个矩阵中，很容易知道图中的信息。

 

    （1）要判断任意两顶点是否有边无边就很容易了；

 

    （2）要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行或（第i列）的元素之和；

 

    （3）求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点；

 

    而有向图讲究入度和出度，顶点vi的入度为1，正好是第i列各数之和。顶点vi的出度为2，即第i行的各数之和。

 

    若图G是网图，有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

 

    

 

    这里的wij表示(vi,vj)上的权值。无穷大表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。下面左图就是一个有向网图，右图就是它的邻接矩阵。

 

    

 

    那么邻接矩阵是如何实现图的创建的呢？代码如下。

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <stdio.h>
#include <stdlib.h>
#include <curses.h>
 
typedef char VertexType;                //顶点类型应由用户定义
typedef int EdgeType;                   //边上的权值类型应由用户定义
 
#define MAXVEX  100             //最大顶点数，应由用户定义
#define INFINITY    65535               //用65535来代表无穷大
#define DEBUG
 
typedef struct //图的基本数据结构
{
    VertexType vexs[MAXVEX];            //顶点表
    EdgeType   arc[MAXVEX][MAXVEX];         //邻接矩阵，可看作边
    int numVertexes, numEdges;      //图中当前的顶点数和边数
}Graph;
 
//定位
int locates(Graph *g, char ch)
{
    int i = 0;
    for(i = 0; i < g->numVertexes; i++)
    {
        if(g->vexs[i] == ch)
        {
            break;
        }
    }
    if(i >= g->numVertexes)
    {
        return -1;
    }
     
    return i;
}
 
//建立一个无向网图的邻接矩阵表示
void CreateGraph(Graph *g)
{
    int i, j, k, w;
    printf("输入顶点数和边数:\n");
    scanf("%d,%d", &(g->numVertexes), &(g->numEdges));
     
    #ifdef DEBUG
    printf("%d %d\n", g->numVertexes, g->numEdges);
    #endif
 
    for(i = 0; i < g->numVertexes; i++)
    {
        g->vexs[i] = getchar();
        while(g->vexs[i] == '\n')
        {
            g->vexs[i] = getchar();
        }
    }
     
    #ifdef DEBUG
    for(i = 0; i < g->numVertexes; i++)
    {
        printf("%c ", g->vexs[i]);
    }
    printf("\n");
    #endif
 
 
    for(i = 0; i < g->numEdges; i++)
    {
        for(j = 0; j < g->numEdges; j++)
        {
            g->arc[i][j] = INFINITY; //邻接矩阵初始化
        }
    }
    for(k = 0; k < g->numEdges; k++)
    {
        char p, q;
        printf("输入边(vi,vj)上的下标i，下标j和权值:\n");
         
        p = getchar();
        while(p == '\n')
        {
            p = getchar();
        }
        q = getchar();
        while(q == '\n')
        {
            q = getchar();
        }
        scanf("%d", &w);   
         
        int m = -1;
        int n = -1;
        m = locates(g, p);
        n = locates(g, q);
        if(n == -1 || m == -1)
        {
            fprintf(stderr, "there is no this vertex.\n");
            return;
        }
        //getchar();
        g->arc[m][n] = w;
        g->arc[n][m] = g->arc[m][n];  //因为是无向图，矩阵对称
    }
}
 
//打印图
void printGraph(Graph g)
{
    int i, j;
    for(i = 0; i < g.numVertexes; i++)
    {
        for(j = 0; j < g.numVertexes; j++)
        {
            printf("%d  ", g.arc[i][j]);
        }
        printf("\n");
    }
}
 
int main(int argc, char **argv)
{
    Graph g;
     
    //邻接矩阵创建图
    CreateGraph(&g);
    printGraph(g);
    return 0;
}

     从代码中可以得到，n个顶点和e条边的无向网图的创建，时间复杂度为O(n + n2 + e)，其中对邻接矩阵Grc的初始化耗费了O(n2)的时间。

 

 

1.2 邻接表

 

    邻接矩阵是不错的一种图存储结构，但是，对于边数相对顶点较少的图，这种结构存在对存储空间的极大浪费。因此，找到一种数组与链表相结合的存储方法称为邻接表。

 

    邻接表的处理方法是这样的：

 

    （1）图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过，数组可以较容易的读取顶点的信息，更加方便。

 

    （2）图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

 

    例如，下图就是一个无向图的邻接表的结构。

 

    

 

    从图中可以看出，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表 的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下 标，next则存储指向边表中下一个结点的指针。

 

    对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。如下图所示。

 

    

 

    对于邻接表结构，图的建立代码如下。

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
/* 邻接表表示的图结构 */
#include <stdio.h>
#include<stdlib.h>
 
#define DEBUG
#define MAXVEX 1000         //最大顶点数
typedef char VertexType;        //顶点类型应由用户定义
typedef int EdgeType;           //边上的权值类型应由用户定义
 
typedef struct EdgeNode         //边表结点
{
    int adjvex;         //邻接点域，存储该顶点对应的下标
    EdgeType weigth;        //用于存储权值，对于非网图可以不需要
    struct EdgeNode *next;      //链域，指向下一个邻接点
}EdgeNode;
 
typedef struct VertexNode       //顶点表结构
{
    VertexType data;        //顶点域，存储顶点信息
    EdgeNode *firstedge;        //边表头指针
}VertexNode, AdjList[MAXVEX];
 
typedef struct
{
    AdjList adjList;
    int numVertexes, numEdges;  //图中当前顶点数和边数
}GraphList;
 
int Locate(GraphList *g, char ch)
{
    int i;
    for(i = 0; i < MAXVEX; i++)
    {
        if(ch == g->adjList[i].data)
        {
            break;
        }
    }
    if(i >= MAXVEX)
    {
        fprintf(stderr,"there is no vertex.\n");
        return -1;
    }
    return i;
}
 
//建立图的邻接表结构
void CreateGraph(GraphList *g)
{
    int i, j, k;
    EdgeNode *e;
    EdgeNode *f;
    printf("输入顶点数和边数:\n");
    scanf("%d,%d", &g->numVertexes, &g->numEdges);
     
    #ifdef DEBUG
    printf("%d,%d\n", g->numVertexes, g->numEdges);
    #endif
     
    for(i = 0; i < g->numVertexes; i++)
    {
        printf("请输入顶点%d:\n", i);
        g->adjList[i].data = getchar();          //输入顶点信息
        g->adjList[i].firstedge = NULL;          //将边表置为空表
        while(g->adjList[i].data == '\n')
        {
            g->adjList[i].data = getchar();
        }
    }
    //建立边表
    for(k = 0; k < g->numEdges; k++)
    {
        printf("输入边(vi,vj)上的顶点序号:\n");
        char p, q;
        p = getchar();
        while(p == '\n')
        {
            p = getchar();
        }
        q = getchar();
        while(q == '\n')
        {
            q = getchar();
        }
        int m, n;
        m = Locate(g, p);
        n = Locate(g, q);
        if(m == -1 || n == -1)
        {
            return;
        }
        #ifdef DEBUG
        printf("p = %c\n", p);
        printf("q = %c\n", q);
        printf("m = %d\n", m);
        printf("n = %d\n", n);
        #endif
     
        //向内存申请空间，生成边表结点
        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        if(e == NULL)
        {
            fprintf(stderr, "malloc() error.\n");
            return;
        }
        //邻接序号为j
        e->adjvex = n;
        //将e指针指向当前顶点指向的结构
        e->next = g->adjList[m].firstedge;
        //将当前顶点的指针指向e
        g->adjList[m].firstedge = e;
         
        f = (EdgeNode *)malloc(sizeof(EdgeNode));
        if(f == NULL)
        {
            fprintf(stderr, "malloc() error.\n");
            return;
        }
        f->adjvex = m;
        f->next = g->adjList[n].firstedge;
        g->adjList[n].firstedge = f;
    }
}
 
 
void printGraph(GraphList *g)
{
    int i = 0;
    #ifdef DEBUG
    printf("printGraph() start.\n");
    #endif
     
    while(g->adjList[i].firstedge != NULL && i < MAXVEX)
    {
        printf("顶点:%c  ", g->adjList[i].data);
        EdgeNode *e = NULL;
        e = g->adjList[i].firstedge;
        while(e != NULL)
        {
            printf("%d  ", e->adjvex);
            e = e->next;
        }
        i++;
        printf("\n");
    }
}
 
int main(int argc, char **argv)
{
    GraphList g;
    CreateGraph(&g);
    printGraph(&g);
    return 0;
}

     对于无向图，一条边对应都是两个顶点，所以，在循环中，一次就针对i和j分布进行插入。

 

 

    本算法的时间复杂度，对于n个顶点e条边来说，很容易得出是O(n+e)。

 

1.3 十字链表

 

    对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才知道，反之，逆邻接表解决了入度却不了解出度情况。下面介绍的这种有向图的存储方法：十字链表，就是把邻接表和逆邻接表结合起来的。

 

    重新定义顶点表结点结构，如下所示。

 

    

 

    其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。

 

    重新定义边表结构，如下所示。

 

    

 

    其中，tailvex是指弧起点在顶点表的下表，headvex是指弧终点在顶点表的下标，headlink是指入边表指针域，指向终点相同的下一条 边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以增加一个weight域来存储权值。

 

    比如下图，顶点依然是存入一个一维数组，实线箭头指针的图示完全与邻接表相同。就以顶点v0来说，firstout指向的是出边表中的第一个结点v3。所以，v0边表结点hearvex = 3，而tailvex其实就是当前顶点v0的下标0，由于v0只有一个出边顶点，所有headlink和taillink都是空的。

 

    

 

    重点需要解释虚线箭头的含义。它其实就是此图的逆邻接表的表示。对于v0来说，它有两个顶点v1和v2的入边。因此的firstin指向顶点v1的边表结点中headvex为0的结点，如上图圆圈1。接着由入边结点的headlink指向下一个入边顶点v2，如上图圆圈2。对于顶点v1，它有一个入边顶点v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，如上图圆圈3。

 

    十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易找到以v为尾的弧，也容易找到以v为头的弧，因而比较容易求得顶点的出度和入度。

 

    而且除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图应用中，十字链表是非常好的数据结构模型。

 

    这里就介绍以上三种存储结构，除了第三种存储结构外，其他的两种存储结构比较简单。

 

 

 

二、图的遍历

 

    图的遍历和树的遍历类似，希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫图的遍历。

 

    对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通过有两种遍历次序方案：深度优先遍历和广度优先遍历。

 

2.1 深度优先遍历

 

    深度优先遍历，也有称为深度优先搜索，简称DFS。其实，就像是一棵树的前序遍历。

 

    它从图中某个结点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中的所有顶点都被访问到为止。

 

    我们用邻接矩阵的方式，则代码如下所示。

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#define MAXVEX  100     //最大顶点数
typedef int Boolean;            //Boolean 是布尔类型，其值是TRUE 或FALSE
Boolean visited[MAXVEX];        //访问标志数组
#define TRUE 1
#define FALSE 0
 
//邻接矩阵的深度优先递归算法
void DFS(Graph g, int i)
{
    int j;
    visited[i] = TRUE;
    printf("%c ", g.vexs[i]);                           //打印顶点，也可以其他操作
    for(j = 0; j < g.numVertexes; j++)
    {
        if(g.arc[i][j] == 1 && !visited[j])
        {
            DFS(g, j);                  //对为访问的邻接顶点递归调用
        }
    }
}
 
//邻接矩阵的深度遍历操作
void DFSTraverse(Graph g)
{
    int i;
    for(i = 0; i < g.numVertexes; i++)
    {
        visited[i] = FALSE;         //初始化所有顶点状态都是未访问过状态
    }
    for(i = 0; i < g.numVertexes; i++)
    {
        if(!visited[i])             //对未访问的顶点调用DFS，若是连通图，只会执行一次
        {
            DFS(g,i);
        }
    }
}

 

 

 

    如果使用的是邻接表存储结构，其DFSTraverse函数的代码几乎是相同的，只是在递归函数中因为将数组换成了链表而有不同，代码如下。

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//邻接表的深度递归算法
void DFS(GraphList g, int i)
{
    EdgeNode *p;
    visited[i] = TRUE;
    printf("%c ", g->adjList[i].data);   //打印顶点，也可以其他操作
    p = g->adjList[i].firstedge;
    while(p)
    {
        if(!visited[p->adjvex])
        {
            DFS(g, p->adjvex);           //对访问的邻接顶点递归调用
        }
        p = p->next;
    }
}
 
//邻接表的深度遍历操作
void DFSTraverse(GraphList g)
{
    int i;
    for(i = 0; i < g.numVertexes; i++)
    {
        visited[i] = FALSE;
    }
    for(i = 0; i < g.numVertexes; i++)
    {
        if(!visited[i])
        {
            DFS(g, i);
        }
    }
}

     对比两个不同的存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找某个顶点的邻接点需要访问矩阵中的所有元素，因为需要O(n2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。

 

 

2.2 广度优先遍历

 

    广度优先遍历，又称为广度优先搜索，简称BFS。图的广度优先遍历就类似于树的层序遍历了。

 

    邻接矩阵做存储结构时，广度优先搜索的代码如下。

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//邻接矩阵的广度遍历算法
void BFSTraverse(Graph g)
{
    int i, j;
    Queue q;
    for(i = 0; i < g.numVertexes; i++)
    {
        visited[i] = FALSE;
    }
    InitQueue(&q);
    for(i = 0; i < g.numVertexes; i++)//对每个顶点做循环
    {
        if(!visited[i])               //若是未访问过
        {
            visited[i] = TRUE;
            printf("%c ", g.vexs[i]); //打印结点，也可以其他操作
            EnQueue(&q, i);           //将此结点入队列
            while(!QueueEmpty(q))     //将队中元素出队列，赋值给
            {
                int m;
                DeQueue(&q, &m);       
                for(j = 0; j < g.numVertexes; j++)
                {
                    //判断其他顶点若与当前顶点存在边且未访问过
                    if(g.arc[m][j] == 1 && !visited[j])
                    {
                        visited[j] = TRUE;
                        printf("%c ", g.vexs[j]);
                        EnQueue(&q, j);
                    }
                }
            }
        }
    }
} <span style="line-height:2;font-family:'sans serif', tahoma, verdana, helvetica;">  </span>
1
 

    对于邻接表的广度优先遍历，代码与邻接矩阵差异不大， 代码如下。

 

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//邻接表的广度遍历算法
void BFSTraverse(GraphList g)
{
    int i;
    EdgeNode *p;
    Queue q;
    for(i = 0; i < g.numVertexes; i++)
    {
        visited[i] = FALSE;
    }
    InitQueue(&q);
    for(i = 0; i < g.numVertexes; i++)
    {
        if(!visited[i])
        {
            visited[i] = TRUE;
            printf("%c ", g.adjList[i].data);   //打印顶点，也可以其他操作
            EnQueue(&q, i);
            while(!QueueEmpty(q))
            {
                int m;
                DeQueue(&q, &m);
                p = g.adjList[m].firstedge;     找到当前顶点边表链表头指针
                while(p)
                {
                    if(!visited[p->adjvex])
                    {
                        visited[p->adjvex] = TRUE;
                        printf("%c ", g.adjList[p->adjvex].data);
                        EnQueue(&q, p->adjvex);
                    }
                    p = p->next;
                }
            }
        }
    }
}<span style="font-family:'sans serif', tahoma, verdana, helvetica;line-height:1.5;">   </span>
1
 

      对比图的深度优先遍历与广度优先遍历算法，会发现，它们在时间复杂度上是一样的，不同之处仅仅在于对顶点的访问顺序不同。可见两者在全图遍历上是没有优劣之分的，只是不同的情况选择不同的算法

 

java实现的大部分内容：

 

数据结构-图-Java实现：有向图 图存储（邻接矩阵），最小生成树，广度深度遍历，图的连通性，最短路径

分类： 数据结构及算法 2012-02-03 07:39 2089人阅读 评论(3) 收藏 举报
数据结构存储integerini算法string
  1. import java.util.ArrayList;  
  2.   
  3. import java.util.List;  
  4.   
  5.    
  6.   
  7. // 模块E  
  8.   
  9. public class AdjMatrixGraph<E> {  
  10.   
  11. protected SeqList<E> vertexlist; // 顺序表存储图的顶点集合  
  12.   
  13.    
  14.   
  15. protected int[][] adjmatrix; // 图的邻接矩阵 二维图 存储的是每个顶点的名称（A,B,C,D....）  
  16.   
  17.    
  18.   
  19. private final int MAX_WEIGHT = Integer.MAX_VALUE / 2;  
  20.   
  21.    
  22.   
  23. // private final int MAX_WEIGHT = 10000;  
  24.   
  25.    
  26.   
  27. // -------一，构造图：增删改查-------------------------//  
  28.   
  29. public AdjMatrixGraph(int n) {// n为顶点的数目  
  30.   
  31. this.vertexlist = new SeqList<E>(n);  
  32.   
  33. this.adjmatrix = new int[n][n];  
  34.   
  35. for (int i = 0; i < n; i++)  
  36.   
  37. for (int j = 0; j < n; j++)  
  38.   
  39. this.adjmatrix[i][j] = (i == j) ? 0 : MAX_WEIGHT;  
  40.   
  41. // 对角线上为0，其他的都为无穷大。  
  42.   
  43. }  
  44.   
  45.    
  46.   
  47. // 构造函数内一个是字符串数组，一个是edge的set集合  
  48.   
  49. public AdjMatrixGraph(E[] vertices, Edge[] edges) {  
  50.   
  51. this(vertices.length);  
  52.   
  53. for (int i = 0; i < vertices.length; i++)  
  54.   
  55. insertVertex(vertices[i]);// 添加顶点  
  56.   
  57. for (int j = 0; j < edges.length; j++)  
  58.   
  59. insertEdge(edges[j]);// 添加边  
  60.   
  61. }  
  62.   
  63.    
  64.   
  65. // 构造函数内一个是数组集合，一个是edge的set集合  
  66.   
  67. public AdjMatrixGraph(SeqList<E> list, Edge[] edges) {  
  68.   
  69. this(list.length());  
  70.   
  71. this.vertexlist = list;  
  72.   
  73. for (int j = 0; j < edges.length; j++)  
  74.   
  75. insertEdge(edges[j]);  
  76.   
  77. }  
  78.   
  79.    
  80.   
  81. // 显示出一共顶点的数目  
  82.   
  83. public int vertexCount() {  
  84.   
  85. return this.vertexlist.length();  
  86.   
  87. }  
  88.   
  89.    
  90.   
  91. // 根据编号得到该顶点  
  92.   
  93. public E get(int i) {  
  94.   
  95. return this.vertexlist.get(i);  
  96.   
  97. }  
  98.   
  99.    
  100.   
  101. public boolean insertVertex(E vertex) { // 插入一个顶点，若插入成功，返回true  
  102.   
  103.    
  104.   
  105. return this.vertexlist.add(vertex);  
  106.   
  107. }  
  108.   
  109.    
  110.   
  111. public boolean insertEdge(int i, int j, int weight)  
  112.   
  113. // 插入一条权值为weight的边<vi,vj>，若该边已有，则不插入  
  114.   
  115. {  
  116.   
  117. if (i >= 0 && i < vertexCount() && j >= 0 && j < vertexCount()  
  118.   
  119. && i != j && adjmatrix[i][j] == MAX_WEIGHT) {  
  120.   
  121. // 先判断该边两个顶点的编号是否在范围，该边的值是否为最大值，来确定所添加边的值是否存在；  
  122.   
  123. this.adjmatrix[i][j] = weight;// 添加权值  
  124.   
  125. return true;  
  126.   
  127. }  
  128.   
  129. return false;  
  130.   
  131. }  
  132.   
  133.    
  134.   
  135. public boolean insertEdge(Edge edge) {  
  136.   
  137. if (edge != null)  
  138.   
  139. ;  
  140.   
  141. return insertEdge(edge.start, edge.dest, edge.weight);  
  142.   
  143. }  
  144.   
  145.    
  146.   
  147. public String toString() {  
  148.   
  149. String str = "顶点集合： " + vertexlist.toString() + "\n";  
  150.   
  151. str += "邻近矩阵：    \n";  
  152.   
  153. int n = vertexCount();  
  154.   
  155. for (int i = 0; i < n; i++) {  
  156.   
  157. for (int j = 0; j < n; j++) {  
  158.   
  159. if (adjmatrix[i][j] == MAX_WEIGHT)  
  160.   
  161. str += " ∞";// 最大值（不存在）的时候的显示方式；  
  162.   
  163. else  
  164.   
  165. str += " " + adjmatrix[i][j];// 每一个顶点到其他顶点的权值  
  166.   
  167. }  
  168.   
  169. str += "\n";  
  170.   
  171. }  
  172.   
  173. return str;  
  174.   
  175. }  
  176.   
  177.    
  178.   
  179. public boolean removeEdge(int i, int j) // 删除边〈vi,vj〉，若成功，返回T  
  180.   
  181. {  
  182.   
  183. if (i >= 0 && i < vertexCount() && j >= 0 && j < vertexCount()  
  184.   
  185. && i != j && this.adjmatrix[i][j] != MAX_WEIGHT) {  
  186.   
  187. // 判断该边的两个顶点是否存在，以及改边的值是否为最大值来判断改边是否存在；  
  188.   
  189. this.adjmatrix[i][j] = MAX_WEIGHT; // 设置该边的权值为无穷大，说明已不存在；  
  190.   
  191. return true;  
  192.   
  193. }  
  194.   
  195. return false;  
  196.   
  197. }  
  198.   
  199.    
  200.   
  201. public boolean removeVertex(int v) // 删除序号为v的顶点及其关联的边  
  202.   
  203. {  
  204.   
  205. int n = vertexCount(); // 删除之前的顶点数  
  206.   
  207. if (v >= 0 && v < n) {// V的要求范围  
  208.   
  209. this.vertexlist.remove(v); // 删除顺序表的第i个元素，顶点数已减一  
  210.   
  211. for (int i = v; i < n - 1; i++)  
  212.   
  213. for (int j = 0; j < n; j++)  
  214.   
  215. this.adjmatrix[i][j] = this.adjmatrix[i + 1][j]; // 邻接矩阵：删除点以下往上移动一位  
  216.   
  217. for (int j = v; j < n - 1; j++)  
  218.   
  219. for (int i = 0; i < n - 1; i++)  
  220.   
  221. this.adjmatrix[i][j] = this.adjmatrix[i][j + 1]; // 邻接矩阵：删除点以右往左移动一位  
  222.   
  223. return true;  
  224.   
  225. }  
  226.   
  227. return false;  
  228.   
  229. }  
  230.   
  231.    
  232.   
  233. public int getFirstNeighbor(int v) // 返回顶点v的第一个邻接顶点的序号  
  234.   
  235. {  
  236.   
  237. return getNextNeighbor(v, -1);  
  238.   
  239. } // 若不存在第一个邻接顶点，则返回-1  
  240.   
  241.    
  242.   
  243. public int getNextNeighbor(int v, int w) { // 返回v在w后的下一个邻接顶点  
  244.   
  245. if (v >= 0 && v < vertexCount() && w >= -1 && w < vertexCount()// 对v  
  246.   
  247. // w的范围限定  
  248.   
  249. && v != w)  
  250.   
  251. for (int j = w + 1; j < vertexCount(); j++)  
  252.   
  253. // w=-1时，j从0开始寻找下一个邻接顶点  
  254.   
  255. if (adjmatrix[v][j] > 0 && adjmatrix[v][j] < MAX_WEIGHT)  
  256.   
  257. // 遍历和v相关的点，得到下一个点  
  258.   
  259. return j;  
  260.   
  261. return -1;  
  262.   
  263. }  
  264.   
  265.    
  266.   
  267. // -------二，最小生成树-------------------------//  
  268.   
  269.    
  270.   
  271. /* 
  272.  
  273. * 普里姆算法的基本思想: 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。 在添加的顶点 w 
  274.  
  275. * 和已经在生成树上的顶点v之间必定存在一条边， 并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。 
  276.  
  277. * 之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。 
  278.  
  279. */  
  280.   
  281.    
  282.   
  283. public AdjMatrixGraph minSpanTree_prim() {  
  284.   
  285. Edge[] mst = new Edge[this.vertexCount() - 1]; // n个顶点最小生成树有n-1条边  
  286.   
  287. int un;  
  288.   
  289. List<Integer> u = new ArrayList<Integer>();// 存放所有已访问过的顶点集合  
  290.   
  291. u.add(0);// 起始点默认为标识为0的顶点  
  292.   
  293. for (int i = 0; i < this.vertexCount() - 1; i++) {  
  294.   
  295. int minweight = MAX_WEIGHT;// 最小边的时候，权值  
  296.   
  297. int minstart = MAX_WEIGHT;// 最小边的时候，起点  
  298.   
  299. int mindest = MAX_WEIGHT;// 最小边的时候，终点  
  300.   
  301. for (int j = 0; j < u.size(); j++) {  
  302.   
  303. un = u.get(j);  
  304.   
  305. for (int k = 0; k < this.vertexCount(); k++) {  
  306.   
  307. // 获取最小值的条件：1.该边比当前情况下的最小值小；2.该边还未访问过；  
  308.   
  309. if ((minweight > adjmatrix[un][k]) && (!u.contains(k))) {  
  310.   
  311. minweight = adjmatrix[un][k];  
  312.   
  313. minstart = un;  
  314.   
  315. mindest = k;  
  316.   
  317. }  
  318.   
  319. }  
  320.   
  321. }  
  322.   
  323. System.out.println("一次遍历所添加的最小边：他的权值，起点，终点分别为：weight:" + minweight  
  324.   
  325. + "start:" + minstart + "dest:" + mindest);  
  326.   
  327. u.add(mindest);  
  328.   
  329. Edge e = new Edge(minstart, mindest, adjmatrix[minstart][mindest]);  
  330.   
  331. mst[i] = e;  
  332.   
  333. }  
  334.   
  335. return new AdjMatrixGraph(this.vertexlist, mst); // 构造最小生成树相应的图对象  
  336.   
  337. }  
  338.   
  339.    
  340.   
  341. /* 
  342.  
  343. * public AdjMatrixGraph minSpanTree_kruskal() { } 
  344.  
  345. */  
  346.   
  347.    
  348.   
  349. // -------三，图的遍历（广度遍历，深度遍历）-------------------------//  
  350.   
  351. public void DFStraverse() {  
  352.   
  353. int n = this.vertexCount();  
  354.   
  355. boolean[] visited = new boolean[n];  
  356.   
  357. for (int i = 1; i < n; i++) {  
  358.   
  359. visited[i] = false;  
  360.   
  361. }  
  362.   
  363. // 编号0为起始点，进行一次深度优先遍历（一次得到一个连通分量）  
  364.   
  365. for (int j = 0; j < n; j++) {  
  366.   
  367. if (!visited[j]) {  
  368.   
  369. System.out.println("以该顶点为" + j + "起始点的遍历：");  
  370.   
  371. this.DFS(j, visited);  
  372.   
  373. }  
  374.   
  375. }  
  376.   
  377. }  
  378.   
  379.    
  380.   
  381. // 参数1：遍历起始点的编号，参数2：记录各个顶点是否被访问过  
  382.   
  383. public void DFS(int v, boolean[] visited2) {  
  384.   
  385. boolean[] visited = visited2;  
  386.   
  387. visited[v] = true;  
  388.   
  389. System.out.println("遍历顶点" + v);  
  390.   
  391. for (int w = this.getFirstNeighbor(v); w >= 0; w = this  
  392.   
  393. .getNextNeighbor(v, w)) {  
  394.   
  395. if (!visited[w]) {  
  396.   
  397. visited[w] = true;  
  398.   
  399. DFS(w, visited);  
  400.   
  401. }  
  402.   
  403. }  
  404.   
  405. }  
  406.   
  407.    
  408.   
  409. public void BFStraverse() {  
  410.   
  411. int n = this.vertexCount();  
  412.   
  413. boolean[] visited = new boolean[n];  
  414.   
  415. MyQueue myqueue = new MyQueue();  
  416.   
  417. for (int i = 1; i < n; i++) {  
  418.   
  419. visited[i] = false;  
  420.   
  421. }  
  422.   
  423.    
  424.   
  425. for (int j = 0; j < n; j++) {  
  426.   
  427. if (!visited[j]) {  
  428.   
  429. visited[j] = true;  
  430.   
  431. System.out.println("遍历起点：" + j);  
  432.   
  433. myqueue.EnQueue(j);  
  434.   
  435. while (!myqueue.empty()) {  
  436.   
  437. int v = (Integer) myqueue.DeQueue();  
  438.   
  439. System.out.println("遍历点：" + v);  
  440.   
  441. for (int w = this.getFirstNeighbor(v); w >= 0; w = this  
  442.   
  443. .getNextNeighbor(v, w)) {  
  444.   
  445. if (!visited[w]) {  
  446.   
  447. visited[w] = true;  
  448.   
  449. myqueue.EnQueue(w);  
  450.   
  451. }  
  452.   
  453. }  
  454.   
  455. }  
  456.   
  457. }  
  458.   
  459. }  
  460.   
  461.    
  462.   
  463. }  
  464.   
  465.    
  466.   
  467. // -------四，图的最短路径Dijkstra算法-------------------------//  
  468.   
  469. public void Dijkstra() {  
  470.   
  471. int n = this.vertexCount();  
  472.   
  473. int minweight = MAX_WEIGHT;  
  474.   
  475. int minUn = 0;  
  476.   
  477. int[] minmatrix = new int[n];// 存放当前起始点到其余各个顶点的距离；  
  478.   
  479. boolean[] isS = new boolean[n];// 判断各个是否被访问过  
  480.   
  481. String[] route = new String[n];// 每个字符串是显示对应顶点最短距离的路径；  
  482.   
  483. for (int i = 1; i < n; i++) {// 初始化  
  484.   
  485. minmatrix[i] = adjmatrix[0][i];  
  486.   
  487. isS[i] = false;  
  488.   
  489. route[i] = "起点->" + i;  
  490.   
  491. }  
  492.   
  493. for (int i = 1; i < n; i++) {  
  494.   
  495. // 选择 当前 和起点 连通的，且值最小的顶点；  
  496.   
  497. for (int k = 1; k < n; k++) {  
  498.   
  499. if (!isS[k]) {  
  500.   
  501. if (minmatrix[k] < minweight) {  
  502.   
  503. minweight = minmatrix[k];  
  504.   
  505. minUn = k;  
  506.   
  507. }  
  508.   
  509. }  
  510.   
  511. }  
  512.   
  513. isS[minUn] = true;// 将该点设置为已访问；  
  514.   
  515. for (int j = 1; j < n; j++) {  
  516.   
  517. if (!isS[j]) {// 判断：该顶点还没加入到S中/属于U-S；  
  518.   
  519. if (minweight + adjmatrix[minUn][j] < minmatrix[j]) {  
  520.   
  521. // 通过当下最小值 访问到得其他顶点的距离小于原先的最小值 则进行交换值  
  522.   
  523. minmatrix[j] = minweight + adjmatrix[minUn][j];  
  524.   
  525. route[j] = route[minUn] + "->" + j;  
  526.   
  527. }  
  528.   
  529. }  
  530.   
  531. }  
  532.   
  533. minweight = MAX_WEIGHT;// 因为要放到下一个循环中，所以一定要重设置一下，回到最大值  
  534.   
  535. }  
  536.   
  537. for (int m = 1; m < n; m++) {  
  538.   
  539. System.out.println("从V0出发到达" + m + "点");  
  540.   
  541. if (minmatrix[m] == MAX_WEIGHT) {  
  542.   
  543. System.out.println("没有到达该点的路径");  
  544.   
  545. } else {  
  546.   
  547. System.out.println("当前从V0出发到达该点的最短距离：" + minmatrix[m]);  
  548.   
  549. System.out.println("当前从V0出发到达该点的最短距离：" + route[m]);  
  550.   
  551.    
  552.   
  553. }  
  554.   
  555. }  
  556.   
  557. }  
  558.   
  559.    
  560.   
  561. // -------五，图的连通性-------------------------//  
  562.   
  563. public boolean isConnect() {  
  564.   
  565. int n = this.vertexCount();  
  566.   
  567. boolean[] visited = new boolean[n];  
  568.   
  569. // 记录不能一次深度优先遍历通过的数目  
  570.   
  571. // 全部顶点作为出发点开始遍历，如果全部都不能一次遍历通过（notConnectNum == n），说明该图不连通。  
  572.   
  573. int notConnectNum = 0;  
  574.   
  575. for (int j = 0; j < n; j++) {  
  576.   
  577. for (int i = 0; i < n; i++) {  
  578.   
  579. visited[i] = false;  
  580.   
  581. }  
  582.   
  583. this.DFS(j, visited);  
  584.   
  585. for (int k = 0; k < n; k++) {  
  586.   
  587. System.out.println(visited[k]);  
  588.   
  589. if (visited[k] == false) {  
  590.   
  591. notConnectNum++;  
  592.   
  593. break;// 一旦有没有被遍历到的顶点（说明该顶点不属于该连通分量），跳出循环  
  594.   
  595. }  
  596.   
  597. }  
  598.   
  599. }  
  600.   
  601. if (notConnectNum == n) {  
  602.   
  603. System.out.println("此图是不连通的");  
  604.   
  605. return false;  
  606.   
  607. } else {  
  608.   
  609. System.out.println("此图是连通的");  
  610.   
  611. return true;  
  612.   
  613. }  
  614.   
  615. }  
  616.   
  617.    
  618.   
  619. // -------六，图的拓扑排序-------------------------//  
  620.   
  621. public void topologicalSort() {  
  622.   
  623. int n = this.vertexCount();  
  624.   
  625. int[] indegree = new int[n];  
  626.   
  627. MyStack mystack = new MyStack();  
  628.   
  629. String route = "拓扑排序出发：";  
  630.   
  631. int count = 0;  
  632.   
  633. for (int i = 0; i < n; i++) {  
  634.   
  635. indegree[i] = 0;  
  636.   
  637. for (int j = 0; j < n; j++) {//获取每一个顶点的入度  
  638.   
  639. if (adjmatrix[j][i] != 0 && adjmatrix[j][i] != MAX_WEIGHT) {  
  640.   
  641. indegree[i] += 1;  
  642.   
  643. }  
  644.   
  645. }//先将入度为0的顶点加入到栈中  
  646.   
  647. if (indegree[i] == 0) {  
  648.   
  649. mystack.push(i);  
  650.   
  651. }  
  652.   
  653. }  
  654.   
  655. while (!mystack.empty()) {  
  656.   
  657. int v = (Integer) mystack.pop();//从栈中删除该顶点  
  658.   
  659. route += "->" + v;  
  660.   
  661. ++count;  
  662.   
  663. for (int w = this.getFirstNeighbor(v); w >= 0; w = this  
  664.   
  665. .getNextNeighbor(v, w)) {  
  666.   
  667. indegree[w] -= 1;//因为该顶点被“删除”，所有以该顶点为弧尾的边的弧头的入度减一  
  668.   
  669. if (indegree[w] == 0) {  
  670.   
  671. mystack.push(w);//先将入度为0的顶点加入到栈中  
  672.   
  673. }  
  674.   
  675. }  
  676.   
  677. }  
  678.   
  679. if (count < n) {//当经历拓扑排序遍历后，所有顶点都被“删除”时（count=n），此时实现拓扑排序  
  680.   
  681. System.out.println("存在回路，不满足拓扑排序的条件");  
  682.   
  683. } else {  
  684.   
  685. System.out.println("实现拓扑排序" + route);  
  686.   
  687.    
  688.   
  689. }  
  690.   
  691. }  
  692.   
  693.   
  694. }  

 

分享到：
| 趣味数学（各大经典数学问题）
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    图形算法存储库的编码分钟课程示例 - Java-C++ - 下载.zip

    图形算法涉及到图的表示（如邻接矩阵和邻接表）、遍历（深度优先搜索DFS和广度优先搜索BFS）以及图的基本操作，如查找路径、最小生成树（Kruskal's或Prim's算法）和最短路径问题（Dijkstra算法和Floyd-Warshall算法...

    编码分钟课程的图形算法存储库_Java_C++_下载.zip

    - Kruskal's算法和Prim's算法：最小生成树问题，用于寻找图中边的最小集合，使得这些边连接的所有顶点形成一棵树。 - Topological Sort：有向无环图的排序，常用于解决依赖关系问题。 - Tarjan算法和Floyd-...

    基础07图的遍历和最小生成树.flv.zip

    在IT领域，图的遍历和最小生成树是图论中的两个重要概念，它们在算法设计和网络优化问题中有着广泛的应用。让我们深入探讨这两个概念。 首先，我们来看图的遍历。图是由顶点（节点）和边（连接顶点的线）构成的数据...

    Graph Theory Codes in C用C++写的复杂网络图论算法.rar

    4. **最小生成树**：Prim算法和Kruskal算法用于构建图的最小生成树，保证树中边的权重之和最小。Prim适合加权连通图，而Kruskal处理无环加权图。 5. **拓扑排序**：对于有向无环图（DAG），拓扑排序给出一个无环的...

    数据结构图的各种算法的实现（我已经调试成功）

    3. **其他图的算法**：除了遍历和最小生成树，还有许多其他与图相关的算法，如： - **Dijkstra算法**：单源最短路径算法，用于找出从一个顶点到图中其他所有顶点的最短路径。 - **Floyd-Warshall算法**：全源...

    竞争性编程所需的算法_C++_Java_下载.zip

    2. **搜索算法**：深度优先搜索(DFS)和广度优先搜索(BFS)是最常见的两种图遍历方法，用于解决路径寻找、最短路径等问题。二分查找在有序数组中查找元素效率极高，时间复杂度为O(log n)。 3. **动态规划(DP)**：动态...

    java,c++等,常见算法,面试算法题

    如霍夫曼编码、Prim's最小生成树算法、Dijkstra的最短路径算法。 6. **回溯法（Backtracking）**： 用于解决问题的一种试探性方法，当遇到困境时，回溯到前一步或者更早的状态，尝试其他可能的路径。如八皇后问题...

    02 ALGraph.rar

    图算法是处理图数据结构时所用到的方法，包括查找、遍历、最短路径计算、最小生成树等。严蔚敏教授的教材中可能包含了一些经典的图算法实现，如深度优先搜索（DFS）和广度优先搜索（BFS）。DFS用于遍历图的所有节点...

    数据结构与算法代码.rar.rar

    4. 图算法：实现图的邻接矩阵或邻接表表示，以及DFS、BFS算法，可能还包括最小生成树（Prim或Kruskal）和最短路径算法。 5. 排序算法：各种排序算法的实现，比较它们的时间复杂性和稳定性。 6. 查找算法：线性查找、...

    学习数据结构与算法的代码示例，目前提供 Java、Python、Go、C++ 多种语言支持。.zip

    - **贪心算法**：每一步都采取局部最优解，适用于背包问题、最小生成树等。 3. **编程语言特性**: - **Java**：面向对象，跨平台，内存自动管理，有丰富的类库。 - **Python**：语法简洁，适合快速开发，大量库...

    数据结构DFS、BFS算法、Prim算法、Kruskal算法、Dijstra算法、Floyd算法

    在"图综合实现"的压缩包中，很可能是包含了以上这些算法的实现代码，可能使用C++、Java或Python等编程语言。这些代码会展示如何利用邻接矩阵来存储图的数据结构，以及如何具体实现DFS、BFS、Prim、Kruskal、Dijkstra...

    数据结构课后习题答案 清华大学版

    对于图，可能会有DFS和BFS遍历、最小生成树或最短路径算法的代码实现。 代码实现部分尤为重要，因为它能帮助理解理论知识在实际编程中的应用。例如，你可以找到如何用C++、Java或Python等语言实现栈、队列、树和图...

    数据结构课程设计报告----景区旅游信息管理系统.doc

    - 系统的实现涉及编程语言的选择，如C++、Java或Python等，以及数据结构和算法的具体实现。 - 需要处理输入输出，例如读取景点信息、展示结果和接收用户选择的功能。 这个系统不仅为游客提供了个性化的游览方案，...

    《Hello 算法》：动画图解、一键运行的数据结构与算法教程，支持 Python, C++, Java, C#, G.zip

    你可以期待学习到排序算法（如冒泡排序、选择排序、插入排序、快速排序、归并排序等）、搜索算法（如线性搜索、二分搜索、哈希搜索等）、图算法（如Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法、Prim...

    《数据结构与算法分析》各章的代码详细解释.zip

    6. **图论算法**：包括Dijkstra最短路径算法、Floyd-Warshall所有顶点间最短路径、Prim最小生成树、Kruskal最小生成树等，这些在路由算法、网络规划等领域有广泛应用。 7. **字符串处理**：涉及到模式匹配（如KMP...

    数据结构试验源代码全集

    11. **图论算法**：如最小生成树、拓扑排序、网络流和最短路径算法等。 通过阅读和理解这些源代码，学习者不仅可以掌握数据结构的理论知识，还能提升编程能力，更好地运用到实际项目中。这些源代码通常会采用C、C++...

    数据结构试验4-图实验报告及源码

    3. **图的最小生成树**：在加权图中，可能会涉及寻找最小生成树（MST）的问题，例如Prim算法或Kruskal算法。这些算法用于找到连接所有顶点的最小总权重的边集。 4. **最短路径算法**：在寻找两个顶点之间的最短路径...

    《剑指 Offer》 Python, Java, C++ 解题代码，LeetBook《图解算法数据结构》配套代码仓.zip

    查找算法（如顺序查找、二分查找、哈希查找），图论算法（如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法），动态规划，贪心算法，回溯法，分支限界法等。 算法分析：通过数学方法分析算法的时间...

    820计算机专业基础考纲.docx

    图的存储结构和遍历算法，如最小生成树、最短路径等，同样在考试范围内。 在查找方面，考生需了解各种查找算法，如顺序查找、折半查找、哈希查找等，并能分析其时间复杂度和空间复杂度。排序算法，如插入排序、选择...

    数据结构大纲.doc

    涵盖了数据结构的基本概念、各种数据结构的定义和实现算法、程序性能、数据描述、数组和矩阵、堆栈、队列、跳表和散列、二叉树、优先队列、搜索树、图和贪婪算法等内容，为考研的学生提供了系统的知识结构和考察方向...

Magicbox
Global site tag (gtag.js) - Google Analytics