用C语言写图的建立-邻接矩阵
时间: 2023-06-08 19:05:53 浏览: 56
好的,我们来看一下用C语言写图的邻接矩阵的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXV 100 // 图中最多顶点数目
int mat[MAXV][MAXV]; // 图的邻接矩阵
int n; // 顶点数
int main()
{
scanf("%d", &n); // 读入顶点数
int i, j;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
scanf("%d", &mat[i][j]); // 读入边权值
}
}
// 打印邻接矩阵
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
printf("%d ", mat[i][j]);
}
printf("\n");
}
return 0;
}
```
这段代码首先读入了图的顶点数n,然后通过嵌套的for循环接收各个边的权重,并将它们存储到邻接矩阵mat[][]中。最后再通过另一个for循环打印邻接矩阵的内容。
相关问题
用C语言写图的建立-邻接矩阵,涉及算法
,你能给我讲讲吗?
当使用邻接矩阵表示图时,需要声明一个二维数组。数组的行和列分别表示图中所有节点的编号。如果两个节点之间有连边,则在相应位置上记录边的权值。如果两个节点之间没有连边,则在相应的位置上记录一个特定的值,例如0或无穷大。
具体实现时,可以使用类似下面的代码:
```
#define MAX_N 100 //最大节点个数
int graph[MAX_N][MAX_N];
//初始化邻接矩阵
void initGraph() {
//将所有的值设为0或者无穷大
for(int i = 0; i < MAX_N; i++) {
for(int j = 0; j < MAX_N; j++) {
graph[i][j] = 0;
}
}
}
//添加一条边
void addEdge(int u, int v, int w) {
graph[u][v] = w; //有向图
graph[v][u] = w; //无向图
}
//遍历节点u的所有邻居节点
void traverseNeighbors(int u) {
for(int v = 0; v < MAX_N; v++) {
if(graph[u][v] != 0) {
//v是u的邻居节点
}
}
}
```
算法实现上,常见的操作包括求解图的连通性、最短路、最小生成树等等,它们都可以在邻接矩阵上高效地实现。不同的算法涉及不同的细节和优化,这里就不再进一步展开了。
用c语言写一个用邻接矩阵存储图的prim
以下是使用邻接矩阵存储图的Prim算法的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define V 5
int minKey(int key[], int visited[]) {
int min = INT_MAX, min_index;
for (int i = 0; i < V; i++) {
if (visited[i] == 0 && key[i] < min) {
min = key[i];
min_index = i;
}
}
return min_index;
}
void printMST(int parent[], int graph[V][V]) {
printf("Edge \tWeight\n");
for (int i = 1; i < V; i++) {
printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}
}
void primMST(int graph[V][V]) {
int parent[V];
int key[V];
int visited[V];
for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
visited[i] = 0;
}
key[0] = 0;
parent[0] = -1;
for (int i = 0; i < V - 1; i++) {
int u = minKey(key, visited);
visited[u] = 1;
for (int v = 0; v < V; v++) {
if (graph[u][v] && visited[v] == 0 && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
printMST(parent, graph);
}
int main() {
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };
primMST(graph);
return 0;
}
```
这里使用 `minKey` 函数来找到最小关键字的顶点,然后使用 `printMST` 函数来打印最小生成树的结果。 `primMST` 函数是主函数,其中 `key` 数组用于存储每个顶点的关键字、 `visited` 数组用于表示每个顶点是否已经被访问过、 `parent` 数组用于存储每个顶点的父结点。