By yusijia

Updated:

Contents 
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

#include <stdio.h>

#define MAXVEX 100                      //最大顶点数,应由用户定义
#define INFINITY 65535                  //用65535来代表∞

bool visited[MAXVEX];                    //访问标志数组
typedef char VertexType;                 //顶点类型应用户定义
typedef int  EdgeType;                   //边上的权值应由用户定义
typedef int InforType;                   //信息的类型由用户定义

typedef struct Graph{
    VertexType vexs[MAXVEX];            //顶点表
    EdgeType arc[MAXVEX][MAXVEX];       //邻接矩阵,可看作边
    int numVertexes, numEdge;           //图中当前的顶点数和边数
}Graph;

//定位
int locates(Graph *g, char ch)
{
    int i;
    for(i = 0; i < g->numVertexes; i++)
    {
        if(g->vexs[i] == ch)
            break;
    }
    if(i >= g->numVertexes)
        return -1;
    return i;
}
//建立一个无向网图的邻接矩阵表示
void CreatGraph(Graph *g)
{
    int i, j, k, w;
    printf("输入顶点数和边数:\n");
    scanf("%d %d", &(g->numVertexes), &(g->numEdge));
    getchar();//吃回车
    for(i = 0; i < g->numVertexes; i++)
    {
        scanf("%c", &(g->vexs[i]));
    }
    getchar(); //吃回车
    for(i = 0; i < g->numVertexes; i++)
    {
        for(j = 0; j < g->numVertexes; j++)
        {
            g->arc[i][j] = INFINITY; //邻接矩阵初始化
        }
    }
    for(k = 0; k < g->numEdge; k++)
    {
        char p, q;
        printf("输入边(vi,vj)上的下标i，下标j和权值:\n");
        scanf("%c %c %d", &p, &q, &w);
        getchar(); //吃回车
        int m = locates(g, p);
        int n = locates(g, q);
        if(n == -1 || m == -1)
        {
            printf("There is no this Vertex !\n");
            return ;
        }
        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");
    }
}


//邻接矩阵的深度优先递归算法
void DFS(Graph g, int i)
{
    visited[i] = true;
    printf("%c ", g.vexs[i]);               //打印顶点，也可以其他操作
    for(int j = 0; j < g.numVertexes; j++)
    {
        if(g.arc[i][j] == 1 && !visited[j]);//有边,且没被访问过
            DFS(g, j);                      //对未访问的邻接顶点递归调用
    }
}

//邻接矩阵的深度遍历操作
void DFSTraverse(Graph g)
{
    for(int i = 0; i < g.numVertexes; i++)
        visited[i] = false;                 //初始化所有顶点状态都是未访问过状态
    for(int i = 0; i < g.numVertexes; i++)
    {
        if(!visited[i])
            DFS(g, i);                      //对未访问的顶点调用DFS，若是连通图，只会执行一次
    }
}

int main()
{
    Graph g;
    CreatGraph(&g);
    printGraph(g);
    return 0;
}
Contents