그림 의 인접 행렬 (저장 구조, 그림 의 옮 겨 다 니 기, 최소 생 성 트 리, 관건 적 인 경로, 최 단 경로)
81243 단어 c 언어 데이터 구조데이터 구조c#
그림 은 유방 향도 (DG), 유방 향망 (DN), 무방 향도 (UDG), 무방 향망 (UDN) 으로 나 눌 수 있다
인접 행렬 의 저장 구조
//
typedef struct{
ElemType vexs[N]; //
int arcs[N][N]; //
// arcs[i][j] = （ i = j 0）
int vexnum, arcnum; //
}MGraph;
인접 행렬 의 방식 구조 도 (무방 향 도 예)
//
int LocateVex(MGraph G, ElemType v)
{
//
int i;
for(i = 0; i<G.vexnum; i++)
{
if(v == G.vexs[i])
return i;
}
return -1; // -1
}
void Create_UDN(MGraph &G)
{
int i, j;
ElemType v1, v2;
int a1, a2;
scanf("%d %d", &G.vexnum, &G.arcnum);//
//
for(i = 0;i<G.vexnum; i++) //
scanf("%d", &G.vexs[i]);
//
for(i = 0; i<G.vexnum; i++)
{
for(j = 0; j<G.vexnum; j++)
{
G.arcs[i][j] = 0; //
}
}
//
for(i = 0; i<G.arcnum; i++)
{
scanf("%d %d", &v1, &v2);
a1 = LocateVex(G, v1);
a2 = LocateVex(G, v2);
G.arcs[a1][a2] = G.arcs[a2][a1] = 1;
// G.arcs[a1][a2] = 1
}
}
그림 의 편력
1. 깊이 우선 옮 겨 다 니 기 (Depth First Search)
알고리즘 사상: 1. 그림 의 한 정점 v 에서 출발 하여 이 정점 을 방문 한 다음 에 v 의 방문 되 지 않 은 인접 정점 에서 깊이 있 게 그림 을 옮 겨 다 니 며 그림 의 모든 v 와 연 결 된 정점 이 방문 되 었 을 때 까지.2. 만약 에 이 그림 에 정점 이 방문 되 지 않 았 다 면 (즉, 연결 되 지 않 은 그림) 방문 되 지 않 은 정점 의 시작 점 을 선택 하고 이 과정 을 반복 하여 모든 정점 이 방문 되 었 을 때 까지 합 니 다.
int visited[N]; // 0
int FirstAdjVex(MGraph G, int v)
{
// v , -1
int i, j;
for(i = 0; i<G.vexnum; i++)
{
if(G.arcs[v][i] == 1)
return i;
}
return -1;
}
int NextAdjVex(MGraph G ,int v, int w)
{
// v
int i;
for(i = w+1; i<G.vexnum; i++)
{
if(G.arcs[v][i] == 1)
return i;
}
return -1;
}
// v（ ）
void DFS(MGraph G, int v)
{
// v，
printf("%d ", G.vexs[v]);
visited[v] = 1;
int w;
//v
w = FirstAdjVex(G, v);
while(w>=0)
{
if(visited[w] == 0) // w w
DFS(G, w);
w = NextAdjVex(G ,v, w); // v
}
}
void DFSTraverse(MGraph G)
{
int i;
for(i = 0; i<G.vexnum; i++)
visited[i] = 0; //
for(i = 0; i<G.vexnum; i++)
if(visited[i] == 0) // i ， DFS
DFS(G, i);
}
void DFS(MGraph G, int v)
{
int i;
printf("%d,",G.vexs[v]);
visited[v] = 1;
for(i = 0; i<G.vexnum; i++)
{
if(visited[i]==0 && G.arcs[v][i] == 1)
{
DFS(G, i);
}
}
}
void DFSTraverse(MGraph G)
{
int i;
for(i = 0; i<G.vexnum; i++)
visited[i] = 0; //
for(i = 0; i<G.vexnum; i++)
if(visited[i] == 0) // i ， DFS
DFS(G, i);
}
2. 범위 우선 옮 겨 다 니 기 (Broadth First Search)
// （Broadth_First Search）
void BFSTraverse(MGraph G)
{
//
int Q[N]; //
int front, rear; //
front = rear = 0;
int i, j;
int v;
for(i = 0; i<G.arcnum; i++)
visited[i] = 0;
for(i = 0; i<G.vexnum; i++)
{
if(visited[i] == 0)
{
//
Q[rear++] = i;
visited[i] = 1;
printf("%d ", G.vexs[i]);
//*************************************
while(front != rear)
{
//
v = Q[front++];
// v
for(j = 0; j<G.vexnum; j++)
if(G.arcs[v][j] == 1 && visited[j]==0)
{
Q[rear++] = j;
visited[j] = 1;
printf("%d ", G.vexs[j]);
}
}
}
}
}
// （Broadth_First Search）
void BFSTraverse(MGraph G)
{
//
int Q[N]; //
int front, rear; //
front = rear = 0;
int i, j;
int v;
for(i = 0; i<G.arcnum; i++)
visited[i] = 0;
for(i = 0; i<G.vexnum; i++)
{
if(visited[i] == 0)
{
//
Q[rear++] = i;
visited[i] = 1;
printf("%d ", G.vexs[i]);
//*************************************
int v ,w;
while(front != rear)
{
//
v = Q[front++];
w = FirstAdjVex(G, v);
while(w>=0)
{
if(!visited[w])
{
//
Q[rear++] = w;
visited[w] = 1;
printf("%d ", G.vexs[w]);
}
w = NextAdjVex(G , v, w);
}
}
}
}
}
그림 의 흔 한 알고리즘
최소 생 성 트 리
1. 프 림 알고리즘 (Prim)
알고리즘 사상:
closege[i-1].lowcost = Min{ cost(vi , u) | u∈U }
closege[i-1].vexs = { u | cost(vi , u ) }
// (Prim)
void MiniTree_Prim(MGraph G, ElemType v)
{
// v
struct{
int lowcost; // 0
ElemType vex; //closege[i].vex, i
}closege[N];
int i, j, k;
int w; //
w = LocateVex(G, v);
for(i = 0; i<G.vexnum; i++)
{
// closege[]
if(i != w)
closege[i].lowcost = G.arcs[w][i];
else
closege[i].lowcost = 0;
closege[i].vex = v;
}
int t;
for(i = 1; i<G.vexnum; i++)// G.vexnum-1
{
int min = 99999;
// ， U
for(j = 0; j<G.vexnum; j++)
{
if(closege[j].lowcost < min && closege[j].lowcost != 0)
{
min = closege[j].lowcost;
t = j;
}
}
printf("%d %d,", closege[t].vex, G.vexs[t]);
closege[t].lowcost = 0; // U ，
//
for(k = 0; k<G.vexnum; k++)
{
if(G.arcs[t][k] < closege[k].lowcost)
{
closege[k].lowcost = G.arcs[t][k];
closege[k].vex = G.vexs[t];
}
}
}
}
2. 크 루스 칼 알고리즘 (Kruskal)
알고리즘 사상:
AOV - 네트 랑 AOE. - 네트.
알고리즘 사상:
// (Topological Sort)，
void TopologicalSort(MGraph G)
{
//
int degree[N] = {
0};
int S[N]; //
int top = 0; //
int t; //t
int i, j;
int n = 0; // ，
for(i = 0; i<G.vexnum;i++)
for(j = 0; j<G.vexnum;j++)
degree[i]+=G.arcs[j][i];
//
for(i = 0; i<G.vexnum; i++)
if(degree[i] == 0)
S[top++] = i;
while(top != 0)
{
//
t = S[--top];
printf("%d ", G.vexs[t]);
n++;
// -1， 0
for(i = 0; i<G.vexnum; i++)
{
if(G.arcs[t][i] == 1)
{
degree[i]--;
if(degree[i] == 0)
S[top++] = i;
}
}
}
if(n<G.vexnum)
printf(" ");
}
관건 적 인 경로 문제, AOE - 네트워크
//
int ve[N] = {
0}; // ai
int vl[N] = {
0}; // ai
int T[N];
int top1 = -1; //
int S[N];
int top2 = -1; //
Status TopologicalOrder(MGraph G)
{
int i, j;
int degree[N] = {
0}; //
int e; //
int count; // ， ，
//
for(i = 0; i<G.vexnum; i++)
{
for(j = 0; j<G.vexnum; j++)
{
if(G.arcs[i][j] > 0 && G.arcs[i][j] < MAX)
degree[j]++;
}
}
for(i = 0; i<G.vexnum; i++)
{
if(degree[i] == 0)
{
S[++top2] = i; //
T[++top1] = i; //
count++;
}
}
// ，
while(top2 != -1)
{
e = S[top2--];
for(i = 0; i<G.vexnum; i++)
{
if(G.arcs[e][i] < MAX && G.arcs[e][i] != 0)
{
degree[i]--;
if(degree[i] == 0)
{
S[++top2] = i;
T[++top1] = i;
count++;
if(ve[e] + G.arcs[e][i] > ve[i])
ve[i] = ve[e] + G.arcs[e][i];
}
}
}
}
if(count < G.vexnum)
{
return 0;
}
return 1;
}
//
Status CtriticalPath(MGraph G)
{
if(!TopologicalOrder(G))
return 0;
int i;
int e;
e = T[top1--];
//
for(i = 0; i<G.vexnum; i++)
vl[i] = ve[e];
// ， T ,
while(top1 != -1)
{
for(i = 0; i<G.vexnum; i++)
{
if(G.arcs[i][e] > 0 && G.arcs[i][e] < MAX)
{
if(vl[e]-G.arcs[i][e] < vl[i])
vl[i] = vl[e]-G.arcs[i][e];
}
}
e = T[top1--];
}
//
for(i = 0; i<G.vexnum; i++)
if(ve[i] == vl[i])
printf("%d %d,", i,ve[i]);
return 1;
}
질문
1. 디 제 스 트 라 알고리즘 (Dijkstra)
void ShortestPath_DIJ(MGraph &G, int v0)
{
int D[N]; //D[v] V0 V
int P[N]; // V0 V W。
int final[N]; // V 。0 ，1
int i, j ,v;
for(i = 0; i<G.vexnum; i++)
{
D[i] = G.arcs[v0][i];
P[i] = v0;
final[i] = 0;
}
final[v0] = 1;
D[v0] = 0;
for(i = 1; i<G.vexnum; i++)
{
int min = 999999;
int v;
for(j = 0; j<G.vexnum; j++)
{
if(D[j] < min && final[j] == 0)
{
min = D[j];
v = j;
}
}
final[v] = 1;
for(j = 0; j<G.vexnum; j++) //
{
if(D[j] > G.arcs[v0][v] + G.arcs[v][j])
{
D[j] = G.arcs[v0][v] + G.arcs[v][j];
P[j] = v;
}
}
}
}
1. 프로 이 드 알고리즘 (Floyd)
// (Floyd)
void ShortestPath_FLOYD(MGraph G)
{
int i, j, k;
int D[N][N]; //D[i][j] i j
int P[N][N]; //P[i][j] i j
//
for(i = 0; i<G.vexnum; i++)
{
for(j = 0; j<G.vexnum; j++)
{
D[i][j] = G.arcs[i][j];
P[i][j] = i;
}
}
for(i = 0; i<G.vexnum; i++)
{
for(j = 0; j<G.vexnum; j++)
{
for(k = 0; k<G.vexnum; k++)
{
if(D[j][k] > D[j][i] + D[i][k])
{
D[j][k] = D[j][i] + D[i][k];
P[j][k] = i;
}
}
}
}
}**
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
C 언어 이 진 트 리 의 옮 겨 다 니 기나 무 는 비교적 중요 한 데이터 구조, 특히 이 진 트 리 이다.이 진 트 리 는 특수 한 나무 로 이 진 트 리 의 각 노드 에 최대 두 개의 키 노드 가 있 는데 보통 왼쪽 노드 와 오른쪽 노드 (또는 왼쪽 아...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
