邻接表c语言

Ⅰ c语言关于图的邻接表建立

#include "iostream.h"

const int Max_vertex=5;
const int Max_Edge=8;
int visited[Max_vertex+1]; //访问标志数组

struct ArcNode
{
int adjvex;
ArcNode *nextarc; //指向下一条弧
};

struct Vnode
{
int v; //顶点信息
ArcNode *next;
}a[Max_vertex+1];

/* 无向图的建立 */
void creategraph()
{
int i,j,k;
ArcNode *s;
//初始化
for(i=1;i<=Max_vertex;i++)
{
a[i].v=i;
a[i].next=NULL;
}

/*以头插法建立 */

for(k=1;k<=Max_Edge;k++)
{
cout<<"请输入第"<<k<<"条边:";
cin>>i>>j;
if(i>9||i<0||j<0||j>9)
{
cout<<"输入错误!!\n"<<endl;
break;
}
else{
cout<<endl;
s=new ArcNode;
s->adjvex=j;
s->nextarc=a[i].next;
a[i].next=s;
s=new ArcNode;
s->adjvex=i;
s->nextarc=a[j].next;
a[j].next=s;
}
}
}

void display()
{
ArcNode *p;
cout<<"你建立的图为:"<<endl;
for(int i=1;i<=Max_vertex;i++)
{
p=a[i].next;
cout<<a[i].v<<"->";
while(p->nextarc!=NULL)
{
cout<<p->adjvex<<"->";
p=p->nextarc;
}
cout<<p->adjvex<<endl;
}
}

void main()
{
cout<<"/******\t本算法以关插法建立无向图的邻接表为例!\t******/"<<endl;
char yn='y';int k;
creategraph();
display();

}

Ⅱ 数据结构-图的邻接表表示（C语言）

//grap_theory.cpp:定义控制台应用程序的入口点。

//

//#include"stdafx.h"//VS2010头文件

#include<stdio.h>

#defineNTOTAL(26*4)//最大路径数目

#defineMAX_DISTANCE10000.0

structpiont{

intline_adjacency_list;

intnum_piont;

inttest_num[2];

charfrom[NTOTAL];

charto[NTOTAL];

charall_piont[NTOTAL];

intall_piont_num[NTOTAL];

floatdistance[NTOTAL];

floatdistance_all[NTOTAL][NTOTAL];

};//结构体定义

voidread(piont*test){

inti;

chartemp[100];

scanf("%d",&test->line_adjacency_list);//读取行数

gets(temp);//读取回车字符

for(i=0;i<test->line_adjacency_list;i++){//读取列表

scanf("%c%c%f",&test->from[i],&test->to[i],&test->distance[i]);

gets(temp);//读取回车字符

}

scanf("%c%c",&test->from[i],&test->to[i]);//读取短短路径名称

}

voidcal_num_piont(piont*test){

inti,j;

intfrom_num,to_num;

test->num_piont=0;

for(i=0;i<NTOTAL;i++){

test->all_piont_num[i]=0;//点的度数清零

test->distance_all[i][i]=0.0;

for(j=i+1;j<NTOTAL;j++){

test->distance_all[i][j]=MAX_DISTANCE;

test->distance_all[j][i]=MAX_DISTANCE;

}

}

for(i=0;i<test->line_adjacency_list;i++){

//判断from

for(j=0;j<test->num_piont;j++){

if(test->from[i]==test->all_piont[j]){

from_num=j;

test->all_piont_num[j]++;

break;

}

}

if(j==test->num_piont){

test->all_piont[j]=test->from[i];

from_num=j;

test->all_piont_num[j]++;

test->num_piont++;

}

//判断end

for(j=0;j<test->num_piont;j++){

if(test->to[i]==test->all_piont[j]){

to_num=j;

test->all_piont_num[j]++;

break;

}

}

if(j==test->num_piont){

test->all_piont[j]=test->to[i];

to_num=j;

test->all_piont_num[j]++;

test->num_piont++;

}

test->distance_all[from_num][to_num]=test->distance[i];

test->distance_all[to_num][from_num]=test->distance[i];

}

//判断所求点的位置

for(i=0;i<test->num_piont;i++){

if(test->from[test->line_adjacency_list]==test->all_piont[i])

test->test_num[0]=i;

if(test->to[test->line_adjacency_list]==test->all_piont[i])

test->test_num[1]=i;

}

}

floatmin_distance(piont*test){

inti,j,k,n;

floatmin_dis;

floatdis_i_k_add_k_j;

n=test->num_piont;

//Floyd-Warshall算法

for(k=0;k<n;k++){

for(i=0;i<n;i++){

for(j=0;j<n;j++){

dis_i_k_add_k_j=(test->distance_all[i][k]+test->distance_all[k][j]);

if(test->distance_all[i][j]>dis_i_k_add_k_j)

test->distance_all[i][j]=dis_i_k_add_k_j;

}

}

}

min_dis=test->distance_all[test->test_num[0]][test->test_num[1]];

returnmin_dis;

}

voidtest_printf(piont*test,floatmin_dis){

inti;

printf("%d ",test->num_piont);

for(i=0;i<test->num_piont;i++){

printf("%d ",test->all_piont_num[i]);

}

printf("%-8.0f ",min_dis);

}

voidmain()

{

floatmin_dis;

pionttest1;//结构体声明

read(&test1);

cal_num_piont(&test1);

min_dis=min_distance(&test1);

test_printf(&test1,min_dis);

}

Ⅲ c语言，图的邻接表创建问题。 关于scanf的，不明白是怎么回事

你在输入的时候是用回车结束的吧？
scanf()函数从输入流缓冲区中读取值的，而读取时遇到回车(\n)而结束的。带空格的scanf(" %c")表示要从输入流缓冲区读两个字符，一个给空格，一个给%c。为什么加空格呢，是因为回车符(\n)也在输入流缓冲区中，所以将\n赋值给空格，以让%c被正确赋值。否则，不加空格，回车符\n会被赋值给%c。

Ⅳ C语言 邻接矩阵和邻接表

/**********************邻接矩阵*****************/

#include<bits/stdc++.h>//邻接矩阵

using namespace std;

const int N=300;

int Map[N][N]={0};//邻接矩阵

int book[N]={0};//结点标记数组(1表示该点访问过了;0未访问过)

int n,m;

void dfs(int x)//深度遍历

{

for(int i=1;i<=n;i++)

{//book[i]==0:i未被访问过

// Map[x][i]==1：x到i有边连接

if(book[i]==0&&Map[x][i]==1)

{

book[i]=1;//访问标记

printf("->[%d]",i);

dfs(i);//前往下一个结点i

}

}

}

void bfs(int x)

{

int q[N]={0};

int fornt=0;

int rear=0;

q[rear++]=x;//源点入队

while(fornt<rear)

{

int k=q[fornt++];//出队

for(int i=1;i<=n;i++)

{//扩展一个点周围可以访问的点

if(book[i]==0&&Map[k][i]==1)

{

printf("->[%d]",i);

book[i]=1;//访问标记

q[rear++]=i;//入队

}

}

}

}

int main()

{

scanf("%d%d",&n,&m);//n个结点，m条边

for(int i=0;i<m;i++)

{//构造无向图

int x,y;//输入2个结点;x->y;y->x;

scanf("%d%d",&x,&y);

Map[x][y]=1;//1代表x，y邻接

Map[y][x]=1;

}

book[1]=1;//标记结点1

printf("深度遍历路径 [%d]",1);

dfs(1);//从结点1深度遍历 (起始点可以随便选,1~n)

printf(" ");

memset(book,0,sizeof(book));//标记数组置0，用于广度遍历标记

printf("广度遍历路径 [%d]",1);

book[1]=1;//标记结点1

bfs(1);//从结点1广度遍历 (起始点可以随便选,1~n)

return 0;

}

/*5个结点,7条边

5 7

1 3

1 2

1 4

2 4

2 5

3 5

4 5

*/

/*************************邻接表*************************************/

#include<bits/stdc++.h>//万能头文件，C/C++都能用,包含了所有的头文件

using namespace std;//邻接表

const int N=300;

typedef struct st{

int v;//表头能到达的结点

struct st *next;//指向下一个结点的指针域

}*link,AK;//定义结点类型

struct sx{

AK *next;//表头指针域

}s[N];//n个结点,n个表头

int book[N]={0};//结点标记数组(1表示该点访问过了;0未访问过)

int n,m;

void create(int x,int y)

{//前插法构建邻接表

link p;

p=new AK;//开辟新结点

p->v=y;

p->next=s[x].next;

s[x].next=p;

}

void fun()

{//表头指针赋空(这一步至关重要,没有这一步无法建表)

for(int i=1;i<=n;i++)

s[i].next=NULL;

}

void dfs(int x)//深度遍历邻接表

{

link p=s[x].next;

while(p)

{

if(book[p->v]==0)

{

printf("->[%d]",p->v);

book[p->v]=1;

dfs(p->v);

}

p=p->next;

}

}

void bfs(int x)//广度遍历邻接表

{

int q[N]={0};//队列

int fornt=0;

int rear=0;

q[rear++]=x;

while(fornt<rear)

{

int k=q[fornt++];

link p=s[k].next;

while(p)

{

if(book[p->v]==0)

{

printf("->[%d]",p->v);

book[p->v]=1;

q[rear++]=p->v;

}

p=p->next;

}

}

}

void input()//打印邻接表

{//首列是表头(其后尾随的是与其邻接的结点)

//n个表头

link p;

for(int i=1;i<=n;i++)

{

p=s[i].next;

printf("[%d]",i);

while(p)

{

printf("->[%d]",p->v);

p=p->next;

}

cout<<endl;

}

}

int main()

{

fun();//调用表头置空

scanf("%d%d",&n,&m);//n个结点，m条边

for(int i=0;i<m;i++)

{//构造无向邻接表

int x,y;//输入2个结点;x->y;y->x;

scanf("%d%d",&x,&y);

create(x,y);//构建有向邻接表，只调用一个;

create(y,x);//构建无向邻接表，只调用两个;

}

book[1]=1;//标记结点1

printf("深度遍历路径 [%d]",1);

dfs(1);//从结点1深度遍历 (起始点可以随便选,1~n)

printf(" ");

memset(book,0,sizeof(book));//标记数组置0，用于广度遍历标记

printf("广度遍历路径 [%d]",1);

book[1]=1;//标记结点1

bfs(1);//从结点1广度遍历 (起始点可以随便选,1~n)

printf(" ");

printf("打印邻接表结构 ");

input();//打印邻接表

return 0;

}

/*5个结点,7条边

5 7

1 3

1 2

1 4

2 4

2 5

3 5

4 5

*/

Ⅳ c语言，关于邻接表的建立

AdjList 是自定义类型，是char类型，
第二行 typedef将char类型自定义为 VertexType，即VertexType代表了char型，
VertexType a 就相当于 char a；

同理

倒数第五行 typedef将VertexNode自定义为 AdjList[MaxVertexNum]类型，也就是说现在AdjList就代表了一个 “结构体数组” 类型
AdjList adjlist 相当于 VertexNode adjlist[MaxVertexNum]

这里主要是typedef关键字的使用 希望能帮到你

Ⅵ c语言图的遍历，邻接表存储，深度，广度优先遍历

（1） 图的建立，按采用邻接表作为存储结构。
（2） 从指定顶点出发进行深度优先搜索遍历。
（3） 从指定顶点出发进行广度优先搜索遍历。

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"math.h"

#define MAX_INT 1000
#define MAX_VERTEX_NUM 20
#define MAX_QUEUE_NUMBER 20

typedef struct ArcNode
{
int adjvex;
double adj;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VexNode
{
char szName[40];
ArcNode *firstarc;
}VexNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vexs;
int vexnum,arcnum;
}Net;
//定义队列
typedef struct{
int *elem;
int front, rear;
}Queue;
void InitQueue(Queue &Q)
{
Q.elem = new int[MAX_QUEUE_NUMBER];
Q.front = Q.rear = 0;
}
int EmptyQueue(Queue Q)
{
if(Q.front==Q.rear)
return 0;
else
return 1;
}
void DestroyQueue(Queue &Q){
delete []Q.elem;
Q.front = Q.rear = 0;
}

void EnterQueue(Queue &Q, int e)
{
if((Q.rear + 1)%MAX_QUEUE_NUMBER != Q.front)
Q.elem[Q.rear ] = e;
else
printf("队列满!\n");
Q.rear = (Q.rear + 1)%MAX_QUEUE_NUMBER;
}
void LeaveQueue(Queue &Q, int &e)
{
if(Q.rear != Q.front)
e = Q.elem[Q.front];
else
printf("队列空!\n");
Q.front = (Q.front+1)%MAX_QUEUE_NUMBER;
}
int LocateVex(Net ga,char *name)
{
int i;
for(i=0;i<ga.vexnum;i++)
if(strcmp(name,ga.vexs[i].szName)==0)
return i;
return -1;

}
void crt_net(Net &ga)
{
ArcNode *p;
char name1[40],name2[40];
int i,j,k;
double w;
printf("请输入顶点数和弧数：");
scanf("%d%d",&ga.vexnum,&ga.arcnum);
printf("请依次输入顶点名：\n");
for(i=0;i<ga.vexnum;i++)
{
scanf("%s",ga.vexs[i].szName);
ga.vexs[i].firstarc=NULL;
}
for(k=0;k<ga.arcnum;k++)
{
printf("请输入相邻的两个定点和权值：");
scanf("%s%s%lf",name1,name2,&w);
i=LocateVex(ga,name1);
j=LocateVex(ga,name2);
p=new ArcNode;
p->adjvex=j;
p->adj=w;
p->nextarc=ga.vexs[i].firstarc;
ga.vexs[i].firstarc=p;
}
}

void DFS(Net ga,char *name,int *visited)
{
int v,w;
ArcNode *p;
v=LocateVex(ga,name);
visited[v]=1;
printf("%s ",ga.vexs[v].szName);
p=ga.vexs[v].firstarc;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
DFS(ga,ga.vexs[w].szName,visited);
p=p->nextarc;
}

}
void DFSTravel(Net ga,char *name)
{
int v,k=0;
int visited[20];
for(v=0;v<ga.vexnum;v++)
visited[v]=0;
for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))
{
if(v+1==LocateVex(ga,name))
k++;
if(visited[v]==0)
DFS(ga,ga.vexs[v].szName,visited);

}
}

void BFSTravel(Net ga,char *name)
{
ArcNode *p;
int v,w,u,k=0;
Queue Q;
int visited[20];
for(v=0;v<ga.vexnum;v++)
visited[v]=0;
InitQueue(Q);
for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))
{
if(v+1==LocateVex(ga,name))
k++;
if(visited[v]==0)
{
visited[v]=1;
printf("%s ",ga.vexs[v].szName);
EnterQueue(Q,v);
while(EmptyQueue(Q)!=0)
{
LeaveQueue(Q,u);
p=ga.vexs[u].firstarc;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
{
printf("%s ",ga.vexs[w].szName);
visited[w]=1;
EnterQueue(Q,w);
}
p=p->nextarc;
}
}
}

}
}

void main()
{
char name[40];
Net ga;
crt_net(ga);
printf("请输入深度优先遍历开始点的名：");
scanf("%s",name);
printf("深度优先遍历：");
DFSTravel(ga,name);
printf("\n");
printf("请输入广度优先遍历开始点的名：");
scanf("%s",name);
printf("广度优先遍历：");
BFSTravel(ga,name);
printf("\n");

}

Ⅶ 在C语言中编程实现建立无向图的邻接表,输出某个点的邻接点~!

用矩阵表示无向图的，设有M个节点，则建立一个MXM矩阵，对每个顶点添加它的邻接点，即每行中对于有标记的列为该行顶点的邻接点。

Ⅷ 用c语言编程 1创建图的邻接矩阵和邻接表 2验证图的深度优先、广度优先遍历算法 3验证最短路径

这些是c++的代码不知是否满足你的要求。
1、邻接表表示的图中分别用DFS和BFS遍历
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 图的邻接表的结点
struct Edge
{
int dest; // 目标结点下标
// int value; // 路径长度
Edge *link; // 下一个结点
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 为图添加一条边
// Input: edge - 欲加边的结点; dest - 目的结点
// Output: edge - 加边后的结点
// Tags:
void AddEdge(Edge *&edge, int dest)
{
// 简单的链表操作
if (!edge)
{
edge = new Edge;
edge->dest = dest;
edge->link = 0;
}
else
{
Edge *tail = edge;
while (tail->link) tail = tail->link;
tail->link = new Edge;
tail = tail->link;
tail->dest = dest;
tail->link = 0;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: Console下输入图的边
// Input: Graph - 图; n - 图的结点的个数; EdgeNumber - 添加边的个数;
// Output: Graph - 添加边后的图
// Tags: 用户输入点对(a, b), 表示添加a->b的路径
void Input(Edge **&graph, int n, int EdgeNumber)
{
int i = 0, a, b;
for (i = 0; i < EdgeNumber; i++)
{
scanf("%d %d", &a, &b); // 用户输入起点终点
AddEdge(graph[a], b); // 添加a->b的边
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 深度优先搜索并输出
// Input: Graph - 图; n - 图的结点的个数; StartEdge — 开始的结点;
// Output: Console下输出遍历的顺序
// Tags: 递归调用 _dfs过程、回溯算法
void _dfs(Edge **&graph, bool *visited, int n, int index);
void DFS(Edge **&graph, int n, int StartEdge)
{
bool *visited = new bool[n]; // 标记每个结点是否已访问
memset(visited, (int)false, sizeof(bool) * n);
visited[StartEdge] = true;
printf("start edge: %d\n", StartEdge);
_dfs(graph, visited, n, StartEdge);
visited[StartEdge] = false;
}
// _dfs过程：
// Input: Graph - 图; n - 图的结点的个数; index - 当前的下标, visited - 记录结点是否已访问
// Output: Console下输出遍历的顺序
void _dfs(Edge **&graph, bool *visited, int n, int index)
{
int nIndex; // 下一个结点下标
Edge *edge = graph[index]; // 遍历用结点
while (edge) // 遍历所有的邻接结点
{
nIndex = edge->dest;
if (!visited[nIndex])
{
visited[nIndex] = true;
printf("%d\t", nIndex);
_dfs(graph, visited, n, nIndex);
}
edge = edge->link;
}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 广度优先搜索并输出
// Input: Graph - 图; n - 图的结点的个数; StartEdge - 开始的结点
// Output: Console下输出遍历的顺序
// Tags: 需要一个队列记录所有的灰色结点
void BFS(Edge **&graph, int n, int StartEdge)
{
bool *visited = new bool[n]; // 记录结点是否已访问
memset(visited, (int)false, sizeof(bool) * n);
queue<int> Q; // 记录准备访问的结点
Edge *edge; // 记录当前遍历的结点
int nIndex; // 记录下标

visited[StartEdge] = true;
printf("start edge:%d\n", StartEdge);
Q.push(StartEdge);
while (!Q.empty())
{
edge = graph[Q.front()];
while (edge)
{
nIndex = edge->dest;
if (!visited[nIndex])
{
visited[nIndex] = true;
printf("%d\t", nIndex);
Q.push(nIndex);
}
edge = edge->link;
}
Q.pop();
}
}
int main()
{
const int NODE_NUMBER = 7; // 10结点
const int EDGE_NUMBER = 11; // 10边
Edge **graph = new Edge *[NODE_NUMBER]; // 图
memset(graph, 0, sizeof(Edge *) * NODE_NUMBER); // 一开始没边
Input(graph, NODE_NUMBER, EDGE_NUMBER); // 输入边
printf("DFS:\n");
DFS(graph, NODE_NUMBER, 0); // 深度优先
printf("\n");
printf("BFS:\n");
BFS(graph, NODE_NUMBER, 0); // 广度优先
printf("\n");
return 0;
}

2、邻接矩阵表示的图中利用bellman-ford算法获得单点最短路
#include <cstdio>
#include <cstring>
using namespace std;
#define INTEGER_INF 0xffff // 表示无穷大路径
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 邻接矩阵表示的图
struct Graph
{
int **value; // 权值
int number; // 结点个数
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化图
// Input: number - 结点个数
// Output: graph - 图
void InitGraph(Graph &graph, int number)
{
int i, j;
graph.value = new int *[number];
for (i = 0; i < number; i++)
graph.value[i] = new int[number];
for (i = 0; i < number; i++)
{
for (j = 0; j < number; j++)
{
if (i == j)
graph.value[i][j] = 0;
else
graph.value[i][j] = INTEGER_INF;
}
}
graph.number = number;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 析构图
// Input: graph - 图
// Output: graph - 析构后的图的壳子
void FreeGraph(Graph &graph)
{
int i;
for (i = 0; i < graph.number; i++)
delete []graph.value[i];
delete []graph.value;
graph.number = 0;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 用户在Console下输入图的边
// Input: n - 边的数量
// Output: graph - 加边后的图
void AddEdge(Graph &graph, int n)
{
int i, a, b, v;
for (i = 0; i < n; i++)
{
scanf("%d%d%d", &a, &b, &v);
graph.value[a][b] = v;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: BellmanFord 算法计算单源最短路
// Input: graph - 图, index - 起点
// Output: true - 存在最短路 且 Console 下输出起点到各个顶点的最短路
// false - 不存在最短路(存在边权和为负的环路)
bool BellmanFord(Graph &graph, int index)
{
int num = graph.number; // 结点个数
int *v = new int[num]; // 记录最短路
int i, j, t;
// 设定初值
for (t = 1; t < num; t++)
v[t] = INTEGER_INF;
v[index] = 0;
// 松弛
for (t = 0; t < num - 1; t++) // 循环i-1次
for (i = 0; i < num; i++)
for(j = 0; j < num; j++)
if (i != j && graph.value[i][j] != INTEGER_INF) // 如果两顶点间有路
if (v[j] > v[i] + graph.value[i][j]) // 松弛
v[j] = v[i] + graph.value[i][j];
// 判断是否存在边权和为负的环路
for (i = 0; i < num; i++)
for (j = 0; j < num; j++)
if (graph.value[i][j] != INTEGER_INF &&
v[j] > v[i] + graph.value[i][j])
return false;
// 输出
for (t = 1; t < num; t++)
printf("%d\t", v[t]);
return true;
}
int main()
{
Graph graph;
InitGraph(graph, 5);
AddEdge(graph, 10);
if (!BellmanFord(graph, 0))
printf("该图中存在边权和为负的环路!\n");
FreeGraph(graph);
return 0;
}

Ⅸ 用邻接表表示的图的输出(PrintGraph)的算法(C语言)

单链表类中的输出流函数重载，输出链表
图类中再次重载输出流函数。
一次顶点表的循环，输出。
结果：<<start,dest,weight>,<。。。>>